How to solve non-negativity-constrained quadratic programs?

118 Views Asked by At

$$\min_{x_1,x_2,x_3 \geq 0} \quad 2x^2_1+3x^2_2+4x^2_3+2x_1x_2 -2x_1x_3 -8x_1-4x_2-2x_3 $$

I tried to re range the problem to matrix form and got

$$ \min_{x \geq 0_3} \quad x^T Ax + 2b^Tx$$

where

$$A = \begin{bmatrix} 2 & 1 & -1\\ 1 & 3 & 0 \\ -1 & 0 & 4 \end{bmatrix}, \qquad b = \begin{bmatrix} -4 \\ -2 \\ -1\\ \end{bmatrix}$$

I think $A$ is positive semidefinite matrix thus this becomes convex optimization problem. Does it have analytical solution? How to solve it?

computing the gradient of f(x) will give $$\nabla f=(A^t + A)x + b$$ $$\nabla f(x)= \begin{bmatrix} 4 & 2 & -2 \\ 2 & 6 & 0 \\ -2 & 0 & 8 \end{bmatrix}x +\begin{bmatrix} -4 \\ -2 \\ -1\\ \end{bmatrix}$$

Since gradient must be equal to 0 at optimal point we have the following optimality condition.

$$\frac{df}{dx_i}(x^*) = \begin{cases} =0 , x^*_i >0 \\ \geq0 , x^*_i=0 \end{cases}$$

How can I use above mentioned function to find $$x^* = ?$$

1

There are 1 best solutions below

0
On BEST ANSWER

If you let $f(x)=x^T Ax + 2b^Tx$, you see that $$\min_{x} \quad f(x)$$ has solution $u= (2.5294118, -0.1764706, 0.8823529)$ with is the solution of $$\nabla f(x)=2Ax+2b=0.\tag{1}$$

This means that the solution to the minimization problem $$\min_{x\geq 0} \quad f(x)$$ is not in the interior of the feasible region. This means that you can find $f_{min}$ on $x_1=0$ or on $x_2=0$ or $x_3=0$ or in $\mathbb{R}^3$, as pointed out in comments.

In this problem, you can check that $x_2=0$ gives the answer. Then you remove the second column and the second row of $A$, the second coordinate of $x$ and the second coordinate of $b$, in $(1)$ and solve the equation $$\begin{bmatrix} 2 & -1\\ -1 &4 \end{bmatrix}\begin{bmatrix} x_1\\ x_3 \end{bmatrix} = \begin{bmatrix} 4 \\ 1 \end{bmatrix}$$ to find $x_1=17/7$ and $x_3=6/7$.

This is a particular case of Non-negative least squares, which has a general algorithm to solve.

You can find some related discussion searching for "\( x^T Ax + 2b^Tx\) " on SearchOnMath.