5.3.1. Modeling for Quadratic Programming

Quadratic Programming (QP) problems can be described by using the following mathematical model:

\[\begin{split}\min \quad&-c^f + c^Tx + \frac{1}{2}x^T Q x \\ \mbox{s.t.} \quad&l^r \leq Ax \leq u^r, \\ & l^c \leq x \leq u^c,\end{split}\]
In the preceding model:

  • \(x \in \mathbb{R}^{n}\) is a decision variable.

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

  • \(c^f \in \mathbb{R}\) is a constant in the target function.

  • \(c \in \mathbb{R}^{n}\) is a coefficient in the target function.

  • \(Q \in \mathbb{R}^{n\times n}\) is a quadratic coefficient in thet target function.

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

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

The procedure of using MindOpt is as follows:

  1. Create an optimization model.

  2. Input an optimization problem and set algorithm parameters.

  3. Solve the problem and obtain the solution.

Note

MindOpt stores only non-zero elements in the constraint matrix \(A\) and the quadratic matrix \(Q\). Therefore, you only need to input the row/column index and non-zero value of each non-zero element in the constraint matrix.

5.3.1.1. Examples of quadratic programming problems

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 following part describes how to use MindOpt to build a model and solve the optimization problem. Quadratic programming differs from linear programming in the input of elements into the quadratic matrix. For the modeling of linear constraints, you can input non-zero elements into the constraint matrix in two ways:

  1. By row (constraint)

  2. By column (variable)

For more information, see Modeling for linear programming. To ensure the symmetry of the quadratic coefficient matrix \(Q\), you only need to input the triangle part, which will be multiplied by 1/2 inside the solver.

Examples are provided for different programming languages.