Assume I have an quadratic program of the form: \begin{align*} \min&&&\|LA-B\|^2\\ \text{s.t.}&&& \text{Tr}A=1\\ &&&A \succeq 0 \end{align*} Here $$A,B,C,L$$ are all $$n\times n$$ real matrices, while the last term implies the constraint that $$A$$ is positive semi-definite. The question is how to bring this to the standard SDP form \begin{align*} \min&&&\langle C,X\rangle \\ \text{s.t.}&&&\langle Q_i, X \rangle = b_i \\ &&&X \succeq 0 \end{align*} where $$\langle C, X \rangle = \mathrm{Tr}(CX)$$. I understand that there is the complement trick by Schur but I struggle to apply it. Not sure how to do it.

More generally, how to bring a quadratic program (one whose objective is a quadratic function) to the standard conic SDP form?

• The important question is what your final goal is, as you wouldn't want to write the model in a simple SDP form in practice, but exploit the quadratic form and write as a mixed SDP/SOCP model, as most available solvers would exploit that. Jun 3, 2021 at 5:42
• Even in that case, I would like to see how this is possible. Any references or tips? Jun 3, 2021 at 8:58
• The constraint $t\geq x^2$ is equivalent to $\left[\begin{array}{cc}1&x\\ x&t\end{array}\right]\succeq0.$ From there you can reformulate the sum of squares in the objective. Like Johan mentioned, this is only of theoretical interest perhaps, showing that an SOCP is a special case of an SDP. Jun 3, 2021 at 9:02
• I am very confused as to what small $x$ is. Is the matrix quoted above supposed to represent $X$? At the moment I am indeed interested in the theory. But its not clear how to show this is SDP. Jun 3, 2021 at 9:17

If you want to work in a pure primal standard mixed SDP/SOCP cone you would have to introduce a new object $$e = (e_0,e) \in R\times R^{n\times n}$$ to represent the SOCP cone and replace the objective with $$e_0$$ and connect the two cones with the primal equalities $$e = \text{vec}(LA-B)$$ (which I will not write using inner products as that is absurdly low level).

\begin{align*} \min&&& e_0 \\ \text{s.t.}&&&\text{Tr} A =1 \\ &&&e = \text{vec}(LA-B)\\ &&&A \succeq_{SDP} 0, (e_0,e) \succeq_{SOCP} 0 \end{align*}

It is not certain you want to stay in a pure primal form (as you will be forced to introduce a large number of primal equalities), but instead interpret $$A$$ as a matrix defined by its elements as decision variables, and then skip also the definition of a cone variable for the SOCP and interpret everything from the dual side. The size of this model would be $$n(n+1)/2$$ (the number of variables defining elements of symmetric matrix $$A$$) while the size of the primal model would be $$n^2+1$$ (the number of equalities)

\begin{align*} \min&&& e_0 \\ \text{s.t.}&&& \text{Tr} A =1 \\ &&&A \succeq_{SDP} 0, \\ &&&(e_0,\text{vec}(LA-B)) \succeq_{SOCP} 0 \end{align*}

You typically do not do all this in practice (and we haven't even started with the really low-level boring stuff with inner products to define the equalities explicitly) but use modelling languages for this. The code would look something like this (here in YALMIP)

A = sdpvar(n)
optimize([A>=0, trace(A)==1],norm(L*A-B))

• It is not clear to me what the $e_0$ object is. Is this the variable appearing due to the Schur trick? P.S. my background is in differential topology so I am not familiar with the field and I am confused as to what you mean by "low level boring...". Jun 3, 2021 at 11:42
• Since $(e_0,e)$ in SOCP cone mean $||e||\leq e_0$ and $e$ is constrained to be equal to the elements in $LA−B$, $e_0$ will serve as an upper bound to $||LA−B||$. Low-level mean writing all the equalities in, e.g., $e=\text{vec}(LA−B)$ in the format $\langle Q^1_{i},A \rangle +\langle Q^2_{i},(e_0,e) \rangle = b_i$ Jun 3, 2021 at 12:14
• it's just a notation for the socp-cone $||e|| \leq e_0$ Jun 14, 2021 at 9:25
• If solution is unique, yes. Jun 14, 2021 at 14:44
• Minimizing $||x||^2$ is the same thing as minimizing $||x||$ which is the same thing as minimizing $t$ with the constraints $||x||\leq t$. Jun 15, 2021 at 14:05