Quadratic programming solvers: summary of choices for bounded biharmonic weights

Alec Jacobson

August 17, 2011

weblog/

My recent SIGGRAPH paper Bounded biharmoinc weights for real-time deformation relies on being able to solve sparse quadratic programming problems with constant inequality (box) constraints and sometimes (for our "full solution") linear equality constraints. More generally we solved problems that looked like this 
min x'Qx + x'L + C
subject to Ax ≤ b
where Q is an square n by n matrix of the quadratic coefficients, L is a n-size column vector of linear coefficients, C is a negligible scalar, constant term, A is a possible rectangular m by n matrix of linear inequality constraint coefficients and b is a m-size column vector of linear inequality values. Notice that Ax ≤ b fully captures all of the following just by playing with signs and adding extra rows: 
Ax ≤ b
Ax ≥ b
Ax = b
x ≥ lx //constant lower bound constraints
x ≤ ux //constant upper bound constraints
x = b
where A is an m by n matrix, and b, lx, and ux are a m-size column vectors. For example x≤ ux is the same as Ix ≤ ux where I is an m by n matrix with only ones along the main diagonal. If we want x = b then we can just stack the rows of Ix ≤ b and -Ix ≤ -b. Some solvers don't support full linear inequality constraints instead only some of the above (say, constant bound constraints), others support not only linear inequality constraints but also interfaces each of the above (ideally we'd assume that the solver optimizes Our main concerns were that the solver supported: In the end for the publication we chose MOSEK. Recently MATLAB has added sparse support for its quadprog function in the Optimization Toolbox which we know use in our 2D MATLAB prototype code. Here's a dump of my rough survey of what I've tried: 
= Works = 

Mosek
  min x'Qx + x'L + C
  subject to Ax ≤ b 
  (and lx ≤ x ≤ ux)
  interior point 
  sparse
  matlab, C++
  easy to install
  free for academics
  fast

MINQ:  General Definite and Bound Constrained Indefinite QP
  min 0.5x'Qx + Lx + C
  subject to Ax ≤ b 
  (or lx ≤ x ≤ ux)
  Q must be symmetric
  sparse
  active set method
  moderate speed
  seems only single precision accuracy
  supports initial guess
  must run multiple times
  finds ~ active set as matlab dense active set
  use interior-point method's solution as initial guess to get active set
  free
  easy to install (only matlab .m files)

MATLAB quadprog
  min x'Qx + x'L + C
  subject to Ax ≤ b 
  (and lx ≤ x ≤ ux)
  interior-point method
    sparse
    fast, though slower than mosek
    must carefully set tolerance parameters
  active-set method
    dense only
    slow (because its dense)
    must carefully set tolerance parameters
    reproduces interior-point method solution up to single precision

QPC Quadratic Programming in C
  min ||Ax - b||²
  subject to Ax ≤ b 
  (and lx ≤ x ≤ ux)
  free
  easy to install (precompiled mex binaries)
  dense only 
  fast, surprisingly ~ matlab sparse interior-point
  active-set method
    dense only 
    reproduces MATLAB interior-point method solution up to single precision
    finds ~ active set as MATLAB active set
  interior-point method
    crashes if upper bound equals lower bound (must offset by eps)
    doesn't seem to converge correctly (objective function still very large)

= Not working out =

SLS "A Matlab Toolbox for Sparse Least Squares problems"
  SBLS2.m
    min ||Ax - b||²
    subject to lx ≤ x ≤ ux
    sparse
    active-set method
    easy to install (only matlab .m files)
    doesn't seem to converge correctly (e.g. against MATLAB dense active-set)
    solution doesn't strictly obey bounds, must clamp after-the-fact
  SBLS.m
    min ||Ax - b||²
    subject to lx ≤ x ≤ ux
    sparse
    interior-point method
    easy to install (only matlab .m files)
    fast
    crashes if upper bound equals lower bound (must offset by eps)
    comparable to MATLAB sparse quadprog

LBFGSB
  min f(x)
  subject to lx ≤ x ≤ ux
  quasi-Newton: only needs gradient
  iterative loop caller must manage
  needs external sparse matrix factorization if using for QP
  hard to install (fortan)
  free
  sparse
  slow for QP (e.g. compared to Mosek)

Newton-KKT Interior-Point Methods for Indefinite Quadratic Programming
  dense only
  bad documentation (error messages with no explanation)
  not easily adapted to handle sparse
  easy to install (single matlab .m file)
  
CGAL's QP Solver
  dense
  seems to require all of CGAL

LOQO sparse convex optimization
  min f(x)
  subject to lb ≤ a(x) ≤ ub
  (and lx ≤ x ≤ ux)
  sparse
  not free (limited free student version)
  hard to install (precompiled mex binaries for old computers/linux only)
  matlab interface
QP benchmark