Quadratic programs

The following routines attempt to solve quadratic programs of the form

\[\text{min} \frac{1}{2} z^T P z + q^T z\;\;\;\text{such that }l_b \le z \le u_b\]

using the Alternating Direction Method of Multipliers.

These functions are inspired by a simple ADMM quadratic program solver due to Boyd et al. Elemental’s implementations make use of parallel (dense) linear algebra and allows the user to optionally directly invert the Cholesky factor to improve the parallel performance of the application of its inverse.

C++ API

Int QuadraticProgram(const Matrix<Real> &P, const Matrix<Real> &q, Real lb, Real ub, Matrix<Real> &z, Real rho = 1., Real alpha = 1.2, Int maxIter = 500, Real absTol = 1e-6, Real relTol = 1e-4, bool inv = false, bool progress = true)

Int QuadraticProgram(const AbstractDistMatrix<Real> &P, const AbstractDistMatrix<Real> &q, Real lb, Real ub, AbstractDistMatrix<Real> &z, Real rho = 1., Real alpha = 1.2, Int maxIter = 500, Real absTol = 1e-6, Real relTol = 1e-4, bool inv = true, bool progress = true)

Implementations

Example driver

Parameters	Input/Output	Explanation
P	Input	SPD and part of objective, \(\frac{1}{2}x^T P x + q^T x\)
q	Input	part of objective
lb	Input	lower-bound of constraints, \(l_b \le x \le u_b\)
ub	Input	upper-bound of constraints, \(l_b \le x \le u_b\)
z	Output	primal solution (second term)
rho	Input	augmented-Lagrangian parameter
alpha	Input	over-relaxation parameter (usually in \([1,1.8]\))
maxIter	Input	maximum number of ADMM iterations
absTol	Input	absolute convergence tolerance
relTol	Input	relative convergence tolerance
inv	Input	compute inverse of Cholesky factor?
progress	Input	display detailed progress information?

C API

ElError ElQuadraticProgram_s(ElConstMatrix_s P, ElConstMatrix_s S, float lb, float ub, ElMatrix_s Z, ElInt* numIts)

ElError ElQuadraticProgram_d(ElConstMatrix_d P, ElConstMatrix_d S, double lb, double ub, ElMatrix_d Z, ElInt* numIts)

ElError ElQuadraticProgramDist_s(ElConstDistMatrix_s P, ElConstDistMatrix_s S, float lb, float ub, ElDistMatrix_s Z, ElInt* numIts)

ElError ElQuadraticProgramDist_d(ElConstDistMatrix_d P, ElConstDistMatrix_d S, double lb, double ub, ElDistMatrix_d Z, ElInt* numIts)