Análisis convexo

Un politopo convexo tridimensional. El análisis convexo incluye no sólo el estudio de subconjuntos convexos de espacios euclidianos sino también el estudio de funciones convexas en espacios abstractos.

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

Conjuntos convexos

Un subconjunto de algún espacio vectorial es convexo si satisface alguna de las siguientes condiciones equivalentes: ${\displaystyle C\subseteq X}$ ${\displaystyle X}$

1. Si es real y entonces ^[1] ${\displaystyle 0\leq r\leq 1}$ ${\displaystyle x,y\in C}$ ${\displaystyle rx+(1-r)y\in C.}$
2. si es real y con entonces ${\displaystyle 0<r<1}$ ${\displaystyle x,y\in C}$ ${\displaystyle x\neq y,}$ ${\displaystyle rx+(1-r)y\in C.}$

Función convexa en un intervalo.

En todo momento, habrá un mapa valorado en números reales extendidos con un dominio que es un subconjunto convexo de algún espacio vectorial. El mapa es una función convexa si ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle [-\infty ,\infty ]=\mathbb {R} \cup \{\pm \infty \}}$ ${\displaystyle \operatorname {domain} f=X}$ ${\displaystyle f:X\to [-\infty ,\infty ]}$

es válido para cualquier real y cualquier con Si esto sigue siendo cierto cuando la desigualdad definitoria ( Convexidad ≤ ) se reemplaza por la desigualdad estricta ${\displaystyle 0<r<1}$ ${\displaystyle x,y\in X}$ ${\displaystyle x\neq y.}$ ${\displaystyle f}$

entonces se llama estrictamente convexo . ^[1] ${\displaystyle f}$

Las funciones convexas están relacionadas con conjuntos convexos. Específicamente, la función es convexa si y sólo si su epígrafe ${\displaystyle f}$

Una función (en negro) es convexa si y sólo si su epígrafe, que es la región encima de su gráfica (en verde), es un conjunto convexo .

Una gráfica de la función convexa bivariada. ${\displaystyle x^{2}+xy+y^{2}.}$

es un conjunto convexo. ^[2] Los epígrafes de funciones de valores reales extendidas desempeñan un papel en el análisis convexo que es análogo al papel que desempeñan las gráficas de funciones de valores reales en el análisis real . Específicamente, el epígrafe de una función extendida de valor real proporciona intuición geométrica que puede usarse para ayudar a formular o probar conjeturas.

El dominio de una función se denota por mientras que su dominio efectivo es el conjunto ^[2] ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle \operatorname {domain} f}$

La función se llama propia si y para todos ^[2] Alternativamente, esto significa que existe algo en el dominio de en el cual y nunca es igual a En palabras, una función es propia si su dominio no está vacío, nunca asume el valor y tampoco es idénticamente igual a Si es una función convexa adecuada , entonces existe algún vector y algo tal que ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle \operatorname {dom} f\neq \varnothing }$ ${\displaystyle f(x)>-\infty }$ ${\displaystyle x\in \operatorname {domain} f.}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle f(x)\in \mathbb {R} }$ ${\displaystyle f}$ ${\displaystyle -\infty .}$ ${\displaystyle -\infty ,}$ ${\displaystyle +\infty .}$ ${\displaystyle f:\mathbb {R} ^{n}\to [-\infty ,\infty ]}$ ${\displaystyle b\in \mathbb {R} ^{n}}$ ${\displaystyle r\in \mathbb {R} }$

${\displaystyle f(x)\geq x\cdot b-r}$     para cada ${\displaystyle x}$

donde denota el producto escalar de estos vectores. ${\displaystyle x\cdot b}$

conjugado convexo

El conjugado convexo de una función extendida de valor real (no necesariamente convexa) es la función del espacio dual (continuo) de y ^[3] ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle f^{*}:X^{*}\to [-\infty ,\infty ]}$ ${\displaystyle X^{*}}$ ${\displaystyle X,}$

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

