Un poco sobre la dualidad cónica

Al estudiar cursos teóricos en aprendizaje automático (matemáticas, economía, optimización, finanzas, etc.), a menudo se encuentra el concepto de un "problema dual".

Las tareas duales a menudo se utilizan para obtener estimaciones inferiores (o superiores) para el objetivo funcional en problemas de optimización. Además, para casi cualquier declaración significativa del problema de optimización, el problema dual tiene una interpretación significativa. Es decir, si se enfrenta a un problema importante de optimización, entonces su problema dual también es muy importante.

En este artículo hablaré sobre la dualidad cónica. Esta forma de construir tareas duales, en mi opinión, es inmerecidamente privada de atención ...

Siguiente matan ...

¿Cómo se suelen construir las tareas duales?

Deje que se dé algún problema de optimización:

$$

$$\ min_ {x \ en R ^ n} f (x) \\ f_i (x) \ leq 0, \ quad 1 \ leq i \ leq k \\ h_i (x) = 0, 1 \ leq i \ leq m $$$

La tarea dual se construye de acuerdo con el siguiente esquema:

• Construir lagrangiana

$$

$$L (x, \ lambda, \ mu) = f (x) + \ sum_ {i = 1} ^ k \ lambda_i f_i (x) + \ sum_ {i = 1} ^ m \ mu_i h_i (x)$$

• Construye una doble función

$$

$$g (\ lambda, \ mu) = \ inf_x L (x, \ lambda, \ mu)$$

• Consigue una doble tarea

$$

$$\ max _ {\ lambda, \ mu} g (\ lambda, \ mu) \\ \ lambda \ geq 0$$

La principal dificultad en este esquema está conectada en el paso de búsqueda $$$\ inf_x L (x, \ lambda, \ mu)$ .

Si el problema no es convexo, entonces se trata de un ataúd; en el caso general, no se puede resolver en tiempo polinómico (si $$$P \ neq NP$ ) y los problemas de este artículo que no abordaremos en el futuro.

Suponga que el problema es convexo, ¿entonces qué?

Si el problema es fluido, entonces podemos usar la condición de optimización de primer orden $$$\ nabla_x L (x, \ lambda, \ mu) = 0$ . A partir de esta condición, si todo está bien, resulta deducir o $$$x (\ lambda, \ mu) = \ arg \ min_x L (x, \ lambda, \ mu)$ y $$$g (\ lambda, \ mu) = L (x (\ lambda, \ mu), \ lambda, \ mu)$ o directamente funciona $$$g (\ lambda, \ mu)$ .

Si el problema no es sencillo, entonces podríamos usar un análogo de la condición de primer orden $$$0 \ in \ partial_x L (x, \ lambda, \ mu)$ (aquí $$$\ partial_x L (x, \ lambda, \ mu)$ denota un subdireccional de una función $$$L (x, \ lambda, \ mu)$ ), sin embargo, este procedimiento suele ser mucho más complicado.

A veces hay un problema de optimización "suave" equivalente y se puede construir uno doble para él. Pero para la mejora de la estructura (de no suave a suave), por regla general, siempre debe pagar un aumento en la dimensión.

Dualidad cónica

Hay bastantes tareas de optimización (ejemplos a continuación) que admiten la siguiente representación:

$$

$$\ min_ {x \ en R ^ n} c ^ Tx \\ Ax + b \ en K$$

donde $$$A$ - matriz $$$b$ - vector $$$K$ - cono convexo no degenerado.

En este caso, la tarea dual se puede construir de acuerdo con el siguiente esquema:

La tarea dual se construye de acuerdo con el siguiente esquema:

• Construir lagrangiana

$$

$$L (x, \ lambda) = c ^ Tx + \ lambda ^ T (Ax + b)$$

• Construye una doble función

$$

$$g (\ lambda) = \ inf_x L (x, \ lambda) = \ begin {cases} \ lambda ^ T b, \ quad c + A ^ T \ lambda = 0 \\ - \ infty, \ quad c + A ^ T \ lambda \ neq 0 \ end {cases}$$

• Consigue una doble tarea

$$

$$\ max _ {\ lambda} b ^ T \ lambda \\ c + A ^ T \ lambda = 0 \\ - \ lambda \ en K ^ *$$

donde esta el cono conjugado $$$K ^ *$ para cono $$$K$ definido como $$$K ^ * = \ left \ {y \ en R ^ k | z ^ T y \ geq 0, \ quad \ forall z \ in K \ right \}$ .

Como vemos, toda la complejidad de la construcción del problema dual se transfirió a la construcción del cono dual. Pero la alegría es que hay un buen cálculo para construir conos dobles y muy a menudo se puede escribir un cono dual de inmediato.

Ejemplo

Supongamos que necesitamos construir un problema de optimización dual para el problema:

$$

$$\ min_ {x \ en R ^ n} \ | x \ | _2 + \ | x \ | _1 \\ Ax \ geq b$$

Aqui $$$\ | x \ | _1 = \ sum_ {i = 1} ^ n | x_i |$ , $$$\ | x \ | _2 = \ sqrt {\ sum_ {i = 1} ^ n x_i ^ 2}$

Lo primero que puede notar: ¡la función objetivo siempre se puede hacer lineal!

Más bien, siempre hay un problema equivalente con una función objetivo lineal:

$$

$$\ min_ {x \ en R ^ n, y \ en R, z \ en R} y + z \\ \ | x \ | _2 \ leq y \\ \ | x \ | _1 \ leq z \\ Ax \ geq b$$

Ahora necesita usar un poco de conocimiento secreto: muchos

$$

$$K_1 = \ {(x, t) \ en R ^ n \ veces R | \ quad \ | x \ | _1 \ leq t \}$$

y

$$

$$K_2 = \ {(x, t) \ en R ^ n \ veces R | \ quad \ | x \ | _2 \ leq t \}$$

son conos convexos

Por lo tanto, llegamos a la notación equivalente del problema:

$$

$$\ min_ {x \ en R ^ n, y \ en R, z \ en R} y + z \\ I_ {n + 1} \ begin {pmatrix} x \\ y \ end {pmatrix} + 0_ {n +1} \ en K_2 \\ I_ {n + 1} \ begin {pmatrix} x \\ z \ end {pmatrix} + 0_ {n + 1} \ en K_1 \\ Ax-b \ en R _ + ^ k$$

Ahora podemos escribir de inmediato un problema doble:

$$

$$\ max _ {\ lambda, \ mu, \ nu} -b ^ T \ nu \\ \ lambda_i + \ mu_i + [A ^ T \ nu] _i = 0, \ quad 1 \ leq i \ leq n \\ \ lambda_ { n + 1} + 1 = 0 \\ \ mu_ {n + 1} +1 = 0 \\ - \ lambda \ en K_2 ^ * (= K_2) \\ - \ mu \ en K_1 ^ * (= K _ {\ infty}) \\ - \ nu \ en R ^ k _ +$$

o, para simplificar un poco,

$$

$$\ max _ {\ lambda, \ mu, \ nu} -b ^ T \ nu \\ \ lambda + \ mu + A ^ T \ nu = 0 \\ \ | \ lambda \ | _2 \ leq 1 \\ \ | \ mu \ | _ {\ infty} \ leq 1 \\ - \ nu \ en R ^ k _ +$$

donde $$$\ | \ mu \ | _ {\ infty} = \ max_ {i} | \ mu_i |$ .

Enlaces para estudios posteriores:

• S. Boyd y L. Vanderberghe, Optimización convexa, 2.6 (p. 51)
• A. Ben-Tall y L. El Ghaoui y A. Nemirovski, Robust Optimization, App. Un