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?



mixed semi definite and second order programming complexity order
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.


