Optimizacion convexa

Subcampo de optimización matemática

La optimización convexa es un subcampo de la optimización matemática que estudia el problema de minimizar funciones convexas sobre conjuntos convexos (o, de manera equivalente, maximizar funciones cóncavas sobre conjuntos convexos). Muchas clases de problemas de optimización convexa admiten algoritmos de tiempo polinomial, ^[1] mientras que la optimización matemática es, en general, NP-hard . ^{[2] [3] [4]}

Definición

forma abstracta

Un problema de optimización convexa se define por dos ingredientes: ^{[5] [6]}

• La función objetivo , que es una función convexa de valor real de n variables, .; ${\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }$
• El conjunto factible , que es un subconjunto convexo . ${\displaystyle C\subseteq \mathbb {R} ^{n}}$

El objetivo del problema es encontrar algún logro. ${\displaystyle \mathbf {x^{\ast }} \in C}$

${\displaystyle \inf\{f(\mathbf {x} ):\mathbf {x} \in C\}}$.

En general, existen tres opciones respecto a la existencia de una solución: ^{[7] : cap.4}

• Si tal punto x * existe, se le denomina punto o solución óptima ; el conjunto de todos los puntos óptimos se llama conjunto óptimo ; y el problema se llama solucionable .
• Si es ilimitado por debajo de , o no se alcanza el mínimo, entonces se dice que el problema de optimización es ilimitado . ${\displaystyle f}$ ${\displaystyle C}$
• De lo contrario, si es el conjunto vacío, entonces se dice que el problema es inviable . ${\displaystyle C}$

Forma estándar

Un problema de optimización convexa está en forma estándar si se escribe como

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {x} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}}$

donde: ^{[7] : capítulo 4}

• ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$es el vector de variables de optimización;
• La función objetivo es una función convexa ; ${\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }$
• Las funciones de restricción de desigualdad , son funciones convexas; ${\displaystyle g_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle i=1,\ldots ,m}$
• Las funciones de restricción de igualdad , , son transformaciones afines , es decir, de la forma: , donde es un vector y es un escalar. ${\displaystyle h_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle i=1,\ldots ,p}$ ${\displaystyle h_{i}(\mathbf {x} )=\mathbf {a_{i}} \cdot \mathbf {x} -b_{i}}$ ${\displaystyle \mathbf {a_{i}} }$ ${\displaystyle b_{i}}$

El conjunto factible del problema de optimización consta de todos los puntos que satisfacen las restricciones de desigualdad e igualdad. Este conjunto es convexo porque es convexo, los conjuntos de subniveles de funciones convexas son convexos, los conjuntos afines son convexos y la intersección de conjuntos convexos es convexa. ^{[7] : capítulo 2} ${\displaystyle C}$ ${\displaystyle \mathbf {x} \in {\mathcal {D}}}$ ${\displaystyle {\mathcal {D}}}$

Muchos problemas de optimización pueden formularse de manera equivalente en esta forma estándar. Por ejemplo, el problema de maximizar una función cóncava se puede reformular de manera equivalente como el problema de minimizar la función convexa . El problema de maximizar una función cóncava sobre un conjunto convexo se denomina comúnmente problema de optimización convexa. ^[8] ${\displaystyle f}$ ${\displaystyle -f}$

Forma de epígrafe (forma estándar con objetivo lineal)

En la forma estándar es posible suponer, sin pérdida de generalidad, que la función objetivo f es una función lineal . Esto se debe a que cualquier programa con un objetivo general se puede transformar en un programa con un objetivo lineal agregando una sola variable t y una sola restricción, de la siguiente manera: ^{[9] : 1.4}

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} ,t}{\operatorname {minimize} }}&&t\\&\operatorname {subject\ to} &&f(\mathbf {x} )-t\leq 0\\&&&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}}$

forma cónica

Todo programa convexo se puede presentar en forma cónica , lo que significa minimizar un objetivo lineal sobre la intersección de un plano afín y un cono convexo: ^{[9] : 5.1}

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&c^{T}x\\&\operatorname {subject\ to} &&x\in (b+L)\cap K\end{aligned}}}$

donde K es un cono convexo puntiagudo cerrado , L es un subespacio lineal de R ⁿ y b es un vector en R ⁿ . Un programa lineal en forma estándar en el caso especial en el que K es el ortante no negativo de R ⁿ .

