Primal and dual active-set methods for convex quadratic programming
From MaRDI portal
Publication:312693
DOI10.1007/S10107-015-0966-2zbMATH Open1346.90652OpenAlexW2216549247MaRDI QIDQ312693FDOQ312693
Abstract: 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.
Recommendations
- Methods for convex and general quadratic programming
- scientific article; zbMATH DE number 3982419
- A numerically stable dual method for solving strictly convex quadratic programs
- A feasible active set method for strictly convex quadratic problems with simple bounds
- Globally convergent primal-dual active-set methods with inexact subproblem solves
Cites work
- scientific article; zbMATH DE number 6610411 (Why is no real title available?)
- scientific article; zbMATH DE number 1215253 (Why is no real title available?)
- scientific article; zbMATH DE number 4197288 (Why is no real title available?)
- scientific article; zbMATH DE number 2201293 (Why is no real title available?)
- A General Quadratic Programming Algorithm
- A Globally Convergent Stabilized SQP Method
- A computational method for the indefinite quadratic programming problem
- A dual-active-set algorithm for positive semi-definite quadratic programming
- A globally convergent primal-dual active-set framework for large-scale convex quadratic optimization
- A method for solving nonlinear maximum‐problems depending on parameters
- A numerical study of limited memory BFGS methods
- A numerically stable dual method for solving strictly convex quadratic programs
- A practical anti-cycling procedure for linearly constrained optimization
- A weighted gram-schmidt method for convex quadratic programming
- An Algorithm for Large-Scale Quadratic Programming
- An iterative working-set method for large-scale nonconvex quadratic programming
- An online active set strategy to overcome the limitations of explicit MPC
- Benchmarking optimization software with performance profiles.
- CUTE
- CUTEr and SifDec
- CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization
- Direct Methods for Solving Symmetric Indefinite Systems of Linear Equations
- Factorizing symmetric indefinite matrices
- GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization
- Inertia-Controlling Methods for General Quadratic Programming
- Inertia-controlling factorizations for optimization algorithms
- MA57---a code for the solution of sparse symmetric definite and indefinite systems
- Methods for convex and general quadratic programming
- New Finite Pivoting Rules for the Simplex Method
- Newton Methods for Large-Scale Linear Equality-Constrained Minimization
- Numerically stable methods for quadratic programming
- On the quadratic programming algorithm of Goldfarb and Idnani
- Optimality and Degeneracy in Linear Programming
- Pivot selection methods of the Devex LP code
- QPSchur: A dual, active-set, Schur-complement method for large-scale and structured convex quadratic programming
- Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization
- Resolving degeneracy in quadratic programming
- SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization
- Some Stable Methods for Calculating Inertia and Solving Symmetric Linear Systems
- Stable reduced Hessian updates for indefinite quadratic programming
- Superlinear convergence of a stabilized SQP method to a degenerate solution
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- The generalized simplex method for minimizing a linear form under linear inequality restraints
- The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling
- qpOASES: a parametric active-set algorithm for~quadratic programming
Cited in
(20)- scientific article; zbMATH DE number 3982419 (Why is no real title available?)
- Methods for convex and general quadratic programming
- A weighted gram-schmidt method for convex quadratic programming
- Optimal Subsampling via Predictive Inference
- Globally convergent primal-dual active-set methods with inexact subproblem solves
- Conflict Analysis for MINLP
- QPSchur: A dual, active-set, Schur-complement method for large-scale and structured convex quadratic programming
- Quadratic maximization of reachable values of affine systems with diagonalizable matrix
- A globally convergent primal-dual active-set framework for large-scale convex quadratic optimization
- A dual gradient-projection method for large-scale strictly convex quadratic problems
- Active set methods with reoptimization for convex quadratic integer programming
- An active set algorithm for nonlinear optimization with polyhedral constraints
- Revisiting degeneracy, strict feasibility, stability, in linear programming
- Single image blind deblurring based on salient edge-structures and elastic-net regularization
- Nonparametric density estimation with nonuniform B-spline bases
- A feasible active set method for strictly convex quadratic problems with simple bounds
- A dual-active-set algorithm for positive semi-definite quadratic programming
- PAL-Hom method for QP and an application to LP
- On a primal-dual Newton proximal method for convex quadratic programs
- A constraint-reduced MPC algorithm for convex quadratic programming, with a modified active set identification scheme
Describes a project that uses
Uses Software
This page was built for publication: Primal and dual active-set methods for convex quadratic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q312693)
