Programación convexa

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 21 de noviembre de 2021; las comprobaciones requieren 2 ediciones .

La programación convexa es un subcampo de la optimización matemática que estudia el problema de minimizar funciones convexas en conjuntos convexos . Mientras que muchas clases de problemas de programación convexa admiten algoritmos de tiempo polinomial [1] , la optimización matemática es generalmente NP-difícil [2] [3] [4] .

La programación convexa tiene aplicaciones en una variedad de disciplinas, como sistemas de control automático , evaluación y procesamiento de señales , comunicaciones y redes, circuitos [5] , análisis y modelado de datos, finanzas , estadísticas ( diseño óptimo de experimentos ) [6] y optimización estructural [7] . El desarrollo de la tecnología informática y los algoritmos de optimización ha hecho que la programación convexa sea casi tan simple como la programación lineal [8] .

Definición

Un problema de programación convexa es un problema de optimización en el que la función objetivo es una función convexa y el dominio de soluciones factibles es convexo . Una función que asigna algún subconjunto a es convexa si el dominio es convexo tanto para todos como para todos en su dominio de . Un conjunto es convexo si para todos sus elementos y alguno de ellos también pertenece al conjunto. $F$ $\mathbb{R} ^{n}$ ${\displaystyle \mathbb {R} \cup \{\pm \infty \))$ ${\ estilo de visualización \ theta \ en [0,1]}$ $x,y$ $f(\theta x+(1-\theta )y)\leqslant \theta f(x)+(1-\theta )f(y)$ $x,y$ ${\ estilo de visualización \ theta \ en [0,1]}$ ${\ estilo de visualización \ theta x + (1- \ theta) y}$

En particular, el problema de la programación convexa es el problema de encontrar algún , en el que $\mathbf {x^{\ast}} \in C$

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

donde la función objetivo es convexa, al igual que el conjunto de soluciones factibles [9] [10] . Si tal punto existe, se llama el punto óptimo . El conjunto de todos los puntos óptimos se llama conjunto óptimo . Si no se alcanza el límite o no se alcanza el mínimo , se dice que la optimización es ilimitada . Si está vacío, se habla de una tarea inaceptable [11] . $F$ $C$ $F$ $C$ $C$

Forma estándar

Se dice que un problema de programación convexa está en forma estándar si se escribe como

Minimizar

{\ estilo de visualización f (\ mathbf {x})}

Bajo condiciones

{\begin{alineado}&&g_{i}(\mathbf {x} )\leqslant 0,\quad i=1,\dots ,m\\&&h_{i}(\mathbf {x} )=0, \quad i=1,\puntos,p,\end{alineado}}

donde es la variable de optimización, las funciones son convexas y las funciones son afines [11] . $x \in \mathbb{R}^n$ ${\displaystyle f,g_{1},\ldots,g_{m))$ ${\displaystyle h_{1},\ldots,h_{p))$

En estos términos, la función es la función objetivo del problema, y las funciones y se denominan funciones de restricción. El conjunto admisible de soluciones al problema de optimización es el conjunto formado por todos los puntos que satisfacen las condiciones y . Este conjunto es convexo porque los conjuntos de subnivel de una función convexa son convexos, los conjuntos afines también son convexos y la intersección de conjuntos convexos es un conjunto convexo [12] . $F$ $soldado americano$ $hola}$ $x \in \mathbb{R}^n$ $g_{1}(x)\leqslant 0,\ldots,g_{m}(x)\leqslant 0$ $h_{1}(x)=0,\ldots,h_{p}(x)=0$

Muchos problemas de optimización se pueden reducir a 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 una función convexa , de modo que el problema de maximizar una función cóncava en un conjunto convexo a menudo se denomina problema de programación convexa. $F$ ${\ estilo de visualización -f}$

Propiedades

Propiedades útiles de problemas de programación convexa [13] [11] :

cualquier mínimo local es un mínimo global ;
el conjunto óptimo es convexo;
si la función objetivo es fuertemente convexa, el problema tiene como máximo un punto óptimo.

Estos resultados se utilizan en la teoría de minimización convexa, junto con conceptos geométricos del análisis funcional (en espacios de Hilbert ), como el teorema de proyección de Hilbert , el teorema del hiperplano de apoyo y el lema de Farkas .

Ejemplos

Las siguientes clases de problemas son problemas de programación convexa o pueden reducirse a problemas de programación convexa mediante transformaciones simples [11] [14] :

Método de mínimos cuadrados
Programación lineal
Optimización cuadrática convexa con restricciones lineales
Programación cuadrática en restricciones cuadráticas
Optimización cónica
programación geométrica
Programación de cónicas en un cono de segundo orden
Programación semidefinida
Principio de máxima entropía con las restricciones apropiadas

Método de los multiplicadores de Lagrange

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

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

