2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do you know about vector $c$? And $q$? Note that the QP is non-convex if $q < 0$. $\endgroup$ – Rodrigo de Azevedo Sep 27 '17 at 17:01
  • $\begingroup$ You might find this paper on non negative quadratic programming useful (looks at a general positive definite $Q$) $\endgroup$ – nemo Sep 27 '17 at 18:37
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ can you please help me with the following problem? math.stackexchange.com/questions/2550644/… I like what you did here, and it seems that you know a lot about these. If you could take a look and help out, I would be forever in your debt! Thank you. $\endgroup$ – ALannister Dec 4 '17 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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