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$
$\endgroup$
2
-
$\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$– DirkCommented Nov 26, 2015 at 8:40
-
$\begingroup$ @Dirk: Indeed there is. Check answer below. $\endgroup$– dohmatobCommented Nov 26, 2015 at 21:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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}
