Dualidad y condición de Slater

Cuando resolvemos una SDP para calcular una cantidad —el sesgo de un juego, una entropía— queremos poder trabajar indistintamente con el primal o con el dual, sabiendo que dan el mismo número. Eso es dualidad fuerte. Este artículo explica cuándo se cumple y por qué la condición de Slater es la llave.

De ≤ a =

Recordemos del Artículo 02 que para cualquier par factible $(x, y)$ ,

\langle a, x\rangle \;\le\; \langle b, y\rangle.

Esto es dualidad débil y vale sin ninguna hipótesis. Tomando el supremo a la izquierda y el ínfimo a la derecha, el valor óptimo primal no supera al valor óptimo dual. La diferencia entre ambos es la brecha de dualidad.

dualidad fuerte es la afirmación —mucho más fuerte— de que la brecha es exactamente $0$ : los dos valores óptimos coinciden. A diferencia de la débil, esto no se cumple siempre. Existen programas cónicos con brecha estrictamente positiva, e incluso casos en los que un lado alcanza su óptimo y el otro no.

La condición de Slater

La hipótesis de regularidad más habitual que cierra la brecha es la condición de Slater: pedir que exista un punto estrictamente factible. Para el primal, esto significa un $x$ factible que no esté en la frontera del cono sino en su interior:

\exists\, x \in \mathrm{int}(K) \ \text{ con }\ \Phi(x) = b.

En una SDP, «interior del cono» quiere decir $X \succ 0$ — definida positiva, con todos los autovalores estrictamente positivos, no solo $\ge 0$ . El resultado clave (una forma del teorema de dualidad cónica) es:

Teorema (dualidad fuerte por Slater). Si el problema dual es factible y el primal cumple la condición de Slater, entonces no hay brecha de dualidad y el óptimo primal se alcanza. Simétricamente, si el primal es factible y el dual cumple Slater, la brecha es nula y el óptimo dual se alcanza.

La geometría de fondo es un teorema de separación de conjuntos convexos: la existencia de un punto interior impide que un hiperplano separe «por un pelo» y fuerza a que los valores se toquen. La estricta factibilidad es justo lo que da el margen para esa separación.

Holgura complementaria

Cuando hay dualidad fuerte, la desigualdad de la demostración de dualidad débil se satura, y eso deja una huella útil. Repasando aquella cuenta, la brecha era $\langle b,y\rangle - \langle a,x\rangle = \langle \Phi^{*}(y) - a,\ x\rangle$ . Si vale cero en el óptimo, entonces

\langle\, \Phi^{*}(y) - a,\ \ x\, \rangle = 0.

Esta es la holgura complementaria. Como ambos factores están en conos duales ( $x \in K$ , $\Phi^{*}(y)-a \in K^{*}$ ), su producto interior nulo obliga a que «no estén activos a la vez»: donde uno es estrictamente positivo, el otro se anula. En una SDP se traduce en $X\,(\Phi^{*}(Y) - A) = 0$ — un vínculo entre los rangos de las soluciones óptimas primal y dual, que es la herramienta práctica para construir soluciones y certificados.

Por qué nos importará

En los módulos siguientes, casi cada cantidad se definirá como el valor de una SDP. La dualidad fuerte —vía Slater— es lo que nos permitirá:

dar dos caras de la misma cantidad (una como máximo, otra como mínimo);
obtener cotas certificadas: cualquier punto dual factible es una cota superior demostrable;
usar la holgura complementaria para caracterizar los optimizadores.

Con esto cerramos el Módulo 01. Tienes ya el lenguaje —conos, dualidad, SDP, Slater— sobre el que se apoya todo lo que viene: la entropía max-relativa del Módulo 02 se definirá, precisamente, como un programa semidefinido.

Ejemplos resueltos

Ejemplo resuelto 1 · Comprobar Slater

Problema. Vuelve a la SDP de la elipse del Artículo 03, $M(x,y) = \left(\begin{smallmatrix} 2+x & y \\ y & 1-\tfrac{x}{2}\end{smallmatrix}\right) \succeq 0$ . ¿Cumple la condición de Slater?

Solución. Slater pide un punto estrictamente factible, $M \succ 0$ . Prueba el centro $(x,y) = (0,0)$ :

M(0,0) = \begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix}, \quad \text{autovalores } 2 \text{ y } 1 > 0.

Es definida positiva, luego hay un punto interior y Slater se cumple. Por el teorema, hay dualidad fuerte: el máximo primal y el mínimo dual coinciden. Para $c=(1,1)$ ambos valen $\sqrt{6}$ (lo calculamos en el primal en el artículo anterior; la dualidad fuerte garantiza que el dual da el mismo número).

Ejemplo resuelto 2 · Holgura complementaria con números

Problema. Ilustra $\langle S, X\rangle = 0 \Rightarrow S X = 0$ con un par concreto de operadores semidefinidos positivos $2\times 2$ .

Solución. Toma

X = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \succeq 0, \qquad S = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} \succeq 0.

Su producto interior de Hilbert-Schmidt es $\langle S, X\rangle = \mathrm{Tr}(S X) = 0$ . Y en efecto

S X = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix} = 0.

Los soportes son ortogonales: $X$ «vive» en la primera coordenada y $S$ en la segunda. Ese es el contenido geométrico de la holgura complementaria — donde una solución óptima es no nula, la otra se anula.

Ejercicios

Ejercicio 1

Explica por qué la condición de Slater pide un punto en el interior del cono ( $X \succ 0$ ) y no basta con uno en la frontera ( $X \succeq 0$ con algún autovalor nulo). ¿Qué se rompería en la separación?

Solución

La demostración construye un hiperplano separador entre el conjunto de valores alcanzables y el semieje por encima del óptimo. Si el único punto factible está en la frontera del cono, el conjunto de valores puede «besar» al hiperplano sin margen, permitiendo una brecha o que el óptimo no se alcance. Un punto interior $X \succ 0$ garantiza que hay una bola de puntos factibles alrededor, lo que da el grosor necesario para que la separación sea estricta y los valores coincidan. Sin ese margen, existen contraejemplos concretos de SDPs con brecha positiva.

Ejercicio 2

Supón dualidad fuerte y sean $X$ , $Y$ óptimos de una SDP con $X \succeq 0$ y $S := \Phi^{*}(Y) - A \succeq 0$ . A partir de $\langle S, X\rangle = 0$ , demuestra que $S X = 0$ .

Solución

Como $S \succeq 0$ , tiene raíz cuadrada $S^{1/2} \succeq 0$ . Entonces $0 = \langle S, X\rangle = \mathrm{Tr}(S X) = \mathrm{Tr}(S^{1/2} X S^{1/2})$ . El operando $S^{1/2} X S^{1/2}$ es semidefinido positivo y tiene traza nula, luego es el operador cero: $S^{1/2} X S^{1/2} = 0$ . De ahí $(X^{1/2} S^{1/2})^{*}(X^{1/2} S^{1/2}) = 0$ , así que $X^{1/2} S^{1/2} = 0$ y por tanto $S X = 0$ (y $X S = 0$ ). Los soportes de $X$ y $S$ son ortogonales: la esencia de la holgura complementaria en SDP.