Prev Next

@(@\newcommand{\W}[1]{ \; #1 \; } \newcommand{\R}[1]{ {\rm #1} } \newcommand{\B}[1]{ {\bf #1} } \newcommand{\D}[2]{ \frac{\partial #1}{\partial #2} } \newcommand{\DD}[3]{ \frac{\partial^2 #1}{\partial #2 \partial #3} } \newcommand{\Dpow}[2]{ \frac{\partial^{#1}}{\partial {#2}^{#1}} } \newcommand{\dpow}[2]{ \frac{ {\rm d}^{#1}}{{\rm d}\, {#2}^{#1}} }@)@
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