\(\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}} }\)
qp_box
abs_normal: Solve a Quadratic Program With Box Constraints
Syntax
qp_box
(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
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\).
Lower c
This is the value of the inequality constraint function at \(x = 0\).
Upper C
This is a row-major representation of thee the inequality constraint matrix \(C\).
Lower g
This is the gradient of the objective function.
Upper 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.,
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
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
Example
The file qp_box.cpp contains an example and test of
qp_box
.