A parametric active set method for quadratic programs with vanishing constraints

Combinatorial and logic constraints arising in a number of challenging optimization applications can be formulated as vanishing constraints. Quadratic programs with vanishing constraints (QPVCs) then arise as subproblems during the numerical solution of such problems using algorithms of the Sequential Quadratic Programming type. QPVCs are nonconvex problems violating standard constraint qualifications. In this paper, we propose a primal--dual parametric active set method for finding strongly stationary points of QPVCs under the MPVC--LICQ regularity condition. We develop a local search strategy that allows to improve such points up to global optimality for this subclass of nonconvex QPVC subproblems. A parametric programming framework facilitates the realization of hot--starting capabilities which improves the efficiency of both the active set method and the local search. We apply the developed methods to solve several instances of a robot path--finding problem with logic communication constraints.


Accepted for publication in Pacific Journal of Optimization.