Optimization Online


A parametric active set method for quadratic programs with vanishing constraints

Christian Kirches (christian.kirches***at***iwr.uni-heidelberg.de)
Andreas Potschka (potschka***at***iwr.uni-heidelberg.de)
Hans Georg Bock (bock***at***iwr.uni-heidelberg.de)
Sebastian Sager (sebastian.sager***at***iwr.uni-heidelberg.de)

Abstract: 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.

Keywords: parametric quadratic programming, mathematical programs with vanishing constraints, active set methods, robot motion planning

Category 1: Combinatorial Optimization (Other )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Applications -- Science and Engineering (Control Applications )

Citation: Accepted for publication in Pacific Journal of Optimization.


Entry Submitted: 01/10/2011
Entry Accepted: 01/10/2011
Entry Last Modified: 11/06/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society