Análisis convexo

Matemáticas de funciones y conjuntos convexos

Un politopo convexo tridimensional. El análisis convexo incluye no solo 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 las funciones convexas y los conjuntos convexos , a menudo con aplicaciones en la minimización convexa , un subdominio de la teoría de la optimización .

Conjuntos convexos

Un subconjunto de algún espacio vectorial es convexo si satisface cualquiera 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, se tratará de una función valorada en números reales extendidos con un dominio que es un subconjunto convexo de algún espacio vectorial. La función 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 ]}$

se cumple 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 los conjuntos convexos. En concreto, la función es convexa si y solo 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 por encima de su gráfico (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 reales extendidas desempeñan un papel en el análisis convexo que es análogo al papel que desempeñan los gráficos de funciones reales en el análisis real . Específicamente, el epígrafe de una función real extendida 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 todo ^[2] Alternativamente, esto significa que existe algún en el dominio de en el que y tampoco es nunca igual a En palabras, una función es propia si su dominio no está vacío, nunca toma el valor y tampoco es idénticamente igual a Si es una función convexa propia , entonces existen algunos vectores y algunos tales 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 uno ${\displaystyle x}$

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

Conjugado convexo

El conjugado convexo de una función real extendida (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 es 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 cualquier 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 una 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 cualquier función propia , si y solo si es convexa y semicontinua inferiormente por 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

Encuentra cuando se 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.}$

Problema dual

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

En general, dados dos pares duales separados en 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 existen condiciones de restricción, estas se pueden incorporar a la función haciendo que donde es 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)}$

¿Dónde está el conjugado convexo en ambas variables de ${\displaystyle F^{*}}$ ${\displaystyle F.}$

La brecha de dualidad es la diferencia de 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 dualidad débil . Si los dos lados son iguales entre sí, se dice que el problema satisface la dualidad fuerte .

Existen muchas condiciones para que se dé la dualidad fuerte, como por ejemplo:

• ${\displaystyle F=F^{**}}$donde es la función de perturbación que relaciona los problemas primal y dual y es el biconjugado de ; ^{[ cita requerida ]} ${\displaystyle F}$ ${\displaystyle F^{**}}$ ${\displaystyle F}$
• El problema primal 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 convexa con restricciones de desigualdad,

${\displaystyle \min {}_{x}f(x)}$sujeto a para ${\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 para ${\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)}$

Véase también

• La convexidad en la economía  : un tema importante en economía
  • No convexidad (economía)  – Violaciones de los supuestos de convexidad de la economía elemental
• Lista de temas sobre convexidad
• Werner Fenchel  – matemático alemán (1905–1988)

Notas

1. Rockafellar, R. Tyrrell (1997) [1970]. Análisis convexo . Princeton, NJ: 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, Adrian (2006). Análisis convexo y optimización no lineal: teoría y ejemplos (2.ª edición). Springer. pp. 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). Superando el fracaso de las condiciones clásicas de regularidad generalizada de punto interior en la optimización convexa. Aplicaciones de la teoría de dualidad a ampliaciones de operadores monótonos máximos . Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3.
8. Borwein, Jonathan; Lewis, Adrian (2006). Análisis convexo y optimización no lineal: teoría y ejemplos (2.ª edición). Springer. ISBN 978-0-387-29570-1.
9. Boyd, Stephen; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. Recuperado el 3 de octubre de 2011 .

1. La conclusión es inmediata si así se supone lo contrario. Arreglar Reemplazando con la norma se obtiene Si y es real entonces usando da donde en particular, tomando da mientras que tomando da y por lo tanto ; además, si además entonces porque se sigue de la definición de la norma dual que Porque que es equivalente a se sigue que 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 de operadores monótonos en espacios de Hilbert . Libros de matemáticas de CMS. Springer Science & Business Media . ISBN 978-3-319-48311-5.OCLC 1037059594  .
• Boyd, Stephen ; Vandenberghe, Lieven (8 de marzo de 2004). Optimización convexa . Cambridge Series in Statistical and Probabilistic Mathematics. 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: Kluwer Academic Publishers. 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 de matemáticas puras y aplicadas. Vol. 8 (segunda edición). Nueva York, NY: McGraw-Hill Science/Engineering/Math . ISBN 978-0-07-054236-5.OCLC 21163277  .
• Singer, Ivan (1997). Análisis convexo abstracto . Serie de monografías y textos avanzados de la Canadian Mathematical Society. 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, NJ Londres: World Scientific Publishing . ISBN 978-981-4488-15-0. MR  1921556. OCLC  285163112 – vía Internet Archive .

Enlaces externos

• Medios relacionados con Análisis convexo en Wikimedia Commons