Dualidad (optimización) - Duality (optimization)

En la teoría matemática de la optimización , la dualidad o el principio de dualidad es el principio de que los problemas de optimización pueden verse desde dos perspectivas, el problema primario o el problema dual . La solución al problema dual proporciona un límite inferior a la solución del problema primario (minimización). Sin embargo, en general, los valores óptimos de los problemas primarios y duales no necesitan ser iguales. Su diferencia se llama brecha de dualidad . Para problemas de optimización convexa , la brecha de dualidad es cero bajo una condición de calificación de restricción .

Problema dual

Por lo general, el término "problema dual" se refiere al problema dual de Lagrange, pero se utilizan otros problemas duales, por ejemplo, el problema dual de Wolfe y el problema dual de Fenchel . El problema dual de Lagrange se obtiene formando el Lagrangiano de un problema de minimización mediante el uso de multiplicadores de Lagrange no negativos para sumar las restricciones a la función objetivo, y luego resolviendo los valores de las variables primarias que minimizan la función objetivo original. Esta solución da las variables primarias como funciones de los multiplicadores de Lagrange, que se denominan variables duales, de modo que el nuevo problema es maximizar la función objetivo con respecto a las variables duales bajo las restricciones derivadas sobre las variables duales (incluyendo al menos la no negatividad limitaciones).

En general dado dos pares duales de separadas espacios localmente convexos y y la función , podemos definir el problema primal como encontrar tal que En otras palabras, si existe, es el mínimo de la función y la infimum (extremo inferior) de la función se alcanza. ${\ Displaystyle \ left (X, X ^ {*} \ right)}$${\ Displaystyle \ left (Y, Y ^ {*} \ right)}$${\ Displaystyle f: X \ to \ mathbb {R} \ cup \ {+ \ infty \}}$${\ Displaystyle {\ hat {x}}}$${\ Displaystyle f ({\ hat {x}}) = \ inf _ {x \ in X} f (x). \,}$${\ Displaystyle {\ hat {x}}}$${\ Displaystyle f ({\ hat {x}})}$${\ Displaystyle f}$

Si hay condiciones de restricción, estas se pueden incorporar a la función dejando dónde está una función adecuada en que tiene un mínimo de 0 en las restricciones, y para la cual se puede demostrar eso . La última condición se satisface trivialmente, pero no siempre de manera conveniente, para la función característica (es decir, para satisfacer las restricciones y demás). Luego, extiéndalo a una función de perturbación tal que . ${\ Displaystyle f}$${\ Displaystyle {\ tilde {f}} = f + I _ {\ mathrm {restricciones}}}$${\ Displaystyle I _ {\ mathrm {restricciones}}}$${\ Displaystyle X}$${\ Displaystyle \ inf _ {x \ in X} {\ tilde {f}} (x) = \ inf _ {x \ \ mathrm {restringido}} f (x)}$${\ Displaystyle I _ {\ mathrm {restricciones}} (x) = 0}$${\ Displaystyle x}$${\ Displaystyle I _ {\ mathrm {restricciones}} (x) = \ infty}$${\ Displaystyle {\ tilde {f}}}$ ${\ Displaystyle F: X \ times Y \ to \ mathbb {R} \ cup \ {+ \ infty \}}$${\ displaystyle F (x, 0) = {\ tilde {f}} (x)}$

La brecha de dualidad es la diferencia de los lados derecho e izquierdo de la desigualdad.

${\ Displaystyle \ sup _ {y ^ {*} \ in Y ^ {*}} - F ^ {*} (0, y ^ {*}) \ leq \ inf _ {x \ in X} F (x, 0), \,}$

donde es el conjugado convexo en ambas variables y denota el supremo (mínimo límite superior). ${\ Displaystyle F ^ {*}}$${\ Displaystyle \ sup}$

Brecha de dualidad

La brecha de dualidad es la diferencia entre los valores de cualquier solución primaria y cualquier solución dual. Si es el valor dual óptimo y es el valor primario óptimo, entonces la brecha de dualidad es igual a . Este valor es siempre mayor o igual a 0. La brecha de dualidad es cero si y solo si se mantiene la dualidad fuerte . De lo contrario, la brecha es estrictamente positiva y la dualidad débil se mantiene. ${\ Displaystyle d ^ {*}}$${\ Displaystyle p ^ {*}}$${\ Displaystyle p ^ {*} - d ^ {*}}$

En la optimización computacional, a menudo se informa otra "brecha de dualidad", que es la diferencia de valor entre cualquier solución dual y el valor de una iteración factible pero subóptima para el problema primario. Esta "brecha de dualidad" alternativa cuantifica la discrepancia entre el valor de una iteración actual factible pero subóptima para el problema primario y el valor del problema dual; el valor del problema dual es, en condiciones de regularidad, igual al valor de la relajación convexa del problema primario: la relajación convexa es el problema que surge al reemplazar un conjunto factible no convexo con su casco convexo cerrado y al reemplazar un conjunto no convexo función convexa con su cierre convexo , que es la función que tiene el epígrafe que es el casco convexo cerrado de la función objetivo primordial original.

Caso lineal

Los problemas de programación lineal son problemas de optimización en los que la función objetivo y las restricciones son todas lineales . En el problema primario, la función objetivo es una combinación lineal de n variables. Hay m restricciones, cada una de las cuales coloca un límite superior en una combinación lineal de las n variables. El objetivo es maximizar el valor de la función objetivo sujeta a las restricciones. Una solución es un vector (una lista) de n valores que alcanza el valor máximo para la función objetivo.

En el problema dual, la función objetivo es una combinación lineal de los valores m que son los límites en las restricciones m del problema primario. Hay n restricciones duales, cada una de las cuales coloca un límite inferior en una combinación lineal de m variables duales.

Relación entre el problema primario y el problema dual

En el caso lineal, en el problema primario, desde cada punto subóptimo que satisface todas las restricciones, hay una dirección o subespacio de direcciones para moverse que aumenta la función objetivo. Se dice que moverse en cualquier dirección elimina la holgura entre la solución candidata y una o más restricciones. Un valor inviable de la solución candidata es uno que excede una o más de las restricciones.

En el problema dual, el vector dual multiplica las restricciones que determinan las posiciones de las restricciones en el primario. Variar el vector dual en el problema dual es equivalente a revisar los límites superiores en el problema primario. Se busca el límite superior más bajo. Es decir, el vector dual se minimiza para eliminar la holgura entre las posiciones candidatas de las restricciones y el óptimo real. Un valor inviable del vector dual es uno que es demasiado bajo. Establece las posiciones candidatas de una o más de las restricciones en una posición que excluye el óptimo real.

Esta intuición se formaliza mediante las ecuaciones en Programación lineal: Dualidad .

Caso no lineal

En la programación no lineal , las restricciones no son necesariamente lineales. No obstante, se aplican muchos de los mismos principios.

Para asegurar que el máximo global de un problema no lineal se pueda identificar fácilmente, la formulación del problema a menudo requiere que las funciones sean convexas y tengan conjuntos compactos de nivel inferior.

Este es el significado de las condiciones de Karush-Kuhn-Tucker . Proporcionan las condiciones necesarias para identificar óptimos locales de problemas de programación no lineal. Hay condiciones adicionales (calificaciones de restricción) que son necesarias para que sea posible definir la dirección hacia una solución óptima . Una solución óptima es aquella que es un óptimo local, pero posiblemente no un óptimo global.

El principio fuerte de Lagrange: la dualidad de Lagrange

Dado un problema de programación no lineal en forma estándar

${\ displaystyle {\ begin {alineado} {\ text {minimizar}} & f_ {0} (x) \\ {\ text {sujeto a}} & f_ {i} (x) \ leq 0, \ i \ in \ left \ {1, \ ldots, m \ right \} \\ & h_ {i} (x) = 0, \ i \ in \ left \ {1, \ ldots, p \ right \} \ end {alineado}}}$

con el dominio que tiene un interior no vacío, la función lagrangiana se define como ${\ Displaystyle {\ mathcal {D}} \ subconjunto \ mathbb {R} ^ {n}}$ ${\ Displaystyle \ Lambda: \ mathbb {R} ^ {n} \ times \ mathbb {R} ^ {m} \ times \ mathbb {R} ^ {p} \ to \ mathbb {R}}$

${\ Displaystyle \ Lambda (x, \ lambda, \ nu) = f_ {0} (x) + \ sum _ {i = 1} ^ {m} \ lambda _ {i} f_ {i} (x) + \ suma _ {i = 1} ^ {p} \ nu _ {i} h_ {i} (x).}$

Los vectores y se denominan variables duales o vectores multiplicadores de Lagrange asociados con el problema. La función dual de Lagrange se define como ${\ Displaystyle \ lambda}$${\ Displaystyle \ nu}$ ${\ Displaystyle g: \ mathbb {R} ^ {m} \ times \ mathbb {R} ^ {p} \ to \ mathbb {R}}$

${\ Displaystyle g (\ lambda, \ nu) = \ inf _ {x \ in {\ mathcal {D}}} \ Lambda (x, \ lambda, \ nu) = \ inf _ {x \ in {\ mathcal { D}}} \ left (f_ {0} (x) + \ sum _ {i = 1} ^ {m} \ lambda _ {i} f_ {i} (x) + \ sum _ {i = 1} ^ {p} \ nu _ {i} h_ {i} (x) \ right).}$

La función dual g es cóncava, incluso cuando el problema inicial no es convexo, porque es un mínimo puntual de funciones afines. La función dual produce límites inferiores al valor óptimo del problema inicial; para todos y cada uno de los que tenemos . ${\ Displaystyle p ^ {*}}$${\ Displaystyle \ lambda \ geq 0}$${\ Displaystyle \ nu}$${\ Displaystyle g (\ lambda, \ nu) \ leq p ^ {*}}$

Si se cumple una calificación de restricción como la condición de Slater y el problema original es convexo, entonces tenemos una fuerte dualidad , es decir . ${\ Displaystyle d ^ {*} = \ max _ {\ lambda \ geq 0, \ nu} g (\ lambda, \ nu) = \ inf f_ {0} = p ^ {*}}$

Problemas convexos

Para un problema de minimización convexo con restricciones de desigualdad,

${\ displaystyle {\ begin {alineado} & {\ underset {x} {\ operatorname {minimizar}}} && f (x) \\ & \ operatorname {sujeto \; to} && g_ {i} (x) \ leq 0, \ quad i = 1, \ ldots, m \ end {alineado}}}$

el problema dual de Lagrange es

${\ Displaystyle {\ begin {alineado} & {\ underset {u} {\ operatorname {maximizar}}} && \ inf _ {x} \ left (f (x) + \ sum _ {j = 1} ^ {m } u_ {j} g_ {j} (x) \ right) \\ & \ operatorname {sujeto \; to} && u_ {i} \ geq 0, \ quad i = 1, \ ldots, m \ end {alineado}} }$

donde la función objetivo es la función dual de Lagrange. Siempre que las funciones y sean continuamente diferenciables, el mínimo se produce cuando el gradiente es igual a cero. El problema ${\ Displaystyle f}$${\ Displaystyle g_ {1}, \ ldots, g_ {m}}$

${\ Displaystyle {\ begin {alineado} & {\ underset {x, u} {\ operatorname {maximizar}}} && f (x) + \ sum _ {j = 1} ^ {m} u_ {j} g_ {j } (x) \\ & \ operatorname {sujeto \; para} && \ nabla f (x) + \ sum _ {j = 1} ^ {m} u_ {j} \, \ nabla g_ {j} (x) = 0 \\ &&& u_ {i} \ geq 0, \ quad i = 1, \ ldots, m \ end {alineado}}}$

se llama el problema dual de Wolfe. Este problema puede ser difícil de resolver computacionalmente, porque la función objetivo no es cóncava en las variables conjuntas . Además, la restricción de igualdad no es lineal en general, por lo que el problema dual de Wolfe suele ser un problema de optimización no convexo. En cualquier caso, la dualidad débil se mantiene. ${\ Displaystyle (u, x)}$${\ Displaystyle \ nabla f (x) + \ sum _ {j = 1} ^ {m} u_ {j} \, \ nabla g_ {j} (x)}$

Historia

Según George Dantzig , el teorema de la dualidad para la optimización lineal fue conjeturado por John von Neumann inmediatamente después de que Dantzig presentara el problema de programación lineal. Von Neumann notó que estaba usando información de su teoría de juegos y conjeturó que el juego matricial de suma cero para dos personas era equivalente a la programación lineal. Albert W. Tucker y su grupo publicaron por primera vez pruebas rigurosas en 1948 . (Prólogo de Dantzig a Nering y Tucker, 1993)

Ver también

• Dualidad convexa
• Dualidad
• Relajación (aproximación)

Notas

Referencias

Libros

• Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Flujos de red: teoría, algoritmos y aplicaciones . Prentice Hall. ISBN 0-13-617549-X.
• Bertsekas, Dimitri; Nedic, Angelia; Ozdaglar, Asuman (2003). Análisis y Optimización Convexos . Athena Scientific. ISBN 1-886529-45-0.
• Bertsekas, Dimitri P. (1999). Programación no lineal (2ª ed.). Athena Scientific. ISBN 1-886529-00-0.
• Bertsekas, Dimitri P. (2009). Teoría de la optimización convexa . Athena Scientific. ISBN 978-1-886529-31-1.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Optimización numérica: Aspectos teóricos y prácticos . Universitext (Segunda edición revisada de la traducción de la edición francesa de 1997). Berlín: Springer-Verlag. págs. xiv + 490. doi : 10.1007 / 978-3-540-35447-5 . ISBN 3-540-35445-X. Señor  2265882 .
• Cook, William J .; Cunningham, William H .; Pulleyblank, William R .; Schrijver, Alexander (12 de noviembre de 1997). Optimización combinatoria (1ª ed.). John Wiley e hijos. ISBN 0-471-55894-X.
• Dantzig, George B. (1963). Programación lineal y extensiones . Princeton, Nueva Jersey: Princeton University Press.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Algoritmos de análisis y minimización convexos, Volumen I: Fundamentos . Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]. 305 . Berlín: Springer-Verlag. págs. xviii + 417. ISBN 3-540-56850-6. Señor  1261420 .
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "14 Dualidad para practicantes". Algoritmos de análisis y minimización convexos, Volumen II: Teoría avanzada y métodos de agrupación . Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]. 306 . Berlín: Springer-Verlag. págs. xviii + 346. ISBN 3-540-56852-2. Señor  1295240 .
• Lasdon, Leon S. (2002) [Reimpresión del Macmillan de 1970]. Teoría de optimización para grandes sistemas . Mineola, Nueva York: Dover Publications, Inc. págs. Xiii + 523. ISBN 978-0-486-41999-2. Señor  1888251 .
• Lawler, Eugene (2001). "4.5. Implicaciones combinatorias del teorema de corte mínimo de flujo máximo, 4.6. Interpretación de programación lineal del teorema de corte mínimo de flujo máximo". Optimización combinatoria: redes y matroides . Dover. págs. 117-120. ISBN 0-486-41453-1.
• Lemaréchal, Claude (2001). "Relajación lagrangiana". En Jünger, Michael; Naddef, Denis (eds.). Optimización combinatoria computacional: artículos de la Escuela de Primavera celebrada en Schloß Dagstuhl, del 15 al 19 de mayo de 2000 . Lecture Notes in Computer Science (LNCS). 2241 . Berlín: Springer-Verlag. págs. 112-156. doi : 10.1007 / 3-540-45586-8_4 . ISBN 3-540-42877-1. Señor  1900016 .
• Minoux, Michel (1986). Programación matemática: teoría y algoritmos . Egon Balas (delantero); Steven Vajda (traducción) del francés (1983 Paris: Dunod). Chichester: una publicación de Wiley-Interscience. John Wiley & Sons, Ltd. págs. Xxviii + 489. ISBN 0-471-90170-9. Señor  0868279 . (2008 Segunda ed., En francés: Programmation mathématique: Théorie et algorítmes , Éditions Tec & Doc, París, 2008. xxx + 711 pp.)).
• Nering, Evar D .; Tucker, Albert W. (1993). Programación lineal y problemas relacionados . Boston, MA: Prensa académica. ISBN 978-0-12-515440-6.
• Papadimitriou, Christos H .; Steiglitz, Kenneth (julio de 1998). Optimización combinatoria: algoritmos y complejidad (edición íntegra). Dover. ISBN 0-486-40258-4.
• Ruszczyński, Andrzej (2006). Optimización no lineal . Princeton, Nueva Jersey: Princeton University Press . págs. xii + 454. ISBN 978-0691119151. Señor  2199043 .

Artículos

• Everett, Hugh, III (1963). "Método multiplicador de Lagrange generalizado para la resolución de problemas de asignación óptima de recursos" . Investigación operativa . 11 (3): 399–417. doi : 10.1287 / opre.11.3.399 . JSTOR  168028 . Señor  0152360 . Archivado desde el original el 24 de julio de 2011.
• Kiwiel, Krzysztof C .; Larsson, Torbjörn; Lindberg, P. O. (agosto de 2007). "Relajación lagrangiana a través de métodos de subgradiente ballstep" . Matemáticas de la investigación operativa . 32 (3): 669–686. doi : 10.1287 / moor.1070.0261 . Señor  2348241 .
• Dualidad en la programación lineal Gary D. Knott