0
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 3 at 5:42
  • $\begingroup$ Even in that case, I would like to see how this is possible. Any references or tips? $\endgroup$
    – Marion
    Jun 3 at 8:58
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 3 at 9:02
  • $\begingroup$ 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. $\endgroup$
    – Marion
    Jun 3 at 9:17
2
$\begingroup$

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))
$\endgroup$
12
  • $\begingroup$ 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...". $\endgroup$
    – Marion
    Jun 3 at 11:42
  • 1
    $\begingroup$ 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$ $\endgroup$ Jun 3 at 12:14
  • 1
    $\begingroup$ it's just a notation for the socp-cone $||e|| \leq e_0$ $\endgroup$ Jun 14 at 9:25
  • 1
    $\begingroup$ If solution is unique, yes. $\endgroup$ Jun 14 at 14:44
  • 1
    $\begingroup$ Minimizing $||x||^2$ is the same thing as minimizing $||x||$ which is the same thing as minimizing $t$ with the constraints $||x||\leq t$. $\endgroup$ Jun 15 at 14:05

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.