Análisis convexo

El análisis convexo es una rama de las matemáticas dedicada al estudio de las propiedades de funciones convexas y conjuntos convexos , que a menudo tiene aplicaciones en la programación convexa , un subcampo de la teoría de la optimización .

Conjuntos convexos

Un conjunto convexo es un conjunto para algún espacio vectorial X tal que para cualquier y [1] $C\subseteq X$ ${\ estilo de visualización x, y \ en C}$ $\lambda\in[0,1]$

{\ estilo de visualización \ lambda x + (1- \ lambda) y \ en C}

Función convexa

Una función convexa es cualquier función extendida de valores reales que satisface la desigualdad de Jensen , es decir, para cualquier y cualquier ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ $x,y\en X$ $\lambda\in[0,1]$

f(\lambda x+(1-\lambda )y)\leqslant \lambda f(x)+(1-\lambda )f(y)

[1] .

De manera equivalente, una función convexa es cualquier función de valor real (extendida) tal que su epígrafe

{\displaystyle \left\{(x,r)\in X\times \mathbf {R} :f(x)\leqslant r\right\))

es un conjunto convexo [1] .

Conjugación convexa

La conjugación convexa de una función extendida de valor real (no necesariamente convexa) es una función , donde X* es el espacio dual de X [2] , tal que ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ ${\displaystyle f^{*}:X^{*}\to \mathbb {R} \cup \{\pm \infty \))$

f^{*}(x^{*})=\sup _{x\in X}\left\{\langle x^{*},x\rangle -f(x)\right\}.

Doble emparejamiento

La doble conjugación de una función es la conjugación conjugación, que generalmente se escribe como . La doble conjugación es útil cuando se necesita mostrar que se mantiene una dualidad fuerte o débil (usando la función de perturbación ). ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ ${\displaystyle f^{**}:X\to \mathbb {R} \cup \{\pm \infty \))$

Porque cualquier desigualdad se sigue de la desigualdad de Fenchel . Para una función propia f = f** si y solo si f es convexa y semicontinua inferior por el teorema de Fenchel-Moro [2] [3] . $x\en X$ $f^{**}(x)\leqslant f(x)$

Minimización convexa

El problema de programación convexa (directa) es un problema de la forma

{\ estilo de visualización \ inf _ {x \ en M} f (x)}

tal que es una función convexa y es un conjunto convexo. ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \))$ $M\subconjunto X$

Problema dual

El principio de dualidad en la optimización establece que los problemas de optimización pueden verse desde dos puntos de vista, como un problema directo o como un problema dual .

En general, dado un par dual [4] de espacios separables localmente convexos y una función , podemos definir el problema directo como encontrar tal que En otras palabras, es el mínimo (límite inferior exacto) de la función . ${\ estilo de visualización \ izquierda (X, X ^ {*} \ derecha)}$ ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \))$ ${\ sombrero {x}}$ $f({\sombrero {x)))=\inf _{x\in X}f(x).\,$ ${\ estilo de visualización f ({\ sombrero {x)))}$ $F$

Si hay restricciones, se pueden incorporar a la función si ponemos , donde está la función indicadora . Sea ahora (para otro par dual ) una función de perturbación tal que [5] . $F$ ${\tilde {f}}=f+I_{\mathrm {restricciones} }$ $yo$ ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \))$ ${\ estilo de visualización \ izquierda (Y, Y ^ {*} \ derecha)}$ $F(x,0)={\tilde {f))(x)$

El problema dual para esta función de perturbación con respecto al problema elegido se define como

\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})

donde F* es la conjugación convexa en ambas variables de la función F .

La brecha de dualidad es la diferencia entre los lados derecho e izquierdo de la desigualdad

\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leqslant \inf_{x\in X}F(x, 0),\,

donde es la conjugación convexa de ambas variables, y significa el supremo (límite superior exacto) [6] [7] [5] [6] . $F^{*}$ $\arriba$

\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leqslant \inf_{x\in X}F(x, 0).

Este principio es el mismo que el de la dualidad débil . Si ambos lados son iguales, se dice que el problema satisface las condiciones de dualidad fuerte .

Hay muchas condiciones para una fuerte dualidad, tales como:

F = F** , donde F es la función de perturbación para los problemas primal y dual, y F** es la doble conjugación de la función F ;
el problema directo es un problema de programación lineal ;
Condición de Slater para problemas de programación convexa [8] [9] .

Dualidad de Lagrange

Para un problema de minimización convexa con restricciones de desigualdad

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

bajo condiciones para i = 1, …, m .

g_{i}(x)\leqslant 0

el problema dual de Lagrange es

{\ estilo de visualización \ sup _ {u} \ inf _ {x} L (x, u)}

bajo condiciones para i = 1, …, m ,

u_{i}(x)\geqslant 0

donde la función objetivo L ( x , u ) es la función dual de Lagrange definida como sigue:

L(x,u)=f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)

Notas

↑ 1 2 3 Rockafellar, 1997 .
↑ 1 2 Zălinescu, 2002 , pág. 75–79.
↑ Borwein y Lewis, 2006 , pág. 76–77.
↑ El par dual es un triple , donde es un espacio vectorial sobre un campo , es el conjunto de todas las aplicaciones lineales , y el tercer elemento es una forma bilineal . $\left(X,X^{*},\langle ,\rangle \right)$ $X$ $F$ $X^{*}$ ${\ estilo de visualización \ phi \ dos puntos X \ a F}$ $X^{*}\times X\to F\colon (\phi ,x)\mapsto \phi (x)$
↑ 1 2 Boţ, Wanka, Grad., 2009 .
↑ 12 Csetnek , 2010 .
↑ Zălinescu, 2002 , pág. 106–113.
↑ Borwein, Lewis, 2006 .
↑ Boyd, Vandenberghe, 2004 .

Literatura

Osipenko K.Yu. Mejoramiento. Parte 1. Análisis convexo (notas de clase). M.: MSU. 57 págs.
Osipenko K.Yu. Análisis convexo (programa del curso y notas de clase). M.: MSU. 68 págs.
Petrov N. N. Análisis convexo (notas de clase) . Izhevsk: UdmGU, 2009. 160 p.
Métodos de optimización de Zhadan VG . Parte I. Introducción al análisis convexo y la teoría de la optimización: libro de texto. asentamiento para semental universidades en la dirección ... "Matemáticas y Física Aplicadas". Moscú: MIPT , 2014. ISBN 978-5-7417-0514-8 . (Parte I). 271 págs. Lanzamiento de 300 uds.
Elementos de análisis convexo y fuertemente convexo: un libro de texto para estudiantes de instituciones de educación superior que estudian en la dirección de "Matemáticas y Física Aplicadas" y áreas y especialidades relacionadas / E. S. Polovinkin , M. V. Balashov. - 2ª ed., corregida. y adicional - Moscú: Fizmatlit, 2007. - 438 p.; 22 cm.- (Libro de texto Phystech).; ISBN 978-5-9221-0896-6
Protasov V. Yu. Análisis convexo (notas de conferencias. Mekhmat MGU, flujo económico, 2009). M.: MSU.
Jonathan Borwein, Adrián Lewis. Análisis Convexo y Optimización No Lineal: Teoría y Ejemplos. - 2. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Stephen Boyd, Lieven Vandenberghe. Optimización convexa . - Prensa de la Universidad de Cambridge, 2004. - ISBN 978-0-521-83378-3 .
R. Tyrrell Rockafellar. Análisis convexo. - Princeton, NJ: Princeton University Press, 1997. - ISBN 978-0-691-01586-6 .
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Dualidad en Optimización de Vectores. - Springer, 2009. - ISBN 978-3-642-02885-4 .
Constantin Zalinescu. Análisis convexo en espacios vectoriales generales. — River Edge, NJ: World Scientific Publishing Co., Inc., 2002. — págs. 106–113. - ISBN 981-238-067-1 .
Ernö Robert Csetnek. Superación del fallo de las condiciones de regularidad clásicas generalizadas del punto interior en la optimización convexa. Aplicaciones de la teoría de la dualidad a ampliaciones de operadores monótonos máximos. - Logos Verlag Berlin GmbH, 2010. - ISBN 978-3-8325-2503-3 .
Jonathan Borwein, Adrián Lewis. Análisis Convexo y Optimización No Lineal: Teoría y Ejemplos. - 2. - Springer, 2006. - ISBN 978-0-387-29570-1 .
Hiriart-Urruty J.-B., Lemaréchal C. Fundamentos del análisis convexo. - Berlín: Springer-Verlag, 2001. - ISBN 978-3-540-42205-1 .
Iván Singer. Análisis convexo abstracto. - Nueva York: John Wiley & Sons, Inc., 1997. - Pág. xxii+491. - (Canadian Mathematical Society serie de monografías y textos avanzados). - ISBN 0-471-16015-6 .
Stoer J., Witzgall C. Convexidad y optimización en dimensiones finitas. - Berlín: Springer, 1970. - Vol. 1. - ISBN 978-0-387-04835-2 .
Kusraev AG, Kutateladze SS Subdiferenciales: teoría y aplicaciones. - Dordrecht: Kluwer Academic Publishers, 1995. - ISBN 978-94-011-0265-0 .
Kusraev A. G., Kutateladze S. S. Subdiferenciales. Teoría y aplicaciones. Parte 2. - 2ª, revisada .. - Novosibirsk: Editorial del Instituto de Matemáticas, 2003. - ISBN 5–86134–116–8.