abs_normal: Solve a Quadratic Program With Box Constraints

Loading [MathJax]/extensions/TeX/newcommand.js

$\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}} }$ This is cppad-20221105 documentation. Here is a link to its current documentation . 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.

Input File: example/abs_normal/qp_box.hpp