A specific quadratic program with non-negativity constraints

1.2k Views Asked by At

I want to solve the following quadratic program in $x \in \mathbb R^{n}$

$$\begin{array}{ll} \text{minimize} & \frac 12 x^\top Q \, x + c^\top x\\ \text{subject to} & x \geq 0_n\end{array}$$

where $Q = q I_n$ and $q>0$. I know we can solve a general QP using Lagrangian multipliers and similar methods. However, I was wondering if $Q$ being a multiple of the identity matrix does simplify the problem. Is there a closed-form solution?

1

There are 1 best solutions below

2
On BEST ANSWER

Maybe write the formula as this form?\begin{align} \frac{1}{2}x^\top Q x+c^\top x= & \frac{q}{2}\left( \sum_{i=1}^{n}\left(x_i^2+\frac{c_i}{q}x_i\right)\right)\\ {}= & \frac{q}{2}\left( \sum_{i=1}^{n}\left(x_i+\frac{c_i}{2q}\right)^2-\frac{c_i^2}{4q^2}\right) \end{align} So it depends on $c=(c_1,\dots,c_n)$. Assume $q>0$, if ${c_i}<0$, then $x_i=-\frac{c_i}{q}$; if $c_i>0$, then $x_i=0$.