Eliminación de restricciones de igualdad lineal

Es posible convertir un programa convexo en forma estándar en un programa convexo sin restricciones de igualdad. ^{[7] : 132} Denota las restricciones de igualdad h _i ( x ) = 0 como Ax = b , donde A tiene n columnas. Si Ax = b es inviable, entonces, por supuesto, el problema original es inviable. De lo contrario, tiene alguna solución x ₀ y el conjunto de todas las soluciones se puede presentar como: Fz + x ₀ , donde z está en R ^k , k = n -rango( A ) y F es un n -por- k matriz. Sustituyendo x = Fz + x ₀ en el problema original se obtiene:

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\leq 0,\quad i=1,\dots ,m\\\end{aligned}}}$

donde las variables son z . Tenga en cuenta que hay menos variables de rango ( A ). Esto significa que, en principio, se puede restringir la atención a problemas de optimización convexos sin restricciones de igualdad. En la práctica, sin embargo, a menudo se prefiere conservar las restricciones de igualdad, ya que podrían hacer que algunos algoritmos sean más eficientes y también hacer que el problema sea más fácil de entender y analizar.

Casos especiales

Las siguientes clases de problemas son todos problemas de optimización convexa, o pueden reducirse a problemas de optimización convexa mediante transformaciones simples: ^{[7] : capítulo 4  [10]}

Una jerarquía de problemas de optimización convexa. (LP: programa lineal, QP: programa cuadrático, programa de cono de segundo orden SOCP, SDP: programa semidefinido, CP: programa de cono).

• Los problemas de programación lineal son los programas convexos más simples. En LP, las funciones objetivo y de restricción son todas lineales.
• La programación cuadrática es la siguiente más simple. En QP, todas las restricciones son lineales, pero el objetivo puede ser una función cuadrática convexa.
• La programación de conos de segundo orden es más general.
• La programación semidefinida es más general.
• La optimización cónica es aún más general; consulte la figura de la derecha.

Otros casos especiales incluyen;

• mínimos cuadrados
• Minimización cuadrática con restricciones cuadráticas convexas
• Programación geométrica
• Maximización de la entropía con restricciones apropiadas.

Propiedades

Las siguientes son propiedades útiles de los problemas de optimización convexa: ^{[11] [7] : cap.4}

• todo mínimo local es un mínimo global ;
• el conjunto óptimo es convexo;
• Si la función objetivo es estrictamente convexa, entonces el problema tiene como máximo un punto óptimo.

Estos resultados son utilizados por la teoría de la minimización convexa junto con nociones geométricas del análisis funcional (en espacios de Hilbert) como el teorema de proyección de Hilbert , el teorema del hiperplano de separación y el lema de Farkas . ^{[ cita necesaria ]}

Algoritmos

Problemas sin restricciones y con restricciones de igualdad

Los programas convexos más fáciles de resolver son los problemas sin restricciones o los problemas con restricciones únicamente de igualdad. Como todas las restricciones de igualdad son lineales, pueden eliminarse con álgebra lineal e integrarse en el objetivo, convirtiendo así un problema de igualdad restringida en uno sin restricciones.

En la clase de problemas sin restricciones (o con restricciones de igualdad), los más simples son aquellos en los que el objetivo es cuadrático . Para estos problemas, las condiciones KKT (que son necesarias para la optimización) son todas lineales, por lo que pueden resolverse analíticamente. ^{[7] : capítulo 11}

Para problemas sin restricciones (o con restricciones de igualdad) con un objetivo convexo general que es dos veces diferenciable, se puede utilizar el método de Newton . Puede verse como una reducción de un problema convexo general sin restricciones a una secuencia de problemas cuadráticos. ^{[7] : capítulo 11.} El método de Newton se puede combinar con la búsqueda de líneas para un tamaño de paso apropiado y se puede demostrar matemáticamente que converge rápidamente.

Otros algoritmos eficientes para la minimización sin restricciones son el descenso de gradiente (un caso especial de descenso más pronunciado ).

Problemas generales

Los problemas más desafiantes son aquellos que tienen restricciones de desigualdad. Una forma común de resolverlos es reducirlos a problemas sin restricciones agregando una función de barrera , que imponga las restricciones de desigualdad, a la función objetivo. Estos métodos se denominan métodos de puntos interiores . ^{[7] : capítulo 11} Deben inicializarse encontrando un punto interior factible utilizando los llamados métodos de fase I , que encuentran un punto factible o muestran que no existe ninguno. Los métodos de la Fase I generalmente consisten en reducir la búsqueda en cuestión a un problema de optimización convexo más simple. ^{[7] : capítulo 11}

