Optimización convexa

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, equivalentemente, 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]}

Un problema de optimización convexa se define mediante 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 }} \en C}$

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

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

• Si existe tal punto x *, se habla de punto óptimo o solución ; el conjunto de todos los puntos óptimos se denomina conjunto óptimo ; y el problema se denomina solucionable .
• Si no tiene límites por debajo de , o no se alcanza el ínfimo, entonces se dice que el problema de optimización no tiene límites .${\estilo de visualización f}$${\estilo de visualización C}$
• De lo contrario, si es el conjunto vacío, entonces se dice que el problema es inviable .${\estilo de visualización C}$

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

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimizar} }}&&f(\mathbf {x} )\\&\operatorname {sujeto\ a} &&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.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,\lpuntos ,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,\lpuntos ,p}$${\displaystyle h_{i}(\mathbf {x} )=\mathbf {a_{i}} \cdot \mathbf {x} -b_{i}}$${\displaystyle \mathbf {a_{i}}}$$Estilo de visualización b_{i}$

El conjunto factible del problema de optimización está formado por 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.2}${\estilo de visualización C}$${\displaystyle \mathbf {x} \in {\mathcal {D}}}$${\displaystyle {\mathcal {D}}}$

Muchos problemas de optimización pueden formularse de forma equivalente en esta forma estándar. Por ejemplo, el problema de maximizar una función cóncava puede reformularse de forma 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}$

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 puede transformarse en un programa con un objetivo lineal añadiendo una única variable t y una única 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}}}$

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 ⁿ .

Es posible convertir un programa convexo en forma estándar, a un programa convexo sin restricciones de igualdad. ^{[7] : 132} Denotemos 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 puede presentarse como: Fz + x ₀ , donde z está en R ^k , k = n -rank( A ), y F es una matriz n -por- k . Sustituyendo x = Fz + x ₀ en el problema original obtenemos:

${\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 . Nótese que hay rank( A ) menos variables. Esto significa que, en principio, se puede restringir la atención a problemas de optimización convexa sin restricciones de igualdad. En la práctica, sin embargo, a menudo se prefiere conservar las restricciones de igualdad, ya que pueden hacer que algunos algoritmos sean más eficientes y también que el problema sea más fácil de entender y analizar.

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

• Los problemas de programación lineal son los programas convexos más simples. En programación lineal, las funciones objetivo y de restricción son todas lineales.
• La programación cuadrática es la segunda más sencilla. En la programación cuadrática, las restricciones son todas 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 a 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.

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

• Cada 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 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 separador y el lema de Farkas . ^{[ cita requerida ]}

Los programas convexos más fáciles de resolver son los problemas sin restricciones , o los problemas con solo restricciones de igualdad. Como las restricciones de igualdad son todas lineales, se pueden eliminar con álgebra lineal e integrar en el objetivo, convirtiendo así un problema con restricciones de igualdad 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 optimalidad) son todas lineales, por lo que se pueden resolver analíticamente. ^{[7] : cap.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 la reducción de un problema convexo general sin restricciones a una secuencia de problemas cuadráticos. ^{[7] : cap.11} El método de Newton se puede combinar con la búsqueda de línea 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 ).

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

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

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

Los métodos de subgradiente se pueden implementar de manera sencilla y, por lo tanto, se utilizan ampliamente. ^[15] Los métodos de subgradiente duales 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 requerida ]}

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (April 2021) (Learn how and when to remove this message)

Consideremos un problema de minimización convexa dado en forma estándar por una función de costo 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 en que se minimiza sobre , existen números reales llamados multiplicadores de Lagrange , que satisfacen simultáneamente estas condiciones:${\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}$(flojedad complementaria).

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

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

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

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

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 el otro.

Los solucionadores implementan los algoritmos por sí mismos y suelen estar escritos en C. Requieren que los usuarios especifiquen los 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 exhaustiva.

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 ( diseño experimental óptimo ), ^[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 riesgo 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] (en particular, clasificación multiclase ^[23] ).
• Optimización de la generación de electricidad . ^[23]
• Optimización combinatoria . ^[23]
• Modelado no probabilístico de la incertidumbre . ^[24]
• Localización mediante señales inalámbricas ^[25]

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 de forma aproximada problemas de minimización no convexa se dan en el campo de la convexidad generalizada , también conocida como análisis convexo abstracto. ^{[ cita requerida ]}

• Dualidad
• Condiciones de Karush-Kuhn-Tucker
• Problema de optimización
• Método del gradiente proximal
• Problemas algorítmicos sobre conjuntos convexos

• Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Análisis y optimización convexa . Belmont, MA.: Athena Scientific. ISBN 978-1-886529-45-8.
• Bertsekas, Dimitri P. (2009). Teoría de 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, Adrian (2000). Análisis convexo y optimización no lineal: teoría y ejemplos, segunda edición (PDF) . Springer . Consultado el 12 de abril de 2021 .
• Christensen, Peter W.; Anders Klarbring (2008). Introducción a la optimización estructural. Vol. 153. Springer Science & Business Media. 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. Sr.  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 descendencia para optimización no diferenciable . Apuntes de clase 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.
• Nesterov, Yurii. (2004). Lecciones introductorias sobre optimización convexa , Kluwer Academic Publishers
• Rockafellar, RT (1970). Análisis convexo . Princeton: Princeton University Press.

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

Wikimedia Commons tiene medios relacionados con Optimización convexa .

• 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, página de inicio del curso MIT OCW
• Brian Borchers, Una descripción general del software para optimización convexa
• Libro de optimización convexa de Lieven Vandenberghe y Stephen P. Boyd