# Quadratic programming solvers: summary of choices for bounded biharmonic weights

## 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:
• sparse matrices
• linear inequality constraints
• large number of variables
• fast convergence
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
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)

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

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)

LBFGSB
min f(x)
subject to lx ≤ x ≤ ux
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