5
$\begingroup$

I am new to this topic and am looking at an example I can't figure out. Can someone please help explain how this example creates the matrices used in the solver? Thanks!

This is the PROBLEM

Minimize $2x_1^2 + x_2^2 + x_1x_2 + x_1 + x_2,\quad$subject to:

$x_1 \geq 0$
$x_2 \geq 0$
$x_1 + x_2 = 1$

ANSWER:
Matrix Form for solver:

Q =
[4.0, 1.0]
[1.0, 2.0]

p =
[1.0]
[1.0]

G =
[-1.0, 0.0]
[0.0, -1.0]

h =
[0.0]
[0.0]

A = [1.0, 1.0]

b = [1.0]

result = solve.qp(Q, p, G, h, A, b)

1 Answers 1

2

It looks like you're trying to solve a quadratic program of the form:

$ \begin{aligned} & \underset{x}{\text{minimize}} & & \frac{1}{2} x^T Q x + p^T x \\ & \text{subject to} & & Gx \preceq h \\ &&& Ax = b \end{aligned} $ Expand the objective function where $x = \left [x_1 \quad x_2 \right ]^T$ and you will see that

$\frac{1}{2} \begin{bmatrix} x_1 & x_2 \end{bmatrix}\begin{bmatrix} 4 & 1 \\ 1 & 2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} + \begin{bmatrix} 1 & 1 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = (2x_1^2 + x_2^2 + x_1x_2) + (x_1 + x_2) $.

Similarly, expand $Gx \preceq h$ and $Ax = b$ and you'll see that they are equivalent to $x_1,x_2 \ge 0$ and $x_1+x_2 = 1$ respectively.

  • 1
    Thank you! - your answer is elegant and extremely helpful2012-11-06