Sparse quadratic programming solver in libigl

Alec Jacobson

September 13, 2013

weblog/

I've implemented an active set solver for solving larger sparse quadratic programming problems. It's now part of our libigl library (Version ≥ 0.3.1). It's implemented using Eigen and follows closely Section 2.2.3 of my phd thesis.

Calling the function looks like:

active_set(A,B,known,Y,Aeq,Beq,Aieq,Bieq,lx,ux,Z)

Which solves the optimization problem:

    argmin ZT * A * Z + ZT * B
      Z
    subject to:  Z_known = Y
                 Aeq * Z = Beq
                Aieq * Z ≤ Bieq
                       Z ≥ lx
                       Z ≤ ux

Note: Since Eigen does not have an LDLT solver for semi-positive-definite sparse matrices yet, I'm using SparseLU which is unnecessarily slow.

Note: I'm not checking for linearly dependent constraints, so the rows of [Aeq;Aieq] must be linearly independent.

Update: I now check for linearly dependent constraints. However, I can't get a sparse Q matrix from Eigen's Sparse QR decomposition so when I encounter linearly dependent constraints some sparse operations sadly seem to become dense.

Note: I have not attempted any performance optimizations (yet). Don't expect this to beat MATLAB or Mosek's quadprogs. But do enjoy that this is a free, easy to incorporate QP solver in C++.