On the identification of local minimizers in inertia-controlling methods for quadratic programming


The verification of a local minimizer of a general (i.e., nonconvex) quadratic program is in general an NP-hard problem. The difficulty concerns the optimality of certain points (which we call dead points) at which the first-order necessary conditions for optimality are satisfied, but strict complementarity does not hold. Inertia-controlling quadratic programming (ICQP) methods form an important class of methods for solving general quadratic programs. We derive a computational scheme for proceeding at a dead point that is appropriate for a general ICQP method.
Return To PEG's Home Page.