Función de Lagrange para el problema

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 cualquier punto que se minimice a , existen números reales , llamados multiplicadores de Lagrange , para los que se cumplen simultáneamente las siguientes condiciones: $X$ $X$ $F$ $X$ ${\ estilo de visualización \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m},}$

$X$ minimiza sobre todo $L(y,\lambda _{0},\lambda _{1},\ldots,\lambda _{m})$ ${\ estilo de visualización y \ en X,}$
${\ estilo de visualización \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m} \ geqslant 0,}$ con al menos uno ${\ estilo de visualización \ lambda _ {k}> 0,}$
$\lambda_{1}g_{1}(x)=\cdots =\lambda_{m}g_{m}(x)=0$ (falta de rigidez complementaria).

Si existe un "punto fuerte admisible", es decir, un punto que satisface $z$

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

entonces la declaración anterior se puede fortalecer para requerir . ${\ estilo de visualización \ lambda _ {0} = 1}$

Por el contrario, si alguno de satisface las condiciones (1)-(3) para escalares con , entonces definitivamente se minimiza en . $X$ $X$ ${\ estilo de visualización \ lambda _ {0}, \ ldots, \ lambda _ {m}}$ ${\ estilo de visualización \ lambda _ {0} = 1}$ $X$ $F$ $X$

Algoritmos

Los problemas de programación convexa se resuelven mediante los siguientes métodos modernos: [15]

Métodos de haz subgradiente } (Wolf, Lemerical, Kivel),
Métodos de proyección de subgradiente (Polyak),
Método de punto interior [1] utilizando funciones de barrera autoconsistentes [16] y funciones de barrera autorreguladas [17] .
Método del plano de corte
método elipsoide
Métodos de subgradiente
Subgradientes de deriva y el método de deriva+penalización

Los métodos de subgradiente se pueden implementar simplemente porque son ampliamente utilizados [18] [19] . Los métodos de subgradiente dual son métodos de subgradiente aplicados a un problema dual . El método de deriva+penalización es similar al método de subgradiente dual, pero utiliza el promedio temporal de las principales variables.

Extensiones

Las extensiones a la programación convexa incluyen optimizaciones para funciones biconvexas , pseudoconvexas y cuasiconvexas . Las extensiones a la teoría del análisis convexo y los métodos iterativos para la solución aproximada de problemas de optimización no convexos ocurren en el campo de la convexidad generalizada , conocido como análisis convexo abstracto.

Véase también

Notas

↑ 1 2 Nesterov y Nemirovskii, 1994 .
↑ Murty y Kabadi 1987 , pág. 117–129.
↑ Sahni, 1974 , pág. 262-279.
↑ Pardalos y Vavasis, 1991 , p. 15-22.
↑ Boyd y Vandenberghe 2004 , pág. 17
↑ Christensen, Klarbring, 2008 , pág. cap. cuatro
↑ Boyd, Vandenberghe, 2004 .
↑ Boyd y Vandenberghe 2004 , pág. ocho.
↑ Hiriart-Urruty, Lemaréchal, 1996 , p. 291.
↑ Ben-Tal, Nemirovskiĭ, 2001 , p. 335–336.
↑ 1 2 3 4 Boyd, Vandenberghe, 2004 , pág. cap. cuatro
↑ Boyd y Vandenberghe 2004 , pág. cap. 2.
↑ Rockafellar, 1993 , p. 183–238.
↑ Agrawal, Verschueren, Diamond, Boyd, 2018 , pág. 42–60.
↑ Para conocer los métodos de programación convexa, consulte los libros de Irriart-Urruti y Lemerical (varios libros) y los libros de Rushczynski, Bercekas y Boyd y Vanderberge (métodos de puntos interiores).
↑ Nésterov, Nemirovskii, 1995 .
↑ Peng, Roos, Terlaky, 2002 , pág. 129–171.
↑ Bertsekas, 2009 .
↑ Bertsekas, 2015 .

