Linear programs

The following routines attempt to solve linear programs of the form

\[\text{min}\, c^T z \;\;\;\text{such that }Az=b,\; z \ge 0.\]

using the Alternating Direction Method of Multipliers.

The following functions were inspired by a simple ADMM linear program solver due to Boyd et al. Elemental’s implementations make use of parallel (dense) linear algebra, a custom structured factorization, and allows the user to optionally directly invert the (pivoted) Schur complement to accelerate its application. The return value is the number of performed ADMM iterations.

C++ API

Int LinearProgram(const Matrix<Real> &A, const Matrix<Real> &b, const Matrix<Real> &c, 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 LinearProgram(const AbstractDistMatrix<Real> &A, const AbstractDistMatrix<Real> &b, const AbstractDistMatrix<Real> &c, 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)

Implementation

Example driver

Parameters Input/Output Explanation
A Input part of constraints, \(Ax=b\)
b Input part of constraints, \(Ax=b\)
c Input part of the objective, \(c^T x\)
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 directly compute Schur-complement inverse?
progress Input display detailed progress information?

C API

ElError ElLinearProgram_s(ElConstMatrix_s A, ElConstMatrix_s b, ElConstMatrix_s c, ElMatrix_s z, ElInt* numIts)
ElError ElLinearProgram_d(ElConstMatrix_d A, ElConstMatrix_d b, ElConstMatrix_d c, ElMatrix_d z, ElInt* numIts)
ElError ElLinearProgramDist_s(ElConstDistMatrix_s A, ElConstDistMatrix_s b, ElConstDistMatrix_s c, ElDistMatrix_s z, ElInt* numIts)
ElError ElLinearProgramDist_d(ElConstDistMatrix_d A, ElConstDistMatrix_d b, ElConstDistMatrix_d c, ElDistMatrix_d z, ElInt* numIts)