programación mixta semidefinida y de segundo orden complejidad orden

Question

Consideremos la siguiente programación mixta semidefinida y de segundo orden:

$\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}$

donde ${\bf{A}}$ , ${{\bf{A'}}}$ y ${{\bf{A''}}}$ son $M \times M$ matrices semidefinidas positivas, $a$ es una constante positiva. $vec(.)$ es el operador de columna de pila. Suponiendo la viabilidad del problema anterior, ¿cómo puedo obtener el orden de complejidad del problema de optimización mixto semidefinido y de segundo orden?

Answer 1

Me ha llevado tiempo, pero espero que siga siendo útil. Volviendo a tu problema me di cuenta de que la restricción de la norma no es convexa (deberías tener la desigualdad opuesta para la convexidad).

Suponiendo que tengas la desigualdad opuesta, $Tr(XA^{\prime})+\|vec(X)^HA\|\leq a$ se puede escribir el problema en forma estándar:

$$\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*}$$

donde $L^{M+1}$ es el cono de Lorentz en $M+1$ variables. Lo bueno de las funciones barrera es que (y su complejidad) son aditivas (véase http://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf , página 276), por lo que la complejidad de los métodos de puntos interiores sería la suma del parámetro barrera de la recta real positiva + el parámetro barrie del cono PSD + el parámetro barrera del cono de Lorentz (y la raíz cuadrada de ese parámetro es lo que entra en el tiempo de ejecución del MIP).

Por supuesto, todo esto siempre que tengas un programa convexo.