Suppose we want to minimize a linear objective inside an ellipsoid that is,

$\min _x l^Tx$

such that $(x - \mu)^TA(x - \mu) \leq \beta ^2$.

Here, A is PSD and $\mu$ is a fixed vector. Can this be written as a SDP ?

  • $\begingroup$ Why should it? Since $A$ is PSD this is a convex quadratic program. By the way: Isn't there a closed form solution (using $A^{-1}$)? $\endgroup$ – Dirk Nov 26 '15 at 8:40
  • $\begingroup$ @Dirk: Indeed there is. Check answer below. $\endgroup$ – dohmatob Nov 26 '15 at 21:04

There is a closed-form expression for that value. Indeed, a straight-forward computation yields \begin{equation} \begin{split} \min_{\langle A(x-\mu),x-\mu\rangle \le \beta^2} \langle l, x\rangle &= \min_{\|v\|^2 \le \beta^2}\langle l, \mu + A^{-1/2}v\rangle = \langle l, \mu \rangle + \min_{\|v\| \le \beta}\langle A^{-1/2}l,v\rangle \\\\& = \langle l, \mu\rangle - \beta \|A^{-1/2}l\| = \langle l, \mu \rangle - \beta \sqrt{\langle A^{-1}l,l\rangle} \end{split} \end{equation}

| cite | improve this answer | |

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.