Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
1  
Thank you! - your answer is elegant and extremely helpful –  Nick Nov 6 '12 at 21:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.