¿Es la teoría de la dualidad en la optimización de tan útil como parece?

Question

He estado leyendo mucho acerca de la optimización no lineal y la dualidad, y parece que la dualidad de la teoría, es extremadamente útil. Siento que me estoy perdiendo algunos de los aspectos negativos y dificultades asociadas con ella y aunque estoy esperando que alguien me puede dar algo más de perspectiva.

El hecho de que la doble función es siempre cóncava, para cualquier no lineal primal problema de optimización, se parece bastante a un resultado significativo. Ahora sé que la dualidad brecha asociada con la optima del primal y dual puede ser distinto de cero, pero siento que no tengo una idea de lo grande este espacio puede ser para algunos de los comunes (no lineal) de los problemas que surgen en la optimización.

¿Cuáles son algunas técnicas útiles para asegurar que la fuerte dualidad se mantiene, o ser capaz de decir que la dualidad de la brecha es lo suficientemente pequeño como para fines prácticos? Se está formando el doble función en un intento de resolver un programa no lineal, normalmente, un buen primer paso?

Sé que esto es una forma más bien vaga post, pero sólo estoy esperando para ganar algo más de la intuición acerca de la utilidad práctica de la dualidad de la teoría de optimización no lineal.

Answer 1

Yo en parte puede responder a una pregunta que te estás preguntando.

Un método común para asegurar que la fuerte dualidad tiene en problemas convexos (y problemas convexos) se Slater condición. Considere la posibilidad de un problema de la forma: \begin{equation} \min f_0(x) \end{equation} sujeto a \begin{equation} f_i(x) \leq 0, \,\,\,\,\,\,\,\, i = 1, \ldots, m \end{equation} y \begin{equation} Ax = b \end{equation} donde $f_i(x)$ es convexa para cada $i \in \{1, \ldots, m\}$. Definir el conjunto $D$ como la intersección de los dominios de las funciones $f_i$, es decir, $D = \cap_{i = 0}^{m} dom(f_i)$. Slater condición dice que si hay algo de $x \in relint(D)$ (donde $relint(D)$ denota la relación interior de $D$) tales que \begin{equation} f_i(x) < 0 \end{equation} para cada una de las $i = 1, \ldots, m$ y que el mismo $x$ satisface $Ax = b$, la fuerte dualidad se mantiene. Aquí, el uso de la relación interior de $D$ más que en el interior de $D$ significa que las desigualdades lineales no necesitan ser estricto; si hay algo de $f_j(x)$ que es lineal en $x$, luego Slater condición mantiene siempre como $f_j(x) \leq 0$. En otras palabras el ser igual a $0$ es permitido desigualdad lineal restricciones al aplicar Slater condición. Por supuesto, hay otros métodos, denominado "restricción de calificaciones," para garantizar la fuerte dualidad, pero Slater condición se utiliza con frecuencia debido a que es tan simple.

Como es a menudo el caso en la optimización, es difícil decir algo general acerca de la no-convexo caso, y no creo que cualquier amplias generalizaciones acerca de la fuerte dualidad de la no-convexo caso se puede hacer.