Conos, convexidad y dualidad

Casi todo objeto de la teoría de la información cuántica vive en un conjunto convexo: los estados, las medidas, los canales. Y la restricción que más se repite —«ser semidefinido positivo»— es la pertenencia a un cono. Este artículo construye ese lenguaje geométrico desde cero, hasta llegar a la idea que gobierna toda la dualidad: el cono dual.

Conjuntos convexos

Un conjunto convexo es de una sencillez engañosa: un conjunto $C$ tal que, si tomas dos de sus puntos, todo el segmento que los une también está dentro. Formalmente, para todo $u, v \in C$ y todo $\lambda \in [0,1]$ ,

\lambda\, u + (1-\lambda)\, v \in C.

El conjunto de operadores de densidad es convexo: mezclar dos estados con probabilidades $\lambda$ y $1-\lambda$ da otro estado válido. Esa mezcla es exactamente una combinación convexa. La convexidad es lo que hace que la optimización sea tratable, y es la propiedad de fondo de todo el curso.

Conos

Un cono captura una idea distinta: la de dirección sin escala. Un conjunto $K$ es un cono si, siempre que contiene un vector, contiene también todos sus múltiplos no negativos:

v \in K \;\text{ y }\; \lambda \ge 0 \;\Longrightarrow\; \lambda v \in K.

Un cono no tiene por qué ser convexo: la unión de dos rectas por el origen es un cono, pero no es convexo. Lo que nos interesa es la combinación de ambas propiedades. Un cono convexo es un cono que además es convexo; equivale a estar cerrado bajo sumas y bajo escalado no negativo. El ejemplo que nos importa:

\mathrm{Pos}(\mathcal{X}) = \{\, P \in \mathrm{Herm}(\mathcal{X}) : P \succeq 0 \,\}

es un cono convexo cerrado dentro del espacio real $\mathrm{Herm}(\mathcal{X})$ . Si dos operadores son semidefinidos positivos, su suma lo es, y cualquier múltiplo no negativo también. Otros ejemplos clásicos son el ortante no negativo $\mathbb{R}^n_{\ge 0}$ (que da la programación lineal) y el cono de segundo orden.

El cono dual

Aquí está la idea central del artículo. A cada conjunto $A$ le asociamos otro, su cono dual — el conjunto de las direcciones que forman un ángulo no obtuso con todos los puntos de $A$ :

A^{*} = \{\, y \in \mathcal{V} : \langle y, x\rangle \ge 0 \ \text{ para todo } x \in A \,\}.

No importa cómo de irregular sea $A$ : su dual $A^{*}$ siempre es un cono convexo cerrado, porque es una intersección de semiespacios (uno por cada $x \in A$ ). Como el producto interior es lineal, basta comprobar la condición sobre las direcciones extremas de $A$ , no sobre todos sus puntos.

La forma más rápida de desarrollar intuición es jugar. Abajo, $K$ es el cono convexo azul en el plano; su dual $K^{*}$ es la región ámbar. Mueve el ángulo base y la apertura y observa cómo responde el dual:

Un cono y su dual

K = K* — apertura de 90°: el cono es autodual. Es lo que le ocurre al cono de operadores semidefinidos positivos.

Ángulo base 20°

Apertura 90°

Dos hechos saltan a la vista. Primero, estrecho ↔ ancho: cuanto más afilado es $K$ , más grande es $K^{*}$ , y viceversa. En el límite, un rayo (cono de apertura cero) tiene por dual un semiplano entero. Segundo, y más importante para nosotros: cuando la apertura es de 90°, el cono coincide con su dual. Es autodual.

¿Por qué nos importa? El cono de operadores semidefinidos positivos $\mathrm{Pos}(\mathcal{X})$ es autodual bajo el producto interior de Hilbert-Schmidt: $\mathrm{Pos}(\mathcal{X})^{*} = \mathrm{Pos}(\mathcal{X})$ . La cuña autodual de 90° del plano es la versión de juguete de ese hecho. Es lo que hará que el dual de una programa semidefinido vuelva a ser una SDP.

El teorema de bidualidad

Un último resultado que usaremos sin pensarlo: para un cono convexo cerrado $K$ , tomar el dual dos veces devuelve el original,

