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?

Improve this question
$\endgroup$
3
  • 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
    Commented Jul 22, 2014 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
    Commented Jul 23, 2014 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
    Commented Jul 23, 2014 at 16:40

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ thank you very much. would you please explain why you add variable $t$ in the objective function. $\endgroup$
    – user51780
    Commented Jul 27, 2014 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
    Commented Jul 29, 2014 at 16:38
  • $\begingroup$ Did I answer your question? $\endgroup$
    – Cristóbal Guzmán
    Commented Aug 6, 2014 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
    Commented Aug 8, 2014 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
    Commented Aug 8, 2014 at 17:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .