2
$\begingroup$

Consider the following mixed semi definite and second order programming:

$\begin{array}{l} \mathop {{\rm{min}}}\limits_{\bf{X}} \,{\rm{Tr}}\left( {{\bf{XA}}} \right)\\ {\rm{s}}{\rm{.t:}}\, & {\rm{Tr}}\left( {{\bf{XA'}}} \right) + \left\| {{\rm{vec}}{{\left( {\bf{X}} \right)}^H}{\bf{A''}}} \right\| \ge a\\ & {\bf{X}} \ge {\bf{0}} \end{array}$

where ${\bf{A}}$,${{\bf{A'}}}$ and ${{\bf{A''}}}$ are $M \times M$ positive semi definite matrices, $a$ is a positive constant. $vec(.)$ is the stack column operator. By assumption of feasibility of the above problem, how can I obtain the order of complexity of the mixed semi definite and second order optimization problem?

$\endgroup$
  • 1
    $\begingroup$ What do you mean by order of complexity? In any case, it might help you to write the norm constraint in (second order) conic form, which will lead to only linear equality constraints + semidefinite + second order cone constraints. $\endgroup$ – Cristóbal Guzmán Jul 22 '14 at 20:20
  • $\begingroup$ Thank you very much for your comment. To clarity, consider the following standard semi definite programming: [\begin{array}{l} \mathop {{\rm{min}}}\limits_{\bf{X}} & {\rm{Tr}}\left( {{\bf{XA}}} \right)\\ {\rm{s}}{\rm{.t:}} & {\rm{Tr}}\left( {{\bf{XA'}}} \right) = a\\ & {\bf{X}} \ge {\bf{0}} \end{array}] the worst case complexity of the above problem is given by ${\cal O}\left( {\sqrt M \log \left( M\right)\log \left( {M/\varepsilon } \right)} \right)$. I want to know how can I calculate the complexity of mixed semi definite and second order programming. $\endgroup$ – user51780 Jul 23 '14 at 7:52
  • $\begingroup$ I think you will see it once you write your problem in standard form (meaning that you convert the norm into a second-order cone constraint). I can write it down later if you want, but let me warn you that the complexity upper bound you wrote above should also depend on $A$, $A^{\prime}$. $\endgroup$ – Cristóbal Guzmán Jul 23 '14 at 16:40
2
$\begingroup$

It took me some time, but I hope it still helps. Coming back to your problem I realized that the norm constraint is not convex (you should have the opposite inequality for convexity).

Assuming you have the opposite inequality, $ Tr(XA^{\prime})+\|vec(X)^HA\|\leq a$, you can write the problem in standard form:

\begin{eqnarray*} \min & Tr(XA)+t \\ \mbox{s.t.} & Tr(X A^{\prime})+t+s &= a \\ & vec(X)^HA^{\prime\prime} &= z \\ & s &\geq 0 \\ & (z,t)&\in L^{M+1}\\ & X &\succeq 0 \end{eqnarray*}

where $L^{M+1}$ is the Lorentz cone in $M+1$ variables. The nice thing about barrier functions is that they (and their complexity) are additive (see http://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf, page 276), so the complexity of interior point methods would be the sum of the barrier parameter of the positive real line + the barrie parameter of the PSD cone + the barrier parameter of the Lorentz cone (and the square root of that parameter is what comes in the running time of the IPM).

Of course, all this provided you have a convex program.

$\endgroup$
  • $\begingroup$ thank you very much. would you please explain why you add variable $t$ in the objective function. $\endgroup$ – user51780 Jul 27 '14 at 6:42
  • $\begingroup$ The previous comment was about the slack variable $s$, so I add now the explanation for t. Note that by the Lorentz cone constraint $t\geq \|z\|=\|vec(X)^HA^{\prime\prime}\|$. Also observe that the other constraint that involves $t$ is (by eliminating the slack $s$): $t\leq a-Tr(XA^{\prime})$, so it does not interfere in the minimization of $t$. This means that when we minimize over $t$ (the other variables being fixed, except for $s$), the Lorentz cone inequality is tight, i.e. $t=\|z\|=\|vec(X)^HA^{\prime\prime}\|$, which is what we want. $\endgroup$ – Cristóbal Guzmán Jul 29 '14 at 16:38
  • $\begingroup$ Did I answer your question? $\endgroup$ – Cristóbal Guzmán Aug 6 '14 at 21:59
  • $\begingroup$ Thank you for your answer to my question. I am convinced about the reason of adding the slack variable $t$ on the constraints, however I'm confused why you add the slack variable $t$ on the objective function.Would you please explain more about it? $\endgroup$ – user51780 Aug 8 '14 at 6:39
  • 1
    $\begingroup$ You have to enforce this variable to be minimized, otherwise it would not take the value $\|z\|$. It is also important that the variable $t$ is not tied to other equations, otherwise it might not satisfy the multiple equality constraints with the value $\|z\|$. If I answered your question, please mark check on my answer. $\endgroup$ – Cristóbal Guzmán Aug 8 '14 at 17:03

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.