Quadratic Programming (QP)
The application solves the quadratic programming problems with linear constraints and bound constraints: \[ \begin{aligned} \min_{x\in\mathbf{R}^n} \quad & \frac{1}{2}x^TQx+c^Tx \\ \text{s.t.}\quad & Ax\leqslant b \\ & A_\mathrm{eq}x = b_\mathrm{eq} \\ & l\leqslant x\leqslant u \end{aligned} \] where $x\in\mathbf{R}^n$ are independent variables while $c\in\mathbf{R}^n$, $b\in\mathbf{R}^m$, $b_\mathrm{eq}\in\mathbf{R}^q$, $l\in\mathbf{R}^n$, $u\in\mathbf{R}^n$, $Q\in\mathbf{R}^{n\times n}$, $A\in\mathbf{R}^{m\times n}$, $A_\mathrm{eq}\in\mathbf{R}^{q\times n}$ are given. In this problem $Q$ is a generally symmetric matrix, not neccessary positive semidefinite.
Here is an example of quadratic programming problems, finding the minimum of \[f(x_1,x_2)=3x_1^2 +2x_1x_2+x_2^2+x_1+6x_2\] under the condition $2x_1+3x_2\geqslant 4$.
To be solved by this calculator, the problem must be written in the form above. From $f(x_1,x_2)$ we get \[ Q=\left(\begin{array}{cc} 6 & 2 \\ 2 & 2 \end{array} \right) \quad\text{and}\quad c = \left(\begin{array}{c} 1 \\ 6 \end{array} \right) \] the constraint is rewritten as $-2x_1-3x_2\leqslant -4$ or in matrix form \[ \left[ \begin{array}{cc} -2 & -3 \end{array} \right] \left[ \begin{array}{c} x_1 \\ x_2 \end{array} \right] \leqslant \left[ \begin{array}{c} -4 \end{array} \right] \] this problem has no equality constraint and no lower/upper bounds of $x$.
Input Data
-
The input for $Q$ and $c$, enter data for $n\times (n+1)$ matrix, where $n$ is the number
of variables, the first $n$ columns are entries of $Q$ and the last column is vector $c$.
Due to the symmetry of $Q$, only entries on the diagonal and upper triangular are used by the
calculator. From the example, $Q$ and $c$ are entered as
6 2 1 2 2 6
- Do the same as $Q$, $c$ for entering input data for $A$, $b$ and $A_\mathrm{eq}$, $b_\mathrm{eq}$. Leave it blank if no data.
- The input for $l$ and $u$ is the same format as used in Constrained Optimization. If no data provided, the application assigns $l_i=-10$ and $u_i=10$ for $i=1,\ldots, n$.
- The input for $x_0$ is the same format as used in Constrained Optimization. If no data provided, the application assigns $x_{0i}=\text{random(0,1)}$ for $i=1,\ldots, n$.