La SDP como caso particular

La programa semidefinido (SDP) es el programa cónico que más usaremos en el curso: aparece al calcular entropías de una toma, el sesgo de juegos XOR y los niveles de la jerarquía NPA. Y no es un objeto nuevo — es lo que obtienes al poner $K = \mathrm{Pos}(\mathcal{X})$ en la maquinaria del artículo anterior.

Elegir el cono

Tomamos $\mathcal{V} = \mathrm{Herm}(\mathcal{X})$ , el espacio real de operadores Hermíticos, y como cono el de los operador semidefinido positivos:

K = \mathrm{Pos}(\mathcal{X}).

La restricción $x \in K$ se vuelve $X \succeq 0$ , y el objetivo lineal $\langle A, X\rangle = \mathrm{Tr}(A X)$ con $A$ Hermítico. La restricción afín $\Phi(X) = B$ usa un mapa canal cuántico que preserva hermiticidad. Así queda el primal:

\begin{array}{ll} \text{maximizar} & \langle A, X\rangle \\[2pt] \text{sujeto a} & \Phi(X) = B, \\[2pt] & X \succeq 0. \end{array}

El dual también es una SDP

Aquí es donde la autodualidad paga. En el dual cónico general aparece $\Phi^{*}(Y) - A \in K^{*}$ . Pero $\mathrm{Pos}(\mathcal{X})$ es autodual, así que $K^{*} = \mathrm{Pos}(\mathcal{X})$ y la condición se lee $\Phi^{*}(Y) - A \succeq 0$ , es decir $\Phi^{*}(Y) \succeq A$ :

\begin{array}{ll} \text{minimizar} & \langle B, Y\rangle \\[2pt] \text{sujeto a} & \Phi^{*}(Y) \succeq A. \end{array}

El dual de una SDP es, de nuevo, una SDP. Esa clausura es la razón por la que la programación semidefinida es tan cómoda: puedes pasar del primal al dual y quedarte siempre en la misma familia de problemas. La dualidad débil del artículo anterior se traduce sin cambios en $\langle A, X\rangle \le \langle B, Y\rangle$ .

La región factible: el espectraedro

¿Qué aspecto tiene el conjunto de puntos factibles de una SDP? Cuando la matriz depende afínmente de unas variables, el conjunto donde es semidefinida positiva se llama espectraedro. Es siempre convexo, y su frontera es donde la matriz pierde rango — donde $\det = 0$ y aparece un autovalor nulo.

Abajo, un ejemplo mínimo en dos variables: $M(x,y) = \left(\begin{smallmatrix} 2+x & y \\ y & 1-\tfrac{x}{2}\end{smallmatrix}\right) \succeq 0$ . La condición de positividad equivale a $\tfrac{x^2}{4} + \tfrac{y^2}{2} \le 1$ : una elipse. Maximizamos un objetivo lineal $\cos\theta\, x + \sin\theta\, y$ sobre ella; gira la dirección y observa dónde cae el óptimo:

Una SDP: objetivo lineal sobre un espectraedro

Región factible M(x,y) ⪰ 0 (el elipse azul) · objetivo c · óptimo x* = (0.00, 0.00), valor 0.000

El óptimo siempre cae en el borde, donde det M = 0: la matriz es semidefinida pero singular.

Dirección del objetivo 35°

El óptimo siempre se apoya en el borde del espectraedro, exactamente donde $M(x,y)$ es semidefinida pero singular (un autovalor se anula). Esa observación —qué restricción se vuelve «activa» en el óptimo— es la semilla de la holgura complementaria que veremos a continuación.

Ejemplos resueltos

Ejemplo resuelto 1 · Maximizar x sobre el espectraedro

Problema. Sobre la región $\tfrac{x^2}{4} + \tfrac{y^2}{2} \le 1$ (la SDP $M(x,y) \succeq 0$ de arriba), maximiza el objetivo $x$ —es decir, $\theta = 0$ , $c = (1,0)$ .

Solución. El mayor $x$ compatible con la elipse se logra con $y = 0$ , lo que deja $\tfrac{x^2}{4} \le 1$ , o sea $x \le 2$ . El óptimo es $(x^{*}, y^{*}) = (2, 0)$ , con valor $2$ .

Ver la matriz singular. Evaluando en el óptimo,

M(2,0) = \begin{pmatrix} 2+2 & 0 \\ 0 & 1 - 1 \end{pmatrix} = \begin{pmatrix} 4 & 0 \\ 0 & 0 \end{pmatrix}.

Sus autovalores son $4$ y $0$ : sigue siendo semidefinida positiva, pero singular ( $\det M = 0$ ). El óptimo se apoya justo donde un autovalor toca el cero — el borde del espectraedro.

Ejemplo resuelto 2 · Una dirección diagonal

Problema. Maximiza $x + y$ sobre la misma elipse ( $c = (1,1)$ ).

Solución. Para $\tfrac{x^2}{A} + \tfrac{y^2}{B} \le 1$ con $A = 4$ , $B = 2$ , el máximo de $c_1 x + c_2 y$ vale $\sqrt{A c_1^2 + B c_2^2}$ y se alcanza en $(x^{*}, y^{*}) = \tfrac{1}{\sqrt{A c_1^2 + B c_2^2}}(A c_1,\ B c_2)$ . Con $c = (1,1)$ :

\text{valor} = \sqrt{4 + 2} = \sqrt{6} \approx 2.449, \qquad (x^{*}, y^{*}) = \tfrac{1}{\sqrt 6}(4, 2) \approx (1.633,\ 0.816).

Comprobación de factibilidad. $\tfrac{x^{*2}}{4} + \tfrac{y^{*2}}{2} = \tfrac{16/6}{4} + \tfrac{4/6}{2} = \tfrac{2}{3} + \tfrac{1}{3} = 1$ : cae exactamente en el borde, como debe. Mueve el deslizador del panel a $45^\circ$ y verás este mismo punto.

Ejercicios

Ejercicio 1

Verifica que $M(x,y) = \left(\begin{smallmatrix} 2+x & y \\ y & 1-\tfrac{x}{2}\end{smallmatrix}\right)$ es semidefinida positiva si y solo si $\tfrac{x^2}{4} + \tfrac{y^2}{2} \le 1$ .

Solución

Una matriz simétrica $2\times 2$ es PSD si y solo si su traza y su determinante son $\ge 0$ (equivalentemente, ambos menores diagonales y el determinante). Aquí $\det M = (2+x)(1-\tfrac{x}{2}) - y^2 = 2 - \tfrac{x^2}{2} - y^2$ . Pedir $\det M \ge 0$ da $\tfrac{x^2}{2} + y^2 \le 2$ , es decir $\tfrac{x^2}{4} + \tfrac{y^2}{2} \le 1$ . Dentro de esa elipse las entradas diagonales $2+x$ y $1-\tfrac{x}{2}$ son automáticamente positivas (porque $|x| \le 2$ ), así que la condición del determinante basta.

Ejercicio 2

En el espectraedro elíptico de arriba, ¿por qué el óptimo de un objetivo lineal nunca cae en el interior? Argumenta con el gradiente del objetivo.

Solución

El objetivo lineal $c^{\mathsf{T}} p$ tiene gradiente constante $c \neq 0$ . En cualquier punto interior puedes moverte una distancia pequeña en la dirección $c$ sin salir del conjunto, aumentando estrictamente el objetivo; luego ningún interior es óptimo. El máximo se alcanza en la frontera, donde el operador semidefinido positivo se vuelve singular. Es el mismo principio por el que los óptimos de la programación lineal caen en vértices: aquí la frontera es curva, pero la lógica del gradiente es idéntica.