Literatura

Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Algoritmos de minimización y análisis convexo: Fundamentos . - 1996. - ISBN 9783540568506 .
Aharon Ben-Tal, Arkadi Semenovich Nemirovskiĭ. Conferencias sobre optimización convexa moderna: análisis, algoritmos y aplicaciones de ingeniería . - 2001. - ISBN 9780898714913 .
Katta Murty, Santosh Kabadi. Algunos problemas NP-completos en programación cuadrática y no lineal // Programación Matemática. - 1987. - T. 39 , núm. 2 . — págs. 117–129 . -doi : 10.1007/ BF02592948 .
Sahni S. Problemas relacionados con la computación // SIAM Journal on Computing. - 1974. - Edición. 3 .
Panos M. Pardalos, Stephen A. Vavasis. La programación cuadrática con un valor propio negativo es NP-hard // Journal of Global Optimization. - 1991. - T. 1 , N º 1 .
R. Tyrrell Rockafellar. Análisis convexo . — Princeton: Prensa de la Universidad de Princeton, 1970.
R. Tyrrell Rockafellar. Multiplicadores de Lagrange y optimalidad // Revista SIAM. - 1993. - T. 35 , núm. 2 . -doi : 10.1137/ 1035044 .
Akshay Agrawal, Robin Verschueren, Steven Diamond, Stephen Boyd. Un sistema de reescritura para problemas de optimización convexa // Control y Decisión. - 2018. - V. 5 , n. 1 . -doi : 10.1080/ 23307706.2017.1397554 .
Yurii Nesterov, Arkadii Nemirovskii. Algoritmos polinómicos de punto interior en programación convexa. - Sociedad de Matemáticas Industriales y Aplicadas, 1995. - ISBN 978-0898715156 .
Yurii Nesterov, Arkadii Nemirovskii. Métodos de polinomios de puntos interiores en programación convexa. - SIAM, 1994. - V. 13. - (Estudios en Matemática Aplicada y Numérica). - ISBN 978-0-89871-319-0 .
Yuri Nésterov. Conferencias introductorias sobre optimización convexa. - Boston, Dordrecht, Londres: Kluwer Academic Publishers, 2004. - T. 87. - (Optimización aplicada). — ISBN 1-4020-7553-7 .
Jiming Peng, Cornelis Roos, Tamás Terlaky. Funciones autorreguladas y nuevas direcciones de búsqueda para optimización lineal y semidefinida // Programación Matemática. - 2002. - T. 93 , núm. 1 . — ISSN 0025-5610 . -doi : 10.1007/ s101070200296 .
Dimitri P. Bertsekas, Angelia Nedic, Asuman Ozdaglar. Análisis y Optimización Convexa. - Athena Scientific, 2003. - ISBN 978-1-886529-45-8 .
Dimitri P. Bertsekas. Teoría de la optimización convexa. - Belmont, MA.: Athena Scientific, 2009. - ISBN 978-1-886529-31-1 .
Dimitri P. Bertsekas. Algoritmos de optimización convexa. - Belmont, MA.: Athena Scientific, 2015. - ISBN 978-1-886529-28-1 .
Stephen P. Boyd, Lieven Vandenberghe. Optimización convexa . - Prensa de la Universidad de Cambridge, 2004. - ISBN 978-0-521-83378-3 .
Jonathan M. Borwein, Adrian Lewis. Análisis Convexo y Optimización No Lineal. - Springer, 2000. - (CMS Books in Mathematics). — ISBN 0-387-29570-4 .
Peter W. Christensen, Anders Klarbring. Una introducción a la optimización estructural. - Springer Science & Business Media, 2008. - V. 153. - ISBN 9781402086663 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Fundamentos del análisis convexo. - Berlín: Springer, 2004. - (ediciones de texto Grundlehren). - ISBN 978-3-540-42205-1 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Algoritmos de minimización y análisis convexo, Volumen I: Fundamentos. - Berlín: Springer-Verlag, 1993. - T. 305. - S. xviii + 417. - ISBN 978-3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Algoritmos de minimización y análisis convexo, Volumen II: Teoría avanzada y métodos de paquetes. - Berlín: Springer-Verlag, 1993. - T. 306. - S. xviii + 346. — ISBN 978-3-540-56852-0 .
Krzysztof C. Kiwiel. Métodos de Descenso para Optimización No Diferenciable. - Nueva York: Springer-Verlag, 1985. - (Lecture Notes in Mathematics). - ISBN 978-3-540-15642-0 .
Claude Lemarechal. Relajación lagrangiana // Optimización combinatoria computacional: artículos de la Spring School celebrada en Schloß Dagstuhl, del 15 al 19 de mayo de 2000. - Berlín: Springer-Verlag, 2001. - Vol. 2241. - P. 112-156. — ISBN 978-3-540-42877-0 . -doi : 10.1007/ 3-540-45586-8_4 .
Andrzej Ruszczyński. optimización no lineal. — Prensa de la Universidad de Princeton, 2006.
Eremin I. I. , Astafiev N. N. Introducción a la teoría de la programación lineal y convexa. - M. , Nauka , 1976. - 189 p.
Kamenev GK Métodos adaptativos óptimos para la aproximación poliédrica de cuerpos convexos. M.: VTs RAN, 2007, 230 p. ISBN 5-201-09876-2 .
Kamenev GK Estudio numérico de la eficiencia de métodos para la aproximación poliédrica de cuerpos convexos. M: Edición. CC RAS, 2010, 118s. ISBN 978-5-91601-043-5 .

Enlaces

Stephen Boyd, Lieven Vandenberghe, Optimización convexa (pdf)
EE364a: Optimización convexa I , EE364b: Optimización convexa II , página del curso de la Universidad de Oxford
6.253: Análisis convexo y optimización , página del curso MIT OCW
Brian Borchers, Una descripción general del software para la optimización convexa

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial