Paola, miembro de nuestro equipo, nos hizo el favor de redactar este artículo ya que conoce perfectamente el tema.
Solución:
$renewcommandRemathbbRnewcommand
$$ f^*(y) = sup_x
Dado un problema de optimización (primal)
$$ mathsfP: mathrmMinimizar_xinRe^n f(x) $$
Su Fenchel dual es
$$ mathsfD: mathrmMaximizar_yinRe^n -f^*(y) $$
y el segundo dual es
$$ mathsfP’: mathrmMinimizar_xinRe^n f^**(x) $$
En general $f^**leq f$. En el contexto de la dualidad de Fenchel, su pregunta es equivalente a preguntar bajo qué condiciones $f=f^**$.
Las condiciones necesarias y suficientes las proporciona el Teorema de Fenchel-Moreau según el cual es necesario y suficiente que $f$ sea propia, convexa y semicontinua inferior (es decir, tenga un epígrafe cerrado).
Tenga en cuenta que $f=f^**$ implica una fuerte dualidad.
Referencias:
- HH Bauschke y PL Combettes, Análisis convexo y teoría del operador monótono en espacios de Hilbert, Springer, 2011.
- RT Rockafellar, análisis convexo, Prensa de la Universidad de Princeton, 1970.
Actualizar: En el caso de la dualidad lagrangiana donde consideramos problemas de la forma beginalign mathrmMinimize_xinRe^n f(x)\ textsujeto a: xin C , endalign donde $f:Re^ntoRe$ es una función convexa y $C$ es un conjunto convexo no vacío, podemos escribir esto como beginalign mathrmMinimize_x F (x) := f(x) + delta_C(x), endalign donde $delta_C$ es el indicador función de $C$ definida como beginalign delta_C(x) = begincases 0,&text if xin C,\ +infty,&text de lo contrario end casos endalign El conjunto $C$ viene dado por $C=xinRe^n: g(x) leq 0$. El lagrangiano dual (donde “dualizamos” las restricciones introduciendo una variable dual $y$ y un costo $
Entonces, podemos aplicar lo anterior: el segundo dual es equivalente al dual siempre que $F^**=F$, entonces, si (Por el Teorema de Fenchel-Moreau) $F$ es propia, convexa y semicontinua inferior . Te dejaré a ti decir qué significa esto para $f$ y $C$.
El fenómeno en la optimización convexa de que el dual del problema dual es (generalmente) el mismo que el problema primal es aparentemente una sorpresa total, y rara vez se explica. Pero hay una explicación agradable y esclarecedora que aprendí al leer a Ekeland y Temam. Este material también se puede encontrar en el libro Variational Analysis de Rockafellar y Wets, a partir de la p. 502.
Las ideas son más claras cuando trabajamos en un nivel apropiado de generalidad. No obtenemos un problema dual hasta que especificamos cómo perturbar el problema primordial.
Supongamos que el problema principal es $$ operatornameminimize_x ,phi(x,0), $$ donde $phi:mathbb R^m times mathbb R^n to mathbb R cup infty $ es una función convexa. Para un $y$ dado, el problema de minimizar $phi(x,y)$ con respecto a $x$ puede verse como una versión “perturbada” del problema primario. Introduzcamos la “función de valor” $h(y) = inf_x , phi(x,y)$. Entonces, el problema principal es evaluar $h(0)$. Si tenemos una comprensión básica del conjugado de Fenchel, entonces sabemos que $h(0) geq h^**(0)$, y típicamente $h(0) = h^**(0) PS El problema dual es simplemente evaluar $h^**(0)$.
Intentemos escribir el problema dual más explícitamente. En primer lugar, beginalign h^*(z) &= sup_y , langle y, z rangle – h(y) \ &= sup_y , langle y, z rangle – inf_x , phi(x,y) \ &= sup_y , langle y, z rangle + sup_x – phi(x,y) \ &= sup_x,y , langle x, 0 rangle + langle y, z rangle – phi(x,y) \ &= phi^*(0,z). endalign Se sigue que beginalign h^**(0) &= sup_z , langle 0, z rangle – phi^*(0,z) \ &= – inf_z , phi^*(0,z). endalign Entonces, el problema dual, escrito como un problema de minimización, es $$ operatornameminimize_z , phi^*(0,z). $$ Mira el hermosa similitud entre los problemas primal y dual.
No obtuvimos un problema dual hasta que especificamos cómo perturbar el problema primal. Entonces, ¿qué pasa si ahora perturbamos el problema dual de la manera obvia? Un problema dual perturbado es $$ operatornameminimize_z , phi^*(w,z). $$ Ahora que hemos especificado cómo perturbar el problema dual, podemos obtener un dual para el problema dual, exactamente de la misma manera que arriba. Y puedes ver de inmediato cuál será el problema dual del dual, sin hacer ningún trabajo. El dual del problema dual es: $$ operatornameminimize_x , phi^**(x,0). $$ Pero típicamente tenemos $phi^** = phi$, en cuyo caso el dual del problema dual es exactamente el problema primario.
Quizás se pregunte cómo se conecta esta construcción de problema dual con la construcción de problema dual estándar (donde primero se forma el Lagrangiano, etc.). Supongamos que el problema primal es beginalign textminimize & quad f(x) \ textsujeto a & quad g(x) leq 0. endalign Un problema perturbado es beginalign textminimizar & quad f(x) \ textsujeto a & quad g(x) + yleq 0. endalign Habiendo especificado cómo perturbar el primario problema, ahora obtenemos un problema dual, y si resuelve los detalles, resulta ser exactamente el problema dual que esperaría. Di más detalles aquí:
Explique la intuición detrás del problema dual en la optimización.
Tienes la posibilidad dar difusión a esta noticia si te fue útil.