LIBQP

LIBQP is C library implementing algorithms for two instances of convex Quadratic Programming (QP) frequently appearing in machine learning algorithms.

QP with simplex constraints

$$\min_{x} \left [ \frac{1}{2}x^T H x + x^T f\right] \quad \mbox{suject to}\quad \begin{array}{rcll} \sum_{i\in I_k} x_i & = & b_k\,, &k\in S_{equ}\, \\ \sum_{i\in I_k} x_i & \leq & b_k \,, & k\in S_{ineq}\, \\ x_i & \geq & 0\,, & i\in I \\ \end{array} $$

where $x=(x_1,\ldots,x_n)\in\Re^n$ are the optimized variables, $H\in\Re^{n\times n}$ is a symmetric PSD matrix, $f\in\Re^n$ is a constant linear term, $\{I_1,\ldots,I_k\}$ is a partitioning of $I=\{1,\ldots,n\}$, $S_{equ}$ and $S_{ineq}$ is a partitioning of $\{1,\ldots,m\}$ and $(b_1,\ldots,b_m)$ are given positive constants.

The solver implements a dual coordinate ascent algorithm which in each iteration updates two variables yilding nearly the maximal improvement of the objective. The QP tasks of this form appear e.g. when learning the Structured Output SVM or when implementing a generic Bundle Method forRisk Minimization.

QP with box constraints and a single linear equality constraint

$$\min_{x} \left [ \frac{1}{2}x^T H x + x^T f\right] \quad \mbox{suject to}\quad \begin{array}{l} x^T a = b \\ l_i \leq x_i \leq u_i\,, i\in \{1,\ldots,n\} \end{array} $$

where $x=(x_1,\ldots,x_n)\in\Re^n$ is the optimized vector, $H\in\Re^{n\times n}$ is a symmetric PSD matrix, $f\in\Re^n$ is a constant linear term, $a\in\Re^n$ is a constant vector with non-zero entries, $b\in\Re$ is a scalar, $(l_1,\ldots,l_n)\in(\Re\cup \{-\infty\})^n$ and $(u_1,\ldots,u_n)\in(\Re\cup\{\infty\})^n$ are lower and upper bounds, respectively.

The solver implements the dual coordinate ascent algorithm updating two variables in each iteration. It uses the maximalviolating pair strategy which selecting for update the variables most violating the Karush-Kuhn-Tucker conditions. This QP task appears e.g. when solving the two-class SVM classifier.

Download

2009-11-20 libqp-2009-11-20.zip

Installation to Matlab

After starting Matlab go to the folder libqp_root/matlab and compile MEX files by:


    cd libqp_root/matlab
    libqp_compile

Now you can start using libqp_splx and libqp_gsmo solvers located in libqp_root/matlab. To make the functions visible from Matlab you need to add them to path


    addpath('libqp_root/matlab');

which can go permanently to your startup.m file. To test the solvers run scripts


  libqp_splx_test
  libqp_gsmo_test

Stand alone example application

There is a simple C example using the libqp solvers to minimize QP tasks defined in a text file. To compile the example you need to go to the folder libqp_root/examples and issue make:


      cd libqp_root/examples
      make

Now you can run test script


    ./run_test