13 votos

Cómo entender convexa de la dualidad de forma intuitiva

Hay una forma intuitiva de entender la parte convexa de la dualidad? Si el problema primal es de minimización, el dual es la maximización sobre otro conjunto de variables - pero me encantaría tener una visualización geométrica de este y de una forma intuitiva para entender por qué esto debería ser cierto. También me gustaría, quiere una fuerte dualidad presente en dicha intuición.

Los libros de texto son densos en las matemáticas, pero no he encontrado un lugar donde esto podría ser imaginado en nuestras mentes sin variables y ecuaciones. ¿Podría alguien por aquí que me ayude?

10voto

littleO Puntos 12894

Esto no es lo que se les pide, pero bueno la intuición por el hecho de que si $f$ es un cerrado convexo de la función, a continuación,$f^{**} = f$. (Aquí se $f^*$ es convexo de la conjugada de $f$.)

Creo que el origen de toda dualidad, resultados de análisis convexo es el hecho de que un conjunto convexo cerrado $C$ es la intersección de todos los cerrados de la mitad de los espacios que contengan $C$.

Si aplicamos esta idea a el epígrafe de un cerrado convexo función de $f$, podemos ver que $f$ es el supremum de todos los afín a las funciones que se majorized por $f$.

Para cualquier pendiente $m$, puede haber diferentes constantes de $b$ de manera tal que la función afín $\langle m, x \rangle - b$ es majorized por $f$. Sólo se necesitan los mejores constante.

Eso es lo que la convexo conjugado $f^*$ hace por nosotros. Dada una pendiente $m$, $f^*$ vuelve la mejor constante $b$ tal que $\langle m, x \rangle - b$ es majorized por $f$. Y (claramente) la mejor opción de $b$ es:

\begin{equation} f^*(m) = \sup_x \quad \langle m, x \rangle - f(x). \end{equation} ($\langle m, x \rangle$ supera $f(x)$ a la mayoría de los $f^*(m)$, por lo que $\langle m, x \rangle - f^*(m)$ supera $f(x)$ a la mayoría de los $0$.)

Desde esta perspectiva, es inmediato que para cualquier $x$ \begin{equation} f(x) = \sup_m \quad \langle m, x \rangle - f^*(m). \end{equation} Y esta dice que el $f(x) = f^{**}(x)$.

Aquí hay una forma natural para asociar un conjunto convexo cerrado con la función de $f$, y llevó a una dualidad en el resultado. Es allí una manera similar a la que asociar un conjunto convexo cerrado con un problema de optimización convexa, y obtener una dualidad resultado para problemas de optimización convexa?

Si el problema de optimización es: \begin{align} \operatorname*{minimize}_x &\quad f(x) \\ \text{subject to} & \quad Ax = b \\ & \quad h_i(x) \leq 0 \quad \text{for } i = 1,\ldots, m \end{align} donde $f$ $h_i,i=1,\ldots, m$ están cerradas las funciones convexas, entonces podemos asociar un "prólogo" a este problema de optimización convexa de la siguiente manera: \begin{equation} C = \{ (u,v,t) \mid \exists \, x \,\text{such that } f(x) \leq t, Au = b, h_i(x) \leq v_i \text{ for } i = 1,\ldots,m \}. \end{equation}

Por el pensamiento de $C$ en términos de cerrado de la mitad de los espacios que contengan $C$, o en términos de hyperplanes que apoyan $C$, se puede obtener una interpretación geométrica de la doble problema, y una buena prueba de un fuerte teorema de la dualidad.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X