Dualidad (optimización)

Principio de optimización matemática

En la teoría de optimización matemática , la dualidad o principio de dualidad es el principio según el cual los problemas de optimización pueden verse desde cualquiera de dos perspectivas, el problema primal 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 para el problema primal (de minimización) es al menos tan grande como cualquier solución factible para el problema dual (de maximización). Por lo tanto, la solución del primal es un límite superior para la solución del dual, y la solución del dual es un límite inferior para la solución del primal. ^[1] Este hecho se llama dualidad débil .

En general, los valores óptimos de los problemas primal y dual no tienen por qué ser iguales. Su diferencia se denomina brecha de dualidad . En el caso de los problemas de optimización convexa , la brecha de dualidad es cero bajo una condición de calificación de restricción . Este hecho se denomina dualidad fuerte .

Problema dual

Por lo general, el término "problema dual" se refiere al problema dual de Lagrange , pero también 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 utilizando multiplicadores de Lagrange no negativos para agregar 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 de las variables duales (incluidas al menos las restricciones de no negatividad).

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 se alcanza el ínfimo (máximo límite inferior) de la función. ${\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 existen condiciones de restricción, estas pueden construirse en la función dejando donde es una función adecuada en que tiene un mínimo 0 en las restricciones, y para la cual se puede probar que . La última condición se satisface trivialmente, pero no siempre convenientemente, para la función característica (es decir, para satisfacer las restricciones y en otros casos). Luego, se extiende 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 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 (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 solo si se cumple la dualidad fuerte . De lo contrario, la brecha es estrictamente positiva y se cumple la dualidad débil . ^[5] ${\displaystyle d^{*}}$ ${\displaystyle p^{*}}$ ${\displaystyle p^{*}-d^{*}}$

En optimización computacional, a menudo se informa de 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 factible pero subóptima actual 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 envoltura convexa cerrada y al reemplazar una función no convexa con su clausura convexa , es decir, la función que tiene el epígrafe que es la envoltura 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 primal, la función objetivo es una combinación lineal de n variables. Hay m restricciones, cada una de las cuales impone un límite superior a 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 impone un límite inferior a una combinación lineal de m variables duales.

Relación entre el problema primal y el problema dual

En el caso lineal, en el problema primal, desde cada punto subóptimo que satisface todas las restricciones, hay una dirección o subespacio de direcciones hacia donde 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 problema 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, se minimiza el vector dual 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 hace formal mediante las ecuaciones de la 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 garantizar 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 de nivel inferior compactos. Esta 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 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.

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 restricciones, 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, e I[u]=∞ en caso contrario. Pero J ( x ) es difícil de resolver ya que no es continua. 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)}$

Nótese 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 al tomar λ = 0, y su valor es entonces f(x);
• Si x viola alguna restricción, f _i ( x )>0 para algún i , entonces L(x, λ )→∞ cuando λ _i →∞ .

Por lo tanto, el problema original es equivalente a:

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

Invirtiendo el orden de min y max, obtenemos:

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

La función dual es el problema interno en 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 una cota inferior para la solución óptima del programa original (primario); este es el principio de dualidad débil . Si el problema primal es convexo y acotado desde abajo, y existe un punto en el que se satisfacen estrictamente todas las restricciones no lineales ( condición de Slater ), entonces la solución óptima del programa dual es igual a la solución óptima del programa primal; este es el principio de dualidad fuerte . En este caso, podemos resolver el programa primal hallando una solución óptima λ * para el programa dual, y luego resolviendo:

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

Nótese que, para utilizar el principio de dualidad débil o fuerte, necesitamos una forma de calcular g( λ ). En general, esto puede ser 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 primal 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 para la dualidad . ^{[18] : Sub.3.3.1}

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

El principio fuerte 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}}}$

con el dominio que tiene 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 ínfimo puntual de funciones afines. La función dual produce límites inferiores para el valor óptimo del problema inicial; para cualquier y cualquier 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 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 convexa 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 ínfimo se da 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 denomina 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 es típicamente un problema de optimización no convexo. En cualquier caso, se cumple la 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 señaló que estaba usando información de su teoría de juegos y conjeturó que el juego de matriz de suma cero para dos personas era equivalente a la programación lineal. Albert W. Tucker y su grupo publicaron por primera vez demostraciones 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 primal 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.

Véase también

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

Notas

1. Boyd, Stephen P.; Vandenberghe, Lieven (2004). Optimización convexa (pdf) . Cambridge University Press. pág. 216. ISBN 978-0-521-83378-3. Recuperado 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). Superando el fracaso de las condiciones clásicas de regularidad generalizada de punto interior en la optimización convexa. Aplicaciones de la teoría de dualidad a ampliaciones de operadores monótonos máximos . Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3.
4. Zălinescu, Constantin (2002). Análisis convexo en espacios vectoriales generales . River Edge, NJ: World Scientific Publishing Co., Inc., págs. 106-113. ISBN 981-238-067-1.Señor 1921556  .
5. Borwein, Jonathan; Zhu, Qiji (2005). Técnicas de análisis variacional . Springer. 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 convexa . Athena Scientific. ISBN 1-886529-45-0.
8. Bertsekas, Dimitri P. (1999). Programación no lineal (2.ª ed.). Athena Scientific. ISBN 1-886529-00-0.
9. Bertsekas, Dimitri P. (2009). Teoría de optimización convexa . Athena Scientific. 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. pp. 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. Sr.  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 de Macmillan de 1970]. Teoría de optimización para sistemas grandes . 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 (prólogo); Steven Vajda (trad.) del francés (1983, París: Dunod). Chichester: A Wiley-Interscience Publication. 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]. pp. xvi+388. ISBN 0-471-77886-9.Sr. 0544669  .
17. David Knowles (2010). "Dualidad lagrangiana para principiantes" (PDF) .
18. Nemirovsky y Ben-Tal (2023). "Optimización III: Optimización convexa" (PDF) .
19. Geoffrion, Arthur M. (1971). "Dualidad en programación no lineal: un desarrollo simplificado orientado a aplicaciones". SIAM Review . 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 convexa . 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 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. pp. 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 & Sons. ISBN 0-471-55894-X.
• Dantzig, George B. (1963). Programación lineal y extensiones . Princeton, NJ: 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. Sr.  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 de Macmillan de 1970]. Optimization theory for large systems [Teoría de optimización para sistemas grandes ] . 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 . 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 (prólogo); Steven Vajda (trad.) del francés (1983, París: Dunod). Chichester: A Wiley-Interscience Publication. 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: Academic Press. 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, NJ: Princeton University Press . pp. xii+454. ISBN 978-0-691-11915-1.Sr. 2199043  .

Artículos

• Everett, Hugh III (1963). "Método generalizado de multiplicadores de Lagrange para resolver problemas de asignación óptima de recursos". Investigación de operaciones . 11 (3): 399–417. doi :10.1287/opre.11.3.399. JSTOR  168028. MR  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 mediante métodos de subgradiente ballstep". Matemáticas de la investigación de operaciones . 32 (3): 669–686. doi :10.1287/moor.1070.0261. MR  2348241. Archivado desde el original el 26 de julio de 2011 . Consultado el 12 de mayo de 2011 .
• Dualidad en la programación lineal Gary D. Knott