Qué es un programa cónico

Un programa cónico es la receta más económica posible para optimizar de forma convexa: un objetivo lineal, una restricción afín, y la exigencia de que la solución viva en un cono. Toda su riqueza está en qué cono elijas. Aquí montamos el primal, el dual, y la relación entre ambos.

Los ingredientes

Fijamos dos espacios reales con producto interior, $\mathcal{V}$ y $\mathcal{W}$ (piensa en $\mathrm{Herm}$ de algún espacio). Necesitamos:

un cono convexo cerrado $K \subseteq \mathcal{V}$ ;
un mapa lineal $\Phi : \mathcal{V} \to \mathcal{W}$ ;
dos vectores, $a \in \mathcal{V}$ y $b \in \mathcal{W}$ .

Es importante que el cuerpo de escalares sea $\mathbb{R}$ : aunque los operadores tengan entradas complejas, $\mathrm{Herm}(\mathcal{X})$ es un espacio vectorial real, y la teoría de dualidad se apoya en ello.

El problema primal

Con esos ingredientes, el problema primal es

\begin{array}{ll} \text{maximizar} & \langle a, x\rangle \\[2pt] \text{sujeto a} & \Phi(x) = b, \\[2pt] & x \in K. \end{array}

Un $x$ que cumple ambas restricciones es factible; el mayor valor alcanzable de $\langle a, x\rangle$ es el valor óptimo primal. La programación lineal es el caso $K = \mathbb{R}^n_{\ge 0}$ ; la semidefinida, el caso $K = \mathrm{Pos}(\mathcal{X})$ .

El adjunto

Para escribir el dual necesitamos una pieza: el adjunto (mapa) de $\Phi$ . Es el único mapa lineal $\Phi^{*} : \mathcal{W} \to \mathcal{V}$ que traslada el producto interior de un lado al otro:

\langle \Phi^{*}(y),\, x\rangle_{\mathcal{V}} = \langle y,\, \Phi(x)\rangle_{\mathcal{W}} \qquad \text{para todo } x \in \mathcal{V},\ y \in \mathcal{W}.

Si representas $\Phi$ por una matriz, $\Phi^{*}$ es su transpuesta conjugada. Para superoperadores es la misma idea, un nivel más arriba.

El problema dual

El problema dual asociado se construye con el adjunto y con el cono dual del artículo anterior:

\begin{array}{ll} \text{minimizar} & \langle b, y\rangle \\[2pt] \text{sujeto a} & \Phi^{*}(y) - a \in K^{*}. \end{array}

Aquí $y \in \mathcal{W}$ es libre (no vive en ningún cono), pero la holgura $\Phi^{*}(y) - a$ debe caer en el cono dual $K^{*}$ . Es exactamente donde el trabajo geométrico del Artículo 01 rinde fruto.

Dualidad débil, en tres líneas

La dualidad débil dice que cualquier valor dual factible acota por arriba a cualquier valor primal factible. Toma un $x$ primal factible y un $y$ dual factible. Entonces

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

donde el primer paso usa $b = \Phi(x)$ , el segundo la definición del adjunto, y el último que $x \in K$ y $\Phi^{*}(y)-a \in K^{*}$ — que es justo lo que significa el cono dual. Por tanto

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

El valor primal nunca supera al dual. La diferencia $\langle b,y\rangle - \langle a,x\rangle$ se llama brecha de dualidad, y siempre es no negativa. La pregunta interesante —¿cuándo llega a cero?— es el tema del Artículo 04.

Ejemplos resueltos

Ejemplo resuelto 1 · Un programa cónico completo

Problema. Toma $\mathcal{V} = \mathbb{R}^2$ , cono $K = \mathbb{R}^2_{\ge 0}$ , mapa $\Phi(x) = x_1 + x_2$ hacia $\mathcal{W} = \mathbb{R}$ , con $a = (1, 2)$ y $b = 1$ . Resuelve el primal y el dual y comprueba que coinciden.

Primal. «maximizar $x_1 + 2x_2$ sujeto a $x_1 + x_2 = 1$ , $x \ge 0$ ». La restricción obliga a repartir una unidad entre $x_1$ y $x_2$ ; como $x_2$ vale el doble, conviene poner todo el peso ahí: $x = (0, 1)$ , con valor $\langle a, x\rangle = 2$ .

Dual. El adjunto de $x \mapsto x_1 + x_2$ es $y \mapsto (y, y)$ , y el ortante es autodual, así que la condición $\Phi^{*}(y) - a \in K^{*}$ es $(y, y) \ge (1, 2)$ , es decir $y \ge 1$ y $y \ge 2$ . El dual es «minimizar $y$ sujeto a $y \ge 2$ », con óptimo $y = 2$ y valor $\langle b, y\rangle = 1\cdot 2 = 2$ .

Comprobación. Valor primal $= 2 =$ valor dual: no hay brecha.

Ejemplo resuelto 2 · La brecha, con números

Problema. En el mismo programa, toma un par no óptimo pero factible: $x = (1, 0)$ en el primal e $y = 3$ en el dual. Verifica la dualidad débil y que la brecha es exactamente $\langle \Phi^{*}(y) - a,\ x\rangle$ .

Valores: $\langle a, x\rangle = 1$ y $\langle b, y\rangle = 3$ , así que $1 \le 3$ ✓. La brecha es $3 - 1 = 2$ . Y por la cuenta del artículo,

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

Coincide. Fíjate en que ambos factores son «buenos»: $x = (1,0) \in K$ y $(2,1) \in K^{*}$ , por eso su producto interior es $\ge 0$ — la brecha nunca puede ser negativa.

Ejercicios

Ejercicio 1

Comprueba que la desigualdad de dualidad débil no usa en ningún momento que $K$ sea autodual — solo la definición de cono dual. ¿Qué propiedad exacta de $K$ y $K^{*}$ hace falta en el último paso?

Solución

Solo se usa que $x \in K$ y que $\Phi^{*}(y) - a \in K^{*}$ , junto con la definición $\langle u, v\rangle \ge 0$ para $u \in K^{*}$ , $v \in K$ . No hace falta autodualidad ni ninguna condición de regularidad: la dualidad débil es gratuita. La autodualidad de $\mathrm{Pos}$ se usará más adelante solo para reconocer que el dual de una SDP es otra SDP.

Ejercicio 2

Especializa el programa cónico a $\mathcal{V} = \mathbb{R}^n$ , $K = \mathbb{R}^n_{\ge 0}$ , con $\Phi(x) = A x$ para una matriz $A$ . Escribe el dual explícitamente y reconoce el par primal-dual de la programación lineal.

Solución

El primal es «maximizar $a^{\mathsf{T}} x$ sujeto a $A x = b$ , $x \ge 0$ ». El adjunto de $x \mapsto A x$ es $y \mapsto A^{\mathsf{T}} y$ , y como el ortante es autodual, la condición $\Phi^{*}(y) - a \in K^{*}$ es $A^{\mathsf{T}} y - a \ge 0$ . El dual queda «minimizar $b^{\mathsf{T}} y$ sujeto a $A^{\mathsf{T}} y \ge a$ » — el par primal-dual estándar de la programación lineal.