qp_box

View page source

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{split}\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}\end{split}\]

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.,

\[| 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

\[\begin{split}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)\end{split}\]

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 .