5.3.1. Modeling for Quadratic Programming

A linear-constrained quadratic program (refered to as QP for simplicity) can be represented as follows:

\[\begin{split}\begin{matrix} \min & &-c^f &+& c^Tx &+& \frac{1}{2}x^T Q x \\ \mbox{s.t.} & &l^r& \leq& Ax &\leq &u^r \\ & & l^c &\leq& x &\leq& u^c \end{matrix}\end{split}\]
where

  • \(x \in \mathbb{R}^{n}\) is the decision variable,

  • \(l^c \in \mathbb{R}^{n}\) and \(u^c \in \mathbb{R}^{n}\) are the lower and upper bounds of \(x\),

  • \(c^f \in \mathbb{R}\) is the constant term in the objective function,

  • \(c \in \mathbb{R}^{n}\) is the linear coefficient in the objective function,

  • \(Q \in \mathbb{R}^{n\times n}\) is the quadratic coefficient matrix in the objective function,

  • \(A \in \mathbb{R}^{m \times n}\) is the constraint matrix,

  • \(l^r \in \mathbb{R}^{m}\) and \(u^r \in \mathbb{R}^{m}\) are the lower and upper bounds of the constraints.

The steps to use MindOpt are as follows:

  1. Create an optimization model;

  2. Input the optimization problem and set algorithm parameters;

  3. Solve the optimization problem and retrieve the optimal solutions.

Note

MindOpt only stores the non-zero elements in the constraint matrices A and \(Q\). Therefore, we only need to input the positions and the values of the non-zero elements during the modeling process.

5.3.1.1. Example of Quadratic Programming

We consider the following Quadratic Programming problem:

\[\begin{split}\begin{matrix} \min & & 1 x_0 & + & 1 x_1 & + & 1 x_2 & + & 1 x_3 \\ & + 1/2 [ & x_0^2 & + & x_1^2 & + & x_2^2 & + & x_3^2 & + & x_0 x_1 & ] \\ \mbox{s.t.} & & 1 x_0 & + & 1 x_1 & + & 2 x_2 & + & 3 x_3 & \geq & 1 \\ & & 1 x_0 & & & - & 1 x_2 & + & 6 x_3 & = & 1 \end{matrix}\end{split}\]
\[\begin{split}\begin{matrix} 0 & \leq & x_0 & \leq & 10 \\ 0 & \leq & x_1 & \leq & \infty \\ 0 & \leq & x_2 & \leq & \infty \\ 0 & \leq & x_3 & \leq & \infty \end{matrix}\end{split}\]

The only difference between the above quadratic programming and linear programming is the input of the quadratic item matrix \(Q\). To ensure the symmetry of \(Q\), users are required to input just its lower triangular part.

We will provide example codes illustrating how MindOpt models and solves the above QP problem in different programming languages.