La dualidad de la teoría y de optimización no lineal

Question

He estado estudiando de optimización no lineal recientemente y han llegado a través de algunos de los resultados que necesito una aclaración. Voy a hacer mi mejor esfuerzo para explicar en detalle a continuación, proporcionar citas cuando sea necesario. Voy a número de las cuestiones/preguntas para que puedan ser abordados de forma independiente si es necesario. Disculpas de antemano por la longitud. Es mi esperanza que esta pregunta también va a ayudar a aclarar las cosas para los demás también.

Considere la posibilidad de una igualdad limitados problema de optimización no lineal \begin{align} \min_{x}&\quad f(x)\\ \nonumber \text{subject to } \quad&h_i(x) = 0,\,i=1,\ldots,I\\ \nonumber \quad&x\in X\subseteq\mathbb{R}^n \end{align} donde todas las funciones se asumen para ser dos veces continuamente diferenciable. No hay más convexidad/linealidad suposiciones con respecto a las funciones que se realizan.

Entiendo que un determinado problema de optimización puede tener diferentes funciones de Lagrange, dependiendo de lo que las restricciones son dualized. Una función de Lagrange asociados con el programa no lineal es $$\mathcal{L}(x,\lambda) = f(x) + \lambda^Th(x)$$ donde $h(x) = (h_1(x),\ldots,h_I(x))$ $\lambda$ (sin restricciones) de doble variables. Vamos a poner una doble función como \begin{align} \phi(\lambda) = \min_{x\in X}\mathcal{L}(x,\lambda) \end{align} (nota: parece que la construcción de esta doble función puede ser tan difícil como resolver el problema original -- si el conjunto $X$ es complicado)

El doble problema es entonces simplemente \begin{align} \max_\lambda \phi(\lambda) \end{align}

Q1: Para una determinada función de Lagrange, es la doble función única?

Local de la dualidad de la teoría

La razón que pido Q1 es causa de un resultado como el local teorema de dualidad (Luenberger, "Lineal y Programación Lineal") enunciarse de la siguiente manera

Supongamos que el problema \begin{align} \min_{x}&\quad f(x)\\ \nonumber \text{subject to } \quad&h_i(x) = 0,\,i=1,\ldots,I \end{align} tiene un local de la solución en $x^*$ con el correspondiente valor de $r^*$ y el multiplicador de Lagrange $\lambda^*$. Supongamos también que $x^*$ es un punto habitual de las limitaciones y de que los correspondientes de la Arpillera de la Lagrangiana $L^*=L(x^*)$ es positiva definida. Entonces el problema dual \begin{align} max\quad \phi(\lambda) \end{align} tiene un local de la solución en $\lambda^*$ con el correspondiente valor de $r^*$ $x^*$ como el punto correspondiente a $\lambda^*$ en la definición de $\phi$.

Para ayudar a entender lo que el teorema es decir (tal y como yo lo entiendo - tal vez esta es la interpretación incorrecta), considere el siguiente escenario. Imagina que la función de Lagrange es una función de dos primal variables $x_1,x_2$ y tiene un gráfico de contorno que se parece a la figura siguiente.

El Lagrangiano tiene cinco puntos estacionarios, tres de los cuales son los máximos locales, dos de los cuales son mínimos locales.

Q2: ¿Es correcto pensar en la existencia de dos diferentes funciones duales, $\phi^1$$\phi^2$, cada uno asociado con sus respectivos mínimos locales? Una especie de local de doble función?

P3: Si la interpretación de Q2 es correcta, entonces parece que todos los locales de la dualidad de la teoría está diciendo es que si queremos maximizar una función dual, es decir $\phi^1(\lambda)$, $\lambda\in\Lambda^1$ (donde $\Lambda^1$ es algo de espacio local correspondiente al subconjunto de a $\mathbb{R}^2$ donde la doble función fue construido), entonces vamos a llegar al mismo valor objetivo como la solución asociada con la región en la que se formó el correspondiente doble función ($\phi^1$). Es esta la correcta línea de pensamiento?

Aquí es donde empiezo a estar un poco confundido. Yo siempre estaba bajo la impresión de que un cero a la dualidad de la brecha implícita de que hemos encontrado la solución global para el problema primal. Sin embargo, parece que el teorema de la dualidad de los estados que hemos llegado a un cero de la dualidad de la brecha con un local de la solución del problema primal. Esto lleva a mi siguiente pregunta:

Q4: ¿un cero a la dualidad de la brecha siempre implica que se han encontrado en todo el mundo un solución óptima? Si es así, ¿por qué esto no contradice el local teorema de la dualidad?

Condiciones de optimalidad global

El último grupo de preguntas que tengo es con respecto a la búsqueda de una solución global para el problema primal. Parece que a lo largo de este debate que estamos muy cerca de llegar a tener un resultado en el que asegura que resolver el doble problema tendrá como resultado un cero a la dualidad de la brecha con la solución global del problema primal. La siguiente pregunta se resume lo que pienso que puede ser una condición suficiente para ello:

P5: parece lógico pensar que si $\mathcal{L}(x,\lambda)$ es estrictamente convexa en $x$ (en todo el espacio), entonces vamos a tener una única función dual y resolver el doble problema de llevar a cero la dualidad de la brecha con la solución global del problema primal. Es este razonamiento sonido? Si no, ¿alguien sabe de un contraejemplo?

Una instrucción alternativa que vale la pena mencionar relacionado con el concepto de puntos de silla y la optimalidad global es el siguiente (de Peter Morgan, "Una explicación de optimización restringida para los economistas")

Si la silla es un global $x$-min, $\lambda$-max silla de montar, el '$x$-parte " de la silla de montar de punto es un óptimo global para el problema de optimización restringida.

Esto se resume en una declaración de la misma fuente

Teorema 9.3 (Kuhn-Tucker Silla-Teorema De Punto) Si la función de Lagrange para la limitación de problema posee un global $x$-min, $\lambda$-max silla punto de $(x^*,\lambda^*)$ $x^*$ es globalmente óptima solución a la limitación de problema.

Desafortunadamente, debido al hecho de que no tengo acceso al libro de Morgan no sé la definición precisa de lo que él entiende por "global $x$-min, $\lambda$-max silla de punto", ni tampoco tengo la prueba.

P6: ¿alguien Puede ofrecer alguna explicación o comprensión de la declaración de Morgan?

Answer 1

A1: Sí, por definición, su doble función de la original restringido problema es único. Por otra parte, es, por definición, cóncava y su supremum (o máximo, cuando es accesible), le da un límite inferior en el valor óptimo del problema original.

A2: Sí, está bien, pero tienes que tener cuidado aquí. Me estoy refiriendo a Luenberger, Ch.14, pág.442, eq.13. Los autores afirman claramente que definen su doble función en las proximidades de $(x^*,\lambda^*)$. Tomar un subconjunto de a $X$, vamos a llamar a $S=X\cap B_\epsilon(x^*)$ donde $B_\epsilon(x^*)$ es una bola de radio $\epsilon$ $x^*$ y, a continuación, puede definir $\phi_S(\lambda)=\min\limits_{x\in S}L(x,\lambda)$ que es una especie de local de doble función y es diferente de la original.

A3: Autores están un poco descuidados en sus definiciones de los mínimos locales y las cosas, pero como yo lo entiendo, local dualidad dice: supongamos que el problema original tiene un local mínimo $r^*$ $x^*$ y el 1 de orden de la condición de optimalidad (que es local) sostiene, con el correspondiente $\lambda^*$. Si consideras $x\in S$ (como hago yo en A2) y construcción $\phi_S(\lambda)$, a continuación, bajo las hipótesis del teorema, la resolución de un problema doble para $\phi_S(\lambda)$ le da el mismo $(x^*, \lambda^*)$$r^*$.

A4: Cero brecha no es violado en este caso porque en el hecho de considerar sólo a $x\in S$, y no $x\in X$, porque en $S$ tiene un localmente convexo problema y todo es bonito, se obtiene un cero brecha a nivel local, pero no para el problema original en $X$.