Minimum of quadratic program

133 Views Asked by At

Given a symmetric matrix $A \in \mathbb{R}^{n \times n}$ and vectors $b \in \mathbb{R}^{n}$ and $c \in [0,\infty)^n$ is there a closed-form solution of the following quadratic program?

$$\begin{array}{ll} \text{minimize} & x^T A x + b^T x\\ \text{subject to} & c^T x = 1 \\ & x_{i} \ge 0\end{array}$$

Note that $A$ is not necessarily positive-definite.

If not, how can I solve this efficiently? Are there specific algorithms?

1

There are 1 best solutions below

2
On

Closed form under some hypothesis. Supposing $A$ invertible and also $\frac 12x^TA x+b^Tx,\ \text{s. t.}\ \ c^Tx=1$ (without the condition $x\ge 0$)

Considering the lagrangian

$$ L = \frac 12x^TA x+b^Tx-\lambda(c^Tx-1) $$

the stationary points are the solution for

$$ \cases{x^T A+b^T-\lambda c^T = 0\\ c^Tx - 1 = 0} $$

If $A$ is invertible

$$ x = \lambda A^{-T}c-A^{-T}b $$

substituting into the restriction

$$ \lambda c^TA^{-T}c-c^{T}A^{-T}b=1 $$

so

$$ \lambda = 1-\frac{c^{T}A^{-T}b}{c^TA^{-T}c} $$

and finally

$$ x = \left(1-\frac{c^{T}A^{-T}b}{c^TA^{-T}c}\right)A^{-T}c-A^{-T}b $$