Optimization Online


Reliable solution of convex quadratic programs with parametric active set methods

Andreas Potschka (potschka***at***iwr.uni-heidelberg.de)
Christian Kirches (christian.kirches***at***iwr.uni-heidelberg.de)
Hans Georg Bock (bock***at***iwr.uni-heidelberg.de)
Johannes P. Schlöder (j.schloeder***at***iwr.uni-heidelberg.de)

Abstract: Parametric Active Set Methods (PASM) are a relatively new class of methods to solve convex Quadratic Programming (QP) problems. They are based on tracing the solution along a linear homotopy between a QP with known solution and the QP to be solved. We explicitly identify numerical challenges in PASM and develop strategies to meet these challenges. To demonstrate the reliability improvements of the proposed strategies we have implemented a prototype code called rpasm. We compare the results of the code with those of other popular academic and commercial QP solvers on problems of a subset of the Maros-M\'esz\'aros test examples. Our code is the only one to solve all of the problems with the default settings. Furthermore, we propose how PASM can be used to compute local solutions of nonconvex QPs.

Keywords: active set, convex, homotopy method, parametric quadratic programming

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Optimization Software and Modeling Systems (Optimization Software Benchmark )

Citation: technical report, Interdisciplinary Center for Scientific Computing, Heidelberg University, Im Neuenheimer Feld 368, 69120 Heidelberg, GERMANY, November, 2010

Download: [PDF]

Entry Submitted: 11/24/2010
Entry Accepted: 11/24/2010
Entry Last Modified: 01/31/2011

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 Programming Society