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 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.
Input File: example/abs_normal/qp_box.hpp
