P000022

*Ruey-Lin Sheu (National Cheng Kung University (NCKU)) rsheu@mail.ncku.edu.tw

An optimization problem which minimizes a quadratic function subject to a set of linear inequality constraints is usually referred to as Quadratic Programming (QP). If the objective function is convex, (QP) is a convex problem and it can be solved in polynomial time. In contrast, for an nonconvex QP, it is known to be NP-hard. By now, no universal method can globally solve (QP). The best attempts so far, including the active set method or the interior point method, can just either obtain the KKT points of (QP) or solve some special case of it. In the talk, we first review some existing methods/techniques for QP and point out the difficulty of a nonconvex QP by negative results on the hidden convexity of QP and by comparing with the extended trust region subproblems (eTRS). Then we present some of our early studies on nonconvex QP. Our study focuses on two themes of the problem: we first study the attainment issue of a nonconvex QP. Then, for an attained QP, we show that it can be always reduced to a convex problem of smaller dimensions. However, the reduction cannot completely avoid enumerations on either vertices or facets of the polyhedron so that it might be still exponential in the worse complexity. Nevertheless, since on each node of branching, we only have to check convexity of the subproblem rather than to actually solve it like the active set method, it reduces considerably the computational cost.

Math formula preview: