Optimization Online


A Globally Convergent Primal-Dual Active-Set Framework for Large-Scale Convex Quadratic Optimization

Frank E. Curtis (frank.e.curtis***at***lehigh.edu)
Zheng Han (zhh210***at***lehigh.edu)
Daniel P. Robinson (daniel.p.robinson***at***jhu.edu)

Abstract: We present a primal-dual active-set framework for solving large-scale convex quadratic optimization problems (QPs). In contrast to classical active-set methods, our framework allows for multiple simultaneous changes in the active- set estimate, which often leads to rapid identification of the optimal active-set regardless of the initial estimate. The iterates of our framework are the active-set estimates themselves, where for each a primal-dual solution is uniquely defined via a reduced subproblem. Through the introduction of an index set auxiliary to the active-set estimate, our approach is globally convergent for strictly convex QPs. Moreover, the computational cost of each iteration typically is only modestly more than the cost of solving a reduced linear system. Numerical results are provided, illustrating that two proposed instances of our framework are efficient in practice, even on poorly conditioned problems. We attribute these latter benefits to the relationship between our framework and semi-smooth Newton techniques.

Keywords: convex quadratic optimization, active-set methods, large-scale optimization, semi-smooth Newton methods

Category 1: Nonlinear Optimization

Category 2: Convex and Nonsmooth Optimization

Citation: Computational Optimization and Applications, DOI: 10.1007/s10589-014-9681-9, 2014


Entry Submitted: 10/17/2012
Entry Accepted: 10/17/2012
Entry Last Modified: 11/16/2014

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