Los problemas de optimización convexa también se pueden resolver mediante los siguientes métodos contemporáneos: ^[12]

• Métodos de paquete (Wolfe, Lemaréchal, Kiwiel) y
• Métodos de proyección subgradiente (Polyak),
• Métodos de punto interior , ^[1] que utilizan funciones de barrera autoconcordantes ^[13] y funciones de barrera autorreguladas. ^[14]
• Métodos de plano de corte
• método elipsoide
• Método de subgradiente
• Subgradientes duales y el método de deriva más penalización

Los métodos de subgradiente se pueden implementar de forma sencilla y por eso se utilizan ampliamente. ^[15] Los métodos de subgradiente dual son métodos de subgradiente aplicados a un problema dual . El método de deriva más penalización es similar al método de subgradiente dual, pero toma un promedio temporal de las variables primarias. ^{[ cita necesaria ]}

Multiplicadores de Lagrange

Considere un problema de minimización convexo dado en forma estándar mediante una función de costos y restricciones de desigualdad para . Entonces el dominio es: ${\displaystyle f(x)}$ ${\displaystyle g_{i}(x)\leq 0}$ ${\displaystyle 1\leq i\leq m}$ ${\displaystyle {\mathcal {X}}}$

${\displaystyle {\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leq 0\right\}.}$

La función lagrangiana para el problema es

${\displaystyle L(x,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})=\lambda _{0}f(x)+\lambda _{1}g_{1}(x)+\cdots +\lambda _{m}g_{m}(x).}$

Para cada punto que minimiza sobre , existen números reales llamados multiplicadores de Lagrange , que satisfacen estas condiciones simultáneamente: ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m},}$

1. ${\displaystyle x}$minimiza sobre todo ${\displaystyle L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})}$ ${\displaystyle y\in X,}$
2. ${\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geq 0,}$con al menos uno ${\displaystyle \lambda _{k}>0,}$
3. ${\displaystyle \lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0}$(flacidez complementaria).

Si existe un "punto estrictamente factible", es decir, un punto que satisfaga ${\displaystyle z}$

${\displaystyle g_{1}(z),\ldots ,g_{m}(z)<0,}$

entonces la afirmación anterior puede reforzarse para exigir eso . ${\displaystyle \lambda _{0}=1}$

Por el contrario, si algo satisface (1)–(3) para escalares con entonces es seguro que se minimizará sobre . ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle \lambda _{0},\ldots ,\lambda _{m}}$ ${\displaystyle \lambda _{0}=1}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle X}$

Software

Existe un gran ecosistema de software para la optimización convexa. Este ecosistema tiene dos categorías principales: solucionadores por un lado y herramientas de modelado (o interfaces ) por otro.

Los solucionadores implementan los algoritmos ellos mismos y generalmente están escritos en C. Requieren que los usuarios especifiquen problemas de optimización en formatos muy específicos que pueden no ser naturales desde una perspectiva de modelado. Las herramientas de modelado son piezas de software independientes que permiten al usuario especificar una optimización en una sintaxis de nivel superior. Gestionan todas las transformaciones hacia y desde el modelo de alto nivel del usuario y el formato de entrada/salida del solucionador.

La siguiente tabla muestra una combinación de herramientas de modelado (como CVXPY y Convex.jl) y solucionadores (como CVXOPT y MOSEK). Esta tabla no es en modo alguno exhaustiva.

Aplicaciones

La optimización convexa se puede utilizar para modelar problemas en una amplia gama de disciplinas, como sistemas de control automático , estimación y procesamiento de señales , comunicaciones y redes, diseño de circuitos electrónicos , ^{[7] : 17} análisis y modelado de datos, finanzas , estadística ( experimental óptimo). diseño ), ^[20] y optimización estructural , donde el concepto de aproximación ha demostrado ser eficiente. ^{[7] [21]} La optimización convexa se puede utilizar para modelar problemas en los siguientes campos:

• Optimización de cartera . ^[22]
• Análisis de riesgos en el peor de los casos. ^[22]
• Publicidad óptima. ^[22]
• Variaciones de la regresión estadística (incluida la regularización y la regresión cuantil ). ^[22]
• Ajuste de modelos ^[22] (particularmente clasificación multiclase ^[23] ).
• Optimización de la generación eléctrica . ^[23]
• Optimización combinatoria . ^[23]
• Modelización no probabilística de la incertidumbre . ^[24]
• Localización mediante señales inalámbricas ^[25]

Extensiones

Las extensiones de la optimización convexa incluyen la optimización de funciones biconvexas , pseudoconvexas y cuasiconvexas . Las extensiones de la teoría del análisis convexo y los métodos iterativos para resolver aproximadamente problemas de minimización no convexos ocurren en el campo de la convexidad generalizada , también conocido como análisis convexo abstracto. ^{[ cita necesaria ]}

Ver también

• Dualidad
• Condiciones de Karush-Kuhn-Tucker
• Problema de optimizacion
• Método de gradiente proximal
• Problemas algorítmicos en conjuntos convexos.

Notas

1. Nesterov y Nemirovskii 1994
2. Murty, Katta; Kabadi, Santosh (1987). "Algunos problemas NP-completos en programación cuadrática y no lineal". Programación Matemática . 39 (2): 117-129. doi :10.1007/BF02592948. hdl : 2027.42/6740 . S2CID  30500771.
3. Sahni, S. "Problemas relacionados con la computación", en SIAM Journal on Computing, 3, 262-279, 1974.
4. La programación cuadrática con un valor propio negativo es NP-duro, Panos M. Pardalos y Stephen A. Vavasis en Journal of Global Optimization , Volumen 1, Número 1, 1991, páginas 15-22.
5. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1996). Algoritmos de análisis y minimización convexos: Fundamentos. pag. 291.ISBN _ 9783540568506.
6. Ben-Tal, Aharon; Nemirovskiĭ, Arkadiĭ Semenovich (2001). Conferencias sobre optimización convexa moderna: análisis, algoritmos y aplicaciones de ingeniería. págs. 335–336. ISBN 9780898714913.
7. Boyd, Stephen; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Prensa de la Universidad de Cambridge . ISBN 978-0-521-83378-3. Consultado el 12 de abril de 2021 .
8. "Tipos de problemas de optimización: optimización convexa". 9 de enero de 2011.
9. Arkadi Nemirovsky (2004). Métodos de tiempo polinómico de puntos interiores en programación convexa.
10. Agrawal, Akshay; Verschueren, Robin; Diamante, Steven; Boyd, Stephen (2018). "Un sistema de reescritura para problemas de optimización convexa" (PDF) . Control y Decisión . 5 (1): 42–60. arXiv : 1709.04494 . doi :10.1080/23307706.2017.1397554. S2CID  67856259.
11. Rockafellar, R. Tyrrell (1993). "Multiplicadores de Lagrange y optimización" (PDF) . Revisión SIAM . 35 (2): 183–238. CiteSeerX 10.1.1.161.7209 . doi :10.1137/1035044. 
12. Para conocer los métodos de minimización convexa, consulte los volúmenes de Hiriart-Urruty y Lemaréchal (paquete) y los libros de texto de Ruszczyński , Bertsekas y Boyd y Vandenberghe (punto interior).
13. Nesterov, Yurii; Arkadii, Nemirovskii (1995). Algoritmos polinomiales de punto interior en programación convexa . Sociedad de Matemática Industrial y Aplicada. ISBN 978-0898715156.
14. Peng, Jiming; Roos, Cornelis; Terlaky, Tamás (2002). "Funciones autorreguladoras y nuevas direcciones de búsqueda para optimización lineal y semidefinida". Programación Matemática . 93 (1): 129-171. doi :10.1007/s101070200296. ISSN  0025-5610. S2CID  28882966.
15. "Optimización numérica". Serie Springer en Investigación de Operaciones e Ingeniería Financiera . 2006. doi :10.1007/978-0-387-40065-5.
16. Borchers, Brian. "Una descripción general del software para la optimización convexa" (PDF) . Archivado desde el original (PDF) el 18 de septiembre de 2017 . Consultado el 12 de abril de 2021 .
17. "Bienvenido a CVXPY 1.1 - documentación de CVXPY 1.1.11". www.cvxpy.org . Consultado el 12 de abril de 2021 .
18. Udell, Madeleine; Mohan, Karanveer; Zeng, David; Hong, Jenny; Diamante, Steven; Boyd, Stephen (17 de octubre de 2014). "Optimización convexa en Julia". arXiv : 1410.4821 [matemáticas.OC].
19. "Optimización convexa disciplinada - CVXR". www.cvxgrp.org . Consultado el 17 de junio de 2021 .
20. Chritensen/Klarbring, cap. 4.
21. Schmit, Luisiana; Fleury, C. 1980: Síntesis estructural combinando conceptos de aproximación y métodos duales . J.Amer. Inst. Aeronauta. Astronauta 18, 1252-1260
22. , Stephen; Diamante, Esteban; Zhang, Junzi; Agrawal, Akshay. "Aplicaciones de optimización convexa" (PDF) . Archivado (PDF) desde el original el 1 de octubre de 2015 . Consultado el 12 de abril de 2021 .
23. Malick, Jérôme (28 de septiembre de 2011). "Optimización convexa: aplicaciones, formulaciones, relajaciones" (PDF) . Archivado (PDF) desde el original el 12 de abril de 2021 . Consultado el 12 de abril de 2021 .
24. Ben Haim Y. y Elishakoff I., Modelos convexos de incertidumbre en mecánica aplicada, Elsevier Science Publishers, Amsterdam, 1990
25. Ahmad Bazzi, Dirk TM Slock y Lisa Meilhac. "Estimación del ángulo de llegada en línea en presencia de acoplamiento mutuo". 2016 Taller de procesamiento estadístico de señales (SSP) del IEEE. IEEE, 2016.

Referencias

• Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Análisis y optimización convexos . Belmont, MA .: Athena Scientific. ISBN 978-1-886529-45-8.
• Bertsekas, Dimitri P. (2009). Teoría de la optimización convexa . Belmont, MA .: Athena Scientific. ISBN 978-1-886529-31-1.
• Bertsekas, Dimitri P. (2015). Algoritmos de optimización convexa . Belmont, MA .: Athena Scientific. ISBN 978-1-886529-28-1.
• Borwein, Jonathan; Lewis, Adrián (2000). Análisis convexo y optimización no lineal: teoría y ejemplos, segunda edición (PDF) . Saltador . Consultado el 12 de abril de 2021 .
• Christensen, Peter W.; Anders Klarbring (2008). Una introducción a la optimización estructural. vol. 153. Medios de ciencia y negocios de Springer. ISBN 9781402086663.

• Hiriart-Urruty, Jean-Baptiste y Lemaréchal, Claude . (2004). Fundamentos del análisis convexo . Berlín: Springer.
• 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 978-3-540-56850-6. SEÑOR  1261420.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). 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 978-3-540-56852-0. SEÑOR  1295240.
• Kiwiel, Krzysztof C. (1985). Métodos de descenso para optimización no diferenciable . Apuntes de conferencias de matemáticas. Nueva York: Springer-Verlag. ISBN 978-3-540-15642-0.
• Lemaréchal, Claude (2001). "Relajación lagrangiana". En Michael Jünger y Denis Naddef (ed.). 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 sobre informática. vol. 2241. Berlín: Springer-Verlag. págs. 112-156. doi :10.1007/3-540-45586-8_4. ISBN 978-3-540-42877-0. SEÑOR  1900016. S2CID  9048698.
• Nesterov, Yurii; Nemirovskii, Arkadii (1994). Métodos polinomiales de puntos interiores en programación convexa . SIAM.
• Nésterov, Yurii. (2004). Conferencias introductorias sobre optimización convexa , Kluwer Academic Publishers
• Rockafellar, RT (1970). Análisis convexo . Princeton: Prensa de la Universidad de Princeton.

• Ruszczyński, Andrzej (2006). Optimización no lineal . Prensa de la Universidad de Princeton.
• Schmit, Luisiana; Fleury, C. 1980: Síntesis estructural combinando conceptos de aproximación y métodos duales . J.Amer. Inst. Aeronauta. Astronauta 18, 1252-1260

enlaces externos

• EE364a: Optimización convexa I y EE364b: Optimización convexa II, páginas de inicio de cursos de Stanford
• 6.253: Análisis y optimización convexos, una página de inicio del curso OCW del MIT
• Brian Borchers, una descripción general del software para la optimización convexa.
• Libro de optimización convexa de Lieven Vandenberghe y Stephen P. Boyd