abs_normal: Solve a Quadratic Program With Box Constraints

Syntax
ok = qp_box(      level, a, b, c, C, g, G, epsilon, maxitr, xin, xout )

Prototype

template <class Vector>
bool qp_box(
size_t        level   ,
const Vector& a       ,
const Vector& b       ,
const Vector& c       ,
const Vector& C       ,
const Vector& g       ,
const Vector& G       ,
double        epsilon ,
size_t        maxitr  ,
const Vector& xin     ,
Vector&       xout    )

Source
This following is a link to the source code for this example: qp_box.hpp .

Purpose
This routine could be used to create a version of abs_min_linear that solved quadratic programs (instead of linear programs).

Problem
We are given $a \in \B{R}^n$, $b \in \B{R}^n$, $c \in \B{R}^m$, $C \in \B{R}^{m \times n}$, $g \in \B{R}^n$, $G \in \B{R}^{n \times n}$, where $G$ is positive semi-definite. This routine solves the problem $$\begin{array}{rl} \R{minimize} & \frac{1}{2} x^T G x + g^T x \; \R{w.r.t} \; x \in \B{R}^n \\ \R{subject \; to} & C x + c \leq 0 \; \R{and} \; a \leq x \leq b \end{array}$$ The matrix $G + C^T C$ must be positive definite on components of the vector $x$ where the lower limit minus infinity and the upper limit is plus infinity; see a and b below.

Vector
The type Vector is a simple vector with elements of type double.

level
This value is less that or equal two. If level == 0 , no tracing is printed. If level >= 1 , a trace of the qp_box operations is printed. If level == 2 , a trace of the qp_interior sub-problem is printed.

a
This is the vector of lower limits for $x$ in the problem. If a[j] is minus infinity, there is no lower limit for $x_j$.

b
This is the vector of upper limits for $x$ in the problem. If a[j] is plus infinity, there is no upper limit for $x_j$.

c
This is the value of the inequality constraint function at $x = 0$.

C
This is a row-major representation of thee the inequality constraint matrix $C$.

g
This is the gradient of the objective function.

G
This is a row-major representation of the Hessian of the objective function. For $j = 0 , \ldots , n-1$, $- \infty < a_j$ or $b_j < + \infty$ or $G_{j,j} > 0.0$.

epsilon
This argument is the convergence criteria; see KKT conditions below. It must be greater than zero.

maxitr
This is the maximum number of qp_interior iterations to try before giving up on convergence.

xin
This argument has size n and is the initial point for the algorithm. It must strictly satisfy the constraints; i.e.,       a < xin,  xin < b,  C * xin - c < 0 
xout
This argument has size is n and the input value of its elements does no matter. Upon return it is the primal variables $x$ corresponding to the problem solution.

ok
If the return value ok is true, convergence is obtained; i.e., $$| F ( x , y_a, s_a, y_b, s_b, y_c, s_c ) |_\infty < \varepsilon$$ where $|v|_\infty$ is the infinity norm of the vector $v$, $\varepsilon$ is epsilon , $x$ is equal to xout , $y_a, s_a \in \B{R}_+^n$, $y_b, s_b \in \B{R}_+^n$ and $y_c, s_c \in \B{R}_+^m$.

KKT Conditions
Give a vector $v \in \B{R}^m$ we define $D(v) \in \B{R}^{m \times m}$ as the corresponding diagonal matrix. We also define $1_m \in \B{R}^m$ as the vector of ones. We define $$F ( x , y_a, s_a, y_b, s_b, y_c, s_c ) = \left( \begin{array}{c} g + G x - y_a + y_b + y_c^T C \\ a + s_a - x \\ x + s_b - b \\ C x + c + s_c \\ D(s_a) D(y_a) 1_m \\ D(s_b) D(y_b) 1_m \\ D(s_c) D(y_c) 1_m \end{array} \right)$$ where $x \in \B{R}^n$, $y_a, s_a \in \B{R}_+^n$, $y_b, s_b \in \B{R}_+^n$ and $y_c, s_c \in \B{R}_+^m$. The KKT conditions for a solution of this problem is $$F ( x , y_a, s_a, y_b, s_b, y_c, s_c ) = 0$$

Example
The file qp_box.cpp contains an example and test of qp_box. It returns true if the test passes and false otherwise.
Input File: example/abs_normal/qp_box.hpp