donde los corchetes denotan la dualidad canónica El biconjugado de es el mapa definido por para cada Si denota el conjunto de funciones con valores en entonces el mapa definido por se llama transformada de Legendre-Fenchel . ${\displaystyle \left\langle \cdot ,\cdot \right\rangle }$ ${\displaystyle \left\langle x^{*},z\right\rangle :=x^{*}(z).}$ ${\displaystyle f}$ ${\displaystyle f^{**}=\left(f^{*}\right)^{*}:X\to [-\infty ,\infty ]}$ ${\displaystyle f^{**}(x):=\sup _{z^{*}\in X^{*}}\left\{\left\langle x,z^{*}\right\rangle -f\left(z^{*}\right)\right\}}$ ${\displaystyle x\in X.}$ ${\displaystyle \operatorname {Func} (X;Y)}$ ${\displaystyle Y}$ ${\displaystyle X,}$ ${\displaystyle \operatorname {Func} (X;[-\infty ,\infty ])\to \operatorname {Func} \left(X^{*};[-\infty ,\infty ]\right)}$ ${\displaystyle f\mapsto f^{*}}$

Conjunto subdiferencial y desigualdad de Fenchel-Young

Si y entonces el conjunto subdiferencial es ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle x\in X}$

${\displaystyle {\begin{alignedat}{4}\partial f(x):&=\left\{x^{*}\in X^{*}~:~f(z)\geq f(x)+\left\langle x^{*},z-x\right\rangle {\text{ for all }}z\in X\right\}&&({\text{“}}z\in X{\text{''}}{\text{ can be replaced with: }}{\text{“}}z\in X{\text{ such that }}z\neq x{\text{''}})\\&=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -f(x)\geq \left\langle x^{*},z\right\rangle -f(z){\text{ for all }}z\in X\right\}&&\\&=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -f(x)\geq \sup _{z\in X}\left\langle x^{*},z\right\rangle -f(z)\right\}&&{\text{ The right hand side is }}f^{*}\left(x^{*}\right)\\&=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -f(x)=f^{*}\left(x^{*}\right)\right\}&&{\text{ Taking }}z:=x{\text{ in the }}\sup {}{\text{ gives the inequality }}\leq .\\\end{alignedat}}}$

Por ejemplo, en el caso especial importante donde hay una norma en , se puede demostrar ^{[prueba 1]} que si entonces esta definición se reduce a: ${\displaystyle f=\|\cdot \|}$ ${\displaystyle X}$ ${\displaystyle 0\neq x\in X}$

${\displaystyle \partial f(x)=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle =\|x\|{\text{ and }}\left\|x^{*}\right\|=1\right\}}$     y     ${\displaystyle \partial f(0)=\left\{x^{*}\in X^{*}~:~\left\|x^{*}\right\|\leq 1\right\}.}$

Para cualquiera y que se llama desigualdad de Fenchel-Young . Esta desigualdad es una igualdad (es decir ) si y sólo si. Es de esta manera que el conjunto subdiferencial está directamente relacionado con el conjugado convexo. ${\displaystyle x\in X}$ ${\displaystyle x^{*}\in X^{*},}$ ${\displaystyle f(x)+f^{*}\left(x^{*}\right)\geq \left\langle x^{*},x\right\rangle ,}$ ${\displaystyle f(x)+f^{*}\left(x^{*}\right)=\left\langle x^{*},x\right\rangle }$ ${\displaystyle x^{*}\in \partial f(x).}$ ${\displaystyle \partial f(x)}$ ${\displaystyle f^{*}\left(x^{*}\right).}$

biconjugado

El biconjugado de una función es el conjugado del conjugado, típicamente escrito como El biconjugado es útil para mostrar cuándo se cumple la dualidad fuerte o débil (a través de la función de perturbación ). ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle f^{**}:X\to [-\infty ,\infty ].}$

Para cualquiera, la desigualdad se deriva de la desigualdad de Fenchel-Young . Para funciones propias , si y solo si es convexa y semicontinua inferior según el teorema de Fenchel-Moreau . ^{[3] [4]} ${\displaystyle x\in X,}$ ${\displaystyle f^{**}(x)\leq f(x)}$ ${\displaystyle f=f^{**}}$ ${\displaystyle f}$

Minimización convexa

Un problema de minimización convexa ( primal ) es uno de la forma

encontrar cuando se le da una función convexa y un subconjunto convexo ${\displaystyle \inf _{x\in M}f(x)}$ ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle M\subseteq X.}$

Doble problema

En la teoría de la optimización, el principio de dualidad establece que los problemas de optimización pueden verse desde dos perspectivas: el problema primario o el problema dual.

En general, dados dos pares duales separados espacios localmente convexos y Luego, dada la función, podemos definir el problema primal como encontrar tal que ${\displaystyle \left(X,X^{*}\right)}$ ${\displaystyle \left(Y,Y^{*}\right).}$ ${\displaystyle f:X\to [-\infty ,\infty ],}$ ${\displaystyle x}$

${\displaystyle \inf _{x\in X}f(x).}$

Si hay condiciones de restricción, estas se pueden incorporar a la función dejando dónde está la función indicadora . Entonces sea una función de perturbación tal que ^[5] ${\displaystyle f}$ ${\displaystyle f=f+I_{\mathrm {constraints} }}$ ${\displaystyle I}$ ${\displaystyle F:X\times Y\to [-\infty ,\infty ]}$ ${\displaystyle F(x,0)=f(x).}$

El problema dual con respecto a la función de perturbación elegida viene dado por

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

donde es el conjugado convexo en ambas variables de ${\displaystyle F^{*}}$ ${\displaystyle F.}$

La brecha de dualidad es la diferencia entre los lados derecho e izquierdo de la desigualdad ^{[6] [5] [7]}

${\displaystyle \sup _{y^{*}\in Y^{*}}-F^{*}\left(0,y^{*}\right)\leq \inf _{x\in X}F(x,0).}$

Este principio es el mismo que el de la dualidad débil . Si los dos lados son iguales entre sí, entonces se dice que el problema satisface una dualidad fuerte .

Hay muchas condiciones para que se mantenga una dualidad fuerte, tales como:

• ${\displaystyle F=F^{**}}$donde es la función de perturbación que relaciona los problemas primario y dual y es el biconjugado de ; ^{[ cita necesaria ]} ${\displaystyle F}$ ${\displaystyle F^{**}}$ ${\displaystyle F}$
• el problema principal es un problema de optimización lineal ;
• "Condición de Slater para un problema de optimización convexa ". ^{[8] [9]}

Dualidad de Lagrange

Para un problema de minimización convexo con restricciones de desigualdad,

${\displaystyle \min {}_{x}f(x)}$sujeto a por ${\displaystyle g_{i}(x)\leq 0}$ ${\displaystyle i=1,\ldots ,m.}$

El problema dual lagrangiano es

${\displaystyle \sup {}_{u}\inf {}_{x}L(x,u)}$sujeto a por ${\displaystyle u_{i}(x)\geq 0}$ ${\displaystyle i=1,\ldots ,m.}$

donde la función objetivo es la función dual de Lagrange definida de la siguiente manera: ${\displaystyle L(x,u)}$

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

Ver también

• Convexidad en economía  : tema importante en economía
  • No convexidad (economía)  : violaciones de los supuestos de convexidad de la economía elemental
• Lista de temas de convexidad.
• Werner Fenchel  - matemático alemánPages displaying wikidata descriptions as a fallback

Notas

1. Rockafellar, R. Tyrrell (1997) [1970]. Análisis convexo . Princeton, Nueva Jersey: Princeton University Press. ISBN 978-0-691-01586-6.
2. Rockafellar & Wets 2009, págs. 1-28.
3. Zălinescu 2002, págs. 75–79.
4. Borwein, Jonathan; Lewis, Adrián (2006). Análisis convexo y optimización no lineal: teoría y ejemplos (2 ed.). Saltador. págs. 76–77. ISBN 978-0-387-29570-1.
5. Boţ, Radu Ioan; Wanka, Gert; Graduado, Sorin-Mihai (2009). Dualidad en la optimización vectorial . Saltador. ISBN 978-3-642-02885-4.
6. Zălinescu 2002, págs. 106-113.
7. Csetnek, Ernö Robert (2010). Superar el fallo de las condiciones clásicas generalizadas de regularidad de puntos interiores en la optimización convexa. Aplicaciones de la teoría de la dualidad a ampliaciones de operadores monótonos máximos . Logos Verlag Berlín GmbH. ISBN 978-3-8325-2503-3.
8. Borwein, Jonathan; Lewis, Adrián (2006). Análisis convexo y optimización no lineal: teoría y ejemplos (2 ed.). Saltador. ISBN 978-0-387-29570-1.
9. Boyd, Esteban; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Prensa de la Universidad de Cambridge. ISBN 978-0-521-83378-3. Consultado el 3 de octubre de 2011 .

1. La conclusión es inmediata si se supone lo contrario. Arreglar Reemplazar con la norma da Si y es real, entonces usar da donde en particular, tomar da mientras toma da y por lo tanto ; es más, si además porque de la definición de la norma dual se sigue que Porque que es equivalente a ella se sigue lo que implica para todos De estos hechos, ahora se puede llegar a la conclusión. ∎ ${\displaystyle X=\{0\}}$ ${\displaystyle x\in X.}$ ${\displaystyle f}$ ${\displaystyle \partial f(x)=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -\|x\|\geq \left\langle x^{*},z\right\rangle -\|z\|{\text{ for all }}z\in X\right\}.}$ ${\displaystyle x^{*}\in \partial f(x)}$ ${\displaystyle r\geq 0}$ ${\displaystyle z:=rx}$ ${\displaystyle \left\langle x^{*},x\right\rangle -\|x\|\geq \left\langle x^{*},rx\right\rangle -\|rx\|=r\left[\left\langle x^{*},x\right\rangle -\|x\|\right],}$ ${\displaystyle r:=2}$ ${\displaystyle x^{*}(x)\geq \|x\|}$ ${\displaystyle r:={\frac {1}{2}}}$ ${\displaystyle x^{*}(x)\leq \|x\|}$ ${\displaystyle x^{*}(x)=\|x\|}$ ${\displaystyle x\neq 0}$ ${\displaystyle x^{*}\left({\frac {x}{\|x\|}}\right)=1,}$ ${\displaystyle \left\|x^{*}\right\|\geq 1.}$ ${\displaystyle \partial f(x)\subseteq \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},}$ ${\displaystyle \partial f(x)=\partial f(x)\cap \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},}$ ${\displaystyle \partial f(x)=\left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|{\text{ and }}\|z\|\geq \left\langle x^{*},z\right\rangle {\text{ for all }}z\in X\right\},}$ ${\displaystyle \left\|x^{*}\right\|\leq 1}$ ${\displaystyle x^{*}\in \partial f(x).}$

Referencias

• Bauschke, Heinz H.; Combettes, Patrick L. (28 de febrero de 2017). Análisis convexo y teoría del operador monótono en espacios de Hilbert . Libros CMS de Matemáticas. Medios de ciencia y negocios de Springer . ISBN 978-3-319-48311-5. OCLC  1037059594.
• Boyd, Esteban ; Vandenberghe, Lieven (8 de marzo de 2004). Optimizacion convexa . Serie Cambridge en Matemáticas Estadística y Probabilística. Cambridge, Reino Unido Nueva York: Cambridge University Press . ISBN 978-0-521-83378-3. OCLC  53331084.
• Hiriart-Urruty, J.-B.; Lemaréchal, C. (2001). Fundamentos del análisis convexo . Berlín: Springer-Verlag. ISBN 978-3-540-42205-1.
• Kusraev, AG; Kutateladze, Semen Samsonovich (1995). Subdiferenciales: teoría y aplicaciones . Dordrecht: Editores académicos de Kluwer. ISBN 978-94-011-0265-0.
• Rockafellar, R. Tyrrell ; Wets, Roger J.-B. (26 de junio de 2009). Análisis variacional . Grundlehren der mathematischen Wissenschaften. vol. 317. Berlín Nueva York: Springer Science & Business Media . ISBN 9783642024313. OCLC  883392544.
• Rudin, Walter (1991). Análisis funcional. Serie Internacional en Matemática Pura y Aplicada. vol. 8 (Segunda ed.). Nueva York, NY: McGraw-Hill Ciencias/Ingeniería/Matemáticas . ISBN 978-0-07-054236-5. OCLC  21163277.
• Cantante, Iván (1997). Análisis convexo abstracto . Serie de monografías y textos avanzados de la Sociedad Canadiense de Matemáticas. Nueva York: John Wiley & Sons, Inc. págs. xxii+491. ISBN 0-471-16015-6. SEÑOR  1461544.
• Stoer, J.; Witzgall, C. (1970). Convexidad y optimización en dimensiones finitas . vol. 1. Berlín: Springer. ISBN 978-0-387-04835-2.
• Zălinescu, Constantin (30 de julio de 2002). Análisis convexo en espacios vectoriales generales . River Edge, Nueva Jersey Londres: World Scientific Publishing . ISBN 978-981-4488-15-0. SEÑOR  1921556. OCLC  285163112 - vía Internet Archive .

enlaces externos

• Medios relacionados con el análisis convexo en Wikimedia Commons