Dualidad (optimización)

Principio de optimización matemática.

En la teoría de la optimización matemática , la dualidad o el principio de dualidad es el principio de que los problemas de optimización pueden verse desde cualquiera de dos perspectivas, el problema primario o el problema dual . Si el primal es un problema de minimización, entonces el dual es un problema de maximización (y viceversa). Cualquier solución factible al problema primario (de minimización) es al menos tan grande como cualquier solución factible al problema dual (de maximización). Por lo tanto, la solución del primal es un límite superior de la solución del dual, y la solución del dual es un límite inferior de la solución del primal. ^[1] Este hecho se llama dualidad débil .

En general, los valores óptimos de los problemas primario y dual no tienen por qué 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 . Este hecho se llama dualidad fuerte .

Doble problema

Por lo general, el término "problema dual" se refiere al problema dual lagrangiano , pero se utilizan otros problemas duales, por ejemplo, el problema dual de Wolfe y el problema dual de Fenchel . El problema dual lagrangiano se obtiene formando el lagrangiano de un problema de minimización utilizando 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 restricciones).

En general, dados dos pares duales de espacios localmente convexos separados 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 el mínimo (máximo límite inferior) de la función se logra. ${\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, éstas se pueden incorporar a la función dejando dónde hay una función adecuada que tiene un mínimo de 0 en las restricciones y para la cual se puede probar que . La última condición se satisface de manera trivial, pero no siempre conveniente, para la función característica (es decir, para satisfacer las restricciones y otras cosas). Luego extienda a una función de perturbación tal que . ^[2] ${\displaystyle f}$ ${\displaystyle {\tilde {f}}=f+I_{\mathrm {constraints} }}$ ${\displaystyle I_{\mathrm {constraints} }}$ ${\displaystyle X}$ ${\displaystyle \inf _{x\in X}{\tilde {f}}(x)=\inf _{x\ \mathrm {constrained} }f(x)}$ ${\displaystyle I_{\mathrm {constraints} }(x)=0}$ ${\displaystyle x}$ ${\displaystyle I_{\mathrm {constraints} }(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 entre 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 supremum (límite superior mínimo). ^{[2] [3] [4]} ${\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 siempre es mayor o igual a 0 (para problemas de minimización). La brecha de dualidad es cero si y sólo si se mantiene una fuerte dualidad . De lo contrario, la brecha es estrictamente positiva y se mantiene una dualidad débil . ^[5] ${\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 principal. 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, bajo condiciones de regularidad, igual al valor de la relajación convexa del problema primal: La relajación convexa es el problema que surge reemplazando un conjunto factible no convexo con su casco convexo cerrado y reemplazando un conjunto factible no convexo con su casco convexo cerrado. función convexa con su cierre convexo , o sea la función que tiene como epígrafe que es la cáscara convexa cerrada de la función objetivo primaria original. ^{[6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16]}

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 m valores que son los límites en las m restricciones 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, existe una dirección o subespacio de direcciones para moverse que aumenta la función objetivo. Se dice que moverse en cualquiera de esas direcciones elimina la holgura entre la solución candidata y una o más restricciones. Un valor inviable de la solución candidata es aquel 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 primal. Variar el vector dual en el problema dual equivale 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 aquel 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 de Programación lineal: Dualidad .

Caso no lineal

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

Para garantizar que el máximo global de un problema no lineal pueda identificarse fácilmente, la formulación del problema a menudo requiere que las funciones sean convexas y tengan conjuntos compactos de niveles inferiores. Ésta es la importancia 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 restricciones) 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.

Dualidad de Lagrange

Motivación . ^[17] Supongamos que queremos resolver el siguiente problema de programación no lineal :

${\displaystyle {\begin{aligned}{\text{minimize }}&f_{0}(x)\\{\text{subject to }}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\\end{aligned}}}$

El problema tiene limitaciones; Nos gustaría convertirlo en un programa sin restricciones. Teóricamente, es posible hacerlo minimizando la función J ( x ), definida como

${\displaystyle J(x)=f_{0}(x)+\sum _{i}I[f_{i}(x)]}$

donde I es una función escalonada infinita : I[u]=0 si u≤0, y I[u]=∞ en caso contrario. Pero J ( x ) es difícil de resolver porque no es continuo. Es posible "aproximar" I[u] por λu , donde λ es una constante positiva. Esto produce una función conocida como lagrangiana:

${\displaystyle L(x,\lambda )=f_{0}(x)+\sum _{i}\lambda _{i}f_{i}(x)}$

Tenga en cuenta que, para cada x ,

${\displaystyle \max _{\lambda \geq 0}L(x,\lambda )=J(x)}$.

Prueba :

• Si x satisface todas las restricciones f _i ( x )≤0, entonces L( x , λ ) se maximiza cuando se toma λ =0, y su valor es entonces f(x);
• Si x viola alguna restricción, f _i ( x )>0 para alguna i , entonces L(x, λ )→∞ cuando λ _i →∞ .

Por tanto, el problema original es equivalente a:

${\displaystyle \min _{x}\max _{\lambda \geq 0}L(x,\lambda )}$.

Invirtiendo el orden de mínimo y máximo obtenemos:

${\displaystyle \max _{\lambda \geq 0}\min _{x}L(x,\lambda )}$.

La función dual es el problema interno de la fórmula anterior:

${\displaystyle g(\lambda ):=\min _{x}L(x,\lambda )}$.

El programa dual lagrangiano es el programa de maximización de g:

${\displaystyle \max _{\lambda \geq 0}g(\lambda )}$.

La solución óptima del programa dual es un límite inferior para la solución óptima del programa original (primal); Este es el principio de dualidad débil . Si el problema primario es convexo y acotado desde abajo, y existe un punto en el que todas las restricciones no lineales se satisfacen estrictamente ( condición de Slater ), entonces la solución óptima del programa dual es igual a la solución óptima del programa primario; Este es el fuerte principio de dualidad. En este caso, podemos resolver el programa primal encontrando una solución óptima λ * para el programa dual y luego resolviendo:

${\displaystyle \min _{x}L(x,\lambda ^{*})}$.

Tenga en cuenta que, para utilizar el principio de dualidad débil o fuerte, necesitamos una forma de calcular g( λ ). En general, esto puede resultar difícil, ya que necesitamos resolver un problema de minimización diferente para cada λ . Pero para algunas clases de funciones, es posible obtener una fórmula explícita para g(). Resolver los programas primario y dual juntos suele ser más fácil que resolver solo uno de ellos. Algunos ejemplos son la programación lineal y la programación cuadrática . El teorema de dualidad de Fenchel proporciona un enfoque mejor y más general de la dualidad . ^{[18] : Sub.3.3.1}

Otra condición en la que min-max y max-min son iguales es cuando el lagrangiano tiene un punto silla : (x∗, λ∗) es un punto silla de la función de Lagrange L si y solo si x∗ es una solución óptima para el primal, λ∗ es una solución óptima del dual, y los valores óptimos en los problemas indicados son iguales entre sí. ^{[18] : Proposición 3.2.2}

El fuerte principio de Lagrange

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

${\displaystyle {\begin{aligned}{\text{minimize }}&f_{0}(x)\\{\text{subject to }}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\&h_{i}(x)=0,\ i\in \left\{1,\ldots ,p\right\}\end{aligned}}}$

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

${\displaystyle {\mathcal {L}}(x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{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}}}{\mathcal {L}}(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 cualquiera y cualquiera que tengamos . ${\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 dualidad fuerte , 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{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\ldots ,m\end{aligned}}}$

El problema dual lagrangiano es

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

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

${\displaystyle {\begin{aligned}&{\underset {x,u}{\operatorname {maximize} }}&&f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\\&\operatorname {subject\;to} &&\nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)=0\\&&&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}}}$

Se llama 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 es no lineal en general, por lo que el problema dual de Wolfe suele ser un problema de optimización no convexo. En cualquier caso, se mantiene una dualidad débil . ^[19] ${\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 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)

Aplicaciones

En las máquinas de vectores de soporte (SVM), la formulación del problema primario de las SVM como el problema dual se puede utilizar para implementar el truco del Kernel , pero este último tiene una mayor complejidad temporal en los casos históricos.

Ver también

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

Notas

1. Boyd, Stephen P.; Vandenberghe, Lieven (2004). Optimización convexa (pdf) . Prensa de la Universidad de Cambridge. pag. 216.ISBN​ 978-0-521-83378-3. Consultado el 15 de octubre de 2011 .
2. Boţ, Radu Ioan; Wanka, Gert; Graduado, Sorin-Mihai (2009). Dualidad en la optimización vectorial . Saltador. ISBN 978-3-642-02885-4.
3. Csetnek, Ernö Robert (2010). Superar el fallo de las condiciones clásicas generalizadas de regularidad de puntos interiores en la optimización convexa. Aplicaciones de la teoría de la dualidad a ampliaciones de operadores monótonos máximos . Logos Verlag Berlín GmbH. ISBN 978-3-8325-2503-3.
4. Zălinescu, Constantin (2002). Análisis convexo en espacios vectoriales generales . River Edge, Nueva Jersey: World Scientific Publishing Co., Inc. págs. ISBN 981-238-067-1. SEÑOR  1921556.
5. Borwein, Jonathan; Zhu, Qiji (2005). Técnicas de Análisis Variacional . Saltador. ISBN 978-1-4419-2026-3.
6. 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.
7. Bertsekas, Dimitri; Nedic, Angelia; Ozdaglar, Asuman (2003). Análisis y optimización convexos . Atenas científica. ISBN 1-886529-45-0.
8. Bertsekas, Dimitri P. (1999). Programación no lineal (2ª ed.). Atenas científica. ISBN 1-886529-00-0.
9. Bertsekas, Dimitri P. (2009). Teoría de la optimización convexa . Atenas científica. ISBN 978-1-886529-31-1.
10. 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.
11. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Algoritmos de minimización y análisis convexo, Volumen I: Fundamentos . Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]. vol. 305. Berlín: Springer-Verlag. págs. xviii+417. ISBN 3-540-56850-6. SEÑOR  1261420.
12. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "14 Dualidad para los profesionales". Algoritmos de minimización y análisis convexo, Volumen II: Teoría avanzada y métodos de paquetes . Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]. vol. 306. Berlín: Springer-Verlag. págs. xviii+346. ISBN 3-540-56852-2. SEÑOR  1295240.
13. 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.
14. 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 . Apuntes de conferencias en informática (LNCS). vol. 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. S2CID  9048698.
15. Minoux, Michel (1986). Programación matemática: Teoría y algoritmos . Egon Balas (delantero); Steven Vajda (traducción) del francés (1983 París: Dunod). Chichester: una publicación de Wiley-Interscience. John Wiley & Sons, Ltd. págs. xxviii + 489. ISBN 0-471-90170-9. MR  0868279. (2008 Segunda ed., en francés: Programmation mathématique: Théorie et algoritmos , Éditions Tec & Doc, París, 2008. xxx+711 págs.).
16. Shapiro, Jeremy F. (1979). Programación matemática: estructuras y algoritmos. Nueva York: Wiley-Interscience [John Wiley & Sons]. págs. xvi+388. ISBN 0-471-77886-9. SEÑOR  0544669.
17. David Knowles (2010). "Dualidad lagrangiana para tontos" (PDF) .
18. Nemirovsky y Ben-Tal (2023). "Optimización III: Optimización convexa" (PDF) .^{[ enlace muerto permanente ]}
19. Geoffrion, Arthur M. (1971). "Dualidad en programación no lineal: un desarrollo simplificado orientado a aplicaciones". Revisión SIAM . 13 (1): 1–37. doi :10.1137/1013001. JSTOR  2028848.

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 . Atenas científica. ISBN 1-886529-45-0.
• Bertsekas, Dimitri P. (1999). Programación no lineal (2ª ed.). Atenas científica. ISBN 1-886529-00-0.
• Bertsekas, Dimitri P. (2009). Teoría de la optimización convexa . Atenas científica. 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.
• Cocinero, 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 minimización y análisis convexo, Volumen I: Fundamentos . Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]. vol. 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 los profesionales". Algoritmos de minimización y análisis convexo, Volumen II: Teoría avanzada y métodos de paquetes . Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]. vol. 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, Eugenio (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 . Apuntes de conferencias en informática (LNCS). vol. 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. S2CID  9048698.
• Minoux, Michel (1986). Programación matemática: Teoría y algoritmos . Egon Balas (delantero); Steven Vajda (traducción) del francés (1983 París: Dunod). Chichester: una publicación de Wiley-Interscience. John Wiley & Sons, Ltd. págs. xxviii + 489. ISBN 0-471-90170-9. MR  0868279. (2008 Segunda ed., en francés: Programmation mathématique: Théorie et algoritmos , É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-0-691-11915-1. SEÑOR  2199043.

Artículos

• Everett, Hugo III (1963). "Método multiplicador de Lagrange generalizado para la resolución de problemas de asignación óptima de recursos". La investigación de operaciones . 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, PO (agosto de 2007). "Relajación lagrangiana mediante métodos de subgradiente de paso de bola". Matemáticas de la Investigación de Operaciones . 32 (3): 669–686. doi :10.1287/moor.1070.0261. SEÑOR  2348241. Archivado desde el original el 26 de julio de 2011 . Consultado el 12 de mayo de 2011 .
• Dualidad en programación lineal Gary D. Knott