Solving Quadratic Programming Problems using Octave

In this post I’m going to show you how to solve quadratic programming problems using Octave. Octave is an alternative to Matlab, with an advantage of being free.

Suppose we want to solve a Quadratic Programming problem with standard form like this:

\begin{align} \text{minimize  } & \frac{1}{2}x^THx+f^Tx \\\\ \text{subject to  } & Bx=b \\\\ & lb \le x \le ub \\\\ &a\_lb \le Ax \le a\_ub \end{align}

This standard form provides more flexible format, it allows the usage of lower and upper bound in inequality. So you don’t need to rewrite the constraints. In Octave, this problem can be resolved by using $qp()$ function. The function can accept less or more variable as input with the output of an array of 4 variables. You can tailor the input corresponding to your QP problem.

[x, z_min, info, lambda] = qp (x0, H)
[x, z_min, info, lambda] = qp (x0, H, f)
[x, z_min, info, lambda] = qp (x0, H, f, B, b)
[x, z_min, info, lambda] = qp (x0, H, f, B, b, lb, ub)
[x, z_min, info, lambda] = qp (x0, H, f, B, b, lb, ub, a_lb, A, a_ub)
[x, z_min, info, lambda] = qp (…, options)
 $x0$  An optional initial guess for $x$. To leave it empty, use $[]$ as its value.
 $x$  Vector that minimizes objective function subject to all bounds and linear constraints. $x$ can be a local minimum for nonconvex problems. For convex problems, $x$ is a global minimum.
 $z\_min$  Value of objective function at the solution $x$ (minimum), a double
$info$  An integer indicating the status of the solution.
$0$ : The problem is feasible and convex. Global solution found.
$1$ : The problem is not convex. Local solution found.
$2$ : The problem is not convex and unbounded.
$3$ : Maximum number of iterations reached.
$6$ : The problem is infeasible.
$lambda$  Structure containing the Lagrange multipliers at the solution $x$

Example

\begin{align} \text{minimize  } & f(x)  = \frac{1}{2}x_1^2+x_2^2-x_1x_2-2x_1-6x_2 \\\\ \text{subject to  } & 1\le x_1+x_2\le 2 \\\\ & -x_1+2x_2\le 2 \\\\ & 2x_1+x_2\le 3 \\\\ & 0\le x_1 \\\\ & 0\le x_2 \end{align}

Answer:

First, we have to convert our objective and constraint function into standard format using matrix notation.

\begin{align} \text{minimize  } & f(x)=\frac{1}{2} \begin{bmatrix}x_1\\x_2\\ \end{bmatrix} \begin{bmatrix}1&-1\\-1&2\\ \end{bmatrix} \begin{bmatrix}x_1&x_2\\ \end{bmatrix}+\begin{bmatrix}-2\\-6\\ \end{bmatrix} \begin{bmatrix}x_1&x_2\\ \end{bmatrix} \\\\ \text{subject to  } & \begin{bmatrix}1\\-Inf\\-Inf\\ \end{bmatrix}\le \begin{bmatrix}1&1\\-1&2\\2&1\\ \end{bmatrix} \begin{bmatrix}x_1\\x_2\\ \end{bmatrix} \le \begin{bmatrix}2\\2\\3\\ \end{bmatrix} \\\\ & \begin{bmatrix}0\\0\\ \end{bmatrix}\le \begin{bmatrix}x_1\\x_2\\ \end{bmatrix} \end{align}


>> H = [1 -1; -1 2]
>> f = [-2; -6]
>> A = [1 1; -1 2; 2 1]
>> a_lb = [1; -Inf; -Inf]
>> a_ub = [2; 2; 3]
>> lb = [0; 0]

>>[x, z_min, info, lambda] = qp ([], H, f, [], [], lb, [], a_lb, A, a_ub)
x =
     0.66667
     1.33333

z_min = -8.2222
info =
     scalar structure containing the fields:
     solveiter = 7
     info = 0

lambda =
     0.00000
     0.00000
     0.00000
     3.11111
     0.44444
     0.00000

Leave a Reply

Your email address will not be published. Required fields are marked *