5
$\begingroup$

I have tried to convert the following constraint into SOCP form but can't figure it out. My issue is that whenever I create the norm, the other side has to be square rooted which invalidates the SOCP form.

The directional parameters ${\boldsymbol w}\in\Bbb R^d$ satisfies the following shaping constraint: $$\boldsymbol w^\top\boldsymbol\Sigma\boldsymbol w+\boldsymbol c^\top\boldsymbol w\le1,$$ where $\boldsymbol\Sigma\in\Bbb R^{d\times d}$ is a given symmetric, positive definite matrix and $\boldsymbol c\in\Bbb R^d$ is a given vector.

$\endgroup$
1
  • $\begingroup$ Btw how do you know Sigma is PSD? Maybe because you know a matrix H such that Sigma=HH'? $\endgroup$ May 11, 2022 at 7:00

2 Answers 2

7
$\begingroup$

For all things convex, Mosek's modeling cookbook and conic modeling cheatsheet have you covered.

In your case, see the section on convex quadratic sets.

$\endgroup$
2
$\begingroup$

Since $\boldsymbol\Sigma$ is PSD, there exists $\boldsymbol Q$ s.t. $\boldsymbol Q^\top\boldsymbol Q=\boldsymbol \Sigma$ (by Cholesky, or eigendecomposition).

Then $\boldsymbol w^\top\boldsymbol \Sigma\boldsymbol w =\boldsymbol w^\top\boldsymbol Q^\top\boldsymbol Q\boldsymbol w = \|\boldsymbol Q\boldsymbol w\|_2^2.$

Then introduce new variable $y$ as epigraph of $\|\boldsymbol Q\boldsymbol w\|$ as follows:

\begin{align}y+\boldsymbol c^\top\boldsymbol w&=1\tag{linear constraint}\\\|\boldsymbol Q\boldsymbol w\|_2^2&\le y\tag{rotated quadratic cone constraint}\end{align}

As @mtanneau posted, these modeling tricks(?) are well-explained in the MOSEK tutorial.

If you use MOSEK, you can just directly use rotated quadratic cone to model second constraint. If you want to convert into second order conic constraints,

\begin{align}&\|\boldsymbol{Qw}\|_{2}^{2} \leq y \\\iff&(\boldsymbol{Qw})^\intercal (\boldsymbol{Qw}) \leq y \\ \iff& (\boldsymbol{Qw})^\intercal (\boldsymbol{Qw})+\frac{(y-1)^2}{4} \leq \frac{(y+1)^2}{4}\\ \iff& \left\|\begin{pmatrix}\boldsymbol{Qw}\\ \frac{y-1}{2} \end{pmatrix}\right\|_{2} \leq \frac{y+1}{2}\end{align}

Hope this is what you're looking for.
*Converting quadratic constraint into soc constraint is well-known tricks, you can find in https://www2.isye.gatech.edu/~nemirovs/LMCOLN2021WithSol.pdf

$\endgroup$
7
  • 2
    $\begingroup$ Shouldn't the 2-norm of $Qw$ be squared? $\endgroup$
    – prubin
    May 10, 2022 at 15:24
  • $\begingroup$ @prubin Sure. I had a mistake. Thanks. $\endgroup$
    – Seok
    May 11, 2022 at 3:56
  • 1
    $\begingroup$ I suggest you change $y+c'w\le1$ to $y+c'w = 1$. That is correct and in theory more efficient. $\endgroup$ May 11, 2022 at 6:56
  • $\begingroup$ Oh, I see. I didnt realize making it linear equality is better until now. Thank you :) BTW, can you plz explain or give some references about that efficiency? Maybe the linear equality can project onto the smaller search space..? $\endgroup$
    – Seok
    May 11, 2022 at 7:42
  • 2
    $\begingroup$ It follows from the complexity analysis of interior-point methods i.e. the barrier parameter will be smaller with equality. $\endgroup$ May 11, 2022 at 10:06

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.