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}} }@)@

*ok* = qp_box(

*level*, *a*, *b*, *c*, *C*, *g*, *G*, *epsilon*, *maxitr*, *xin*, *xout*

)

template<classVector> boolqp_box( size_t level ,constVector& a ,constVector& b ,constVector& c ,constVector& C ,constVector& g ,constVector& G , double epsilon , size_t maxitr ,constVector& xin , Vector& xout )

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

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

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.
The type

*Vector*

is a
simple vector with elements of type `double`

.
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.
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
@)@.
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
@)@.
This is the value of the inequality constraint function at @(@ x = 0 @)@.

This is a row-major representation of thee the inequality constraint matrix @(@ C @)@.

This is the gradient of the objective function.

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 @)@.

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

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

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

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.
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
@)@.
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 @]@

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