(K^{*})^{*} = K.

Es el análogo cónico de que el biortogonal de un subespacio cerrado es él mismo. La consecuencia práctica es que primal y dual están en pie de igualdad: cada uno es el dual del otro. Esa simetría es la que hace que la teoría de dualidad sea tan limpia — y es lo que montaremos en el próximo artículo.

Ejemplos resueltos

Ejemplo resuelto 1 · Calcular un cono dual

Problema. En $\mathbb{R}^2$ , sea $K$ el cono generado por los rayos $(1,0)$ y $(1,1)$ . Encuentra $K^{*}$ explícitamente.

Paso 1 — usar solo las direcciones extremas. Como el producto interior es lineal, $\langle y, x\rangle \ge 0$ para todo $x \in K$ equivale a pedirlo sobre los dos rayos que generan $K$ . Así que

K^{*} = \{\, y : \langle y,(1,0)\rangle \ge 0 \ \text{ y } \ \langle y,(1,1)\rangle \ge 0 \,\}.

Paso 2 — escribir las desigualdades. Con $y = (y_1, y_2)$ :

\langle y,(1,0)\rangle = y_1 \ge 0, \qquad \langle y,(1,1)\rangle = y_1 + y_2 \ge 0.

Resultado. $K^{*} = \{ (y_1,y_2) : y_1 \ge 0,\ y_2 \ge -y_1 \}$ . Es el cono comprendido entre las direcciones $(1,-1)$ (ángulo $-45^\circ$ ) y $(0,1)$ (ángulo $90^\circ$ ): apertura $135^\circ$ . Como $K$ tenía apertura $45^\circ$ , se cumple la regla $45^\circ + 135^\circ = 180^\circ$ del explorador de arriba.

Ejemplo resuelto 2 · Descartar un candidato

Problema. ¿Está $y = (2, -1)$ en el dual del ortante no negativo $\mathbb{R}^2_{\ge 0}$ ?

Solución. Basta encontrar un $x \in \mathbb{R}^2_{\ge 0}$ que viole la condición. Toma $x = (0,1)$ , que está en el ortante. Entonces

\langle y, x\rangle = 2\cdot 0 + (-1)\cdot 1 = -1 < 0.

Como el producto interior sale negativo para un punto de $K$ , concluimos que $y \notin K^{*}$ . (Coincide con que el ortante es autodual: su dual son los $y \ge 0$ , y $(2,-1)$ tiene una componente negativa.)

Ejercicios

Ejercicio 1

Usa el explorador de arriba para convencerte de la regla del dual. Si $K$ tiene ángulo base $\alpha$ y apertura $\omega$ , ¿cuál es la apertura de $K^{*}$ ? ¿Para qué valor de $\omega$ es $K$ autodual, independientemente de $\alpha$ ?

Solución

La condición $\langle y, x\rangle \ge 0$ para todo $x \in K$ equivale a pedirla sobre los dos rayos frontera de $K$ . Cada rayo en dirección $\theta$ impone el semiplano de direcciones dentro de 90° de él. La intersección de los dos semiplanos es el cono $[\,\alpha+\omega-90^\circ,\ \alpha+90^\circ\,]$ , de apertura $180^\circ - \omega$ . Es autodual cuando $180^\circ - \omega = \omega$ , es decir $\omega = 90^\circ$ , para cualquier base $\alpha$ .

Ejercicio 2

Demuestra que el ortante no negativo $\mathbb{R}^n_{\ge 0}$ es autodual bajo el producto interior estándar $\langle y, x\rangle = \sum_i y_i x_i$ .

Solución

Si $y \ge 0$ componente a componente, entonces $\langle y, x\rangle = \sum_i y_i x_i \ge 0$ para todo $x \ge 0$ , así que $y$ está en el dual. A la inversa, si $y$ está en el dual, tómese $x = e_i$ (el $i$ -ésimo vector de la base, que está en el ortante): entonces $\langle y, e_i\rangle = y_i \ge 0$ . Como esto vale para cada $i$ , se tiene $y \ge 0$ . Por tanto el dual es de nuevo el ortante: es autodual. Es la razón por la que el dual de un programa lineal vuelve a ser un programa lineal.