Change search
ReferencesLink to record
Permanent link

Direct link
Primal and dual active-set methods for convex quadratic programming
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.ORCID iD: 0000-0002-6252-7815
2016 (English)In: Mathematical programming, ISSN 0025-5610, E-ISSN 1436-4646, Vol. 159, no 1-2, 469-508 p.Article in journal (Refereed) Published
Abstract [en]

Computational methods are proposed for solving a convex quadratic program (QP). Active-set methods are defined for a particular primal and dual formulation of a QP with general equality constraints and simple lower bounds on the variables. In the first part of the paper, two methods are proposed, one primal and one dual. These methods generate a sequence of iterates that are feasible with respect to the equality constraints associated with the optimality conditions of the primal-dual form. The primal method maintains feasibility of the primal inequalities while driving the infeasibilities of the dual inequalities to zero. The dual method maintains feasibility of the dual inequalities while moving to satisfy the primal inequalities. In each of these methods, the search directions satisfy a KKT system of equations formed from Hessian and constraint components associated with an appropriate column basis. The composition of the basis is specified by an active-set strategy that guarantees the nonsingularity of each set of KKT equations. Each of the proposed methods is a conventional active-set method in the sense that an initial primal- or dual-feasible point is required. In the second part of the paper, it is shown how the quadratic program may be solved as a coupled pair of primal and dual quadratic programs created from the original by simultaneously shifting the simple-bound constraints and adding a penalty term to the objective function. Any conventional column basis may be made optimal for such a primal-dual pair of shifted-penalized problems. The shifts are then updated using the solution of either the primal or the dual shifted problem. An obvious application of this approach is to solve a shifted dual QP to define an initial feasible point for the primal (or vice versa). The computational performance of each of the proposed methods is evaluated on a set of convex problems from the CUTEst test collection.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2016. Vol. 159, no 1-2, 469-508 p.
Keyword [en]
Quadratic programming, Active-set methods, Convex quadratic programming, Primal active-set methods, Dual active-set methods
National Category
Computational Mathematics
URN: urn:nbn:se:kth:diva-193822DOI: 10.1007/s10107-015-0966-2ISI: 000382053900015ScopusID: 2-s2.0-84949941906OAI: diva2:1038579

QC 20161019

Available from: 2016-10-19 Created: 2016-10-11 Last updated: 2016-10-19Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Forsgren, Anders
By organisation
Optimization and Systems Theory
In the same journal
Mathematical programming
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 4 hits
ReferencesLink to record
Permanent link

Direct link