Hispanopedia Wiki
Articulo de referencia

Análisis convexo

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

Hispanopedia WikiContenido en espanolLectura gratuita
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: do ⊆ incógnita {\displaystyle C\subseteq X} incógnita {\estilo de visualización X}

  1. Si es real y entonces [1] 0 ≤ a ≤ 1 {\displaystyle 0\leq r\leq 1} incógnita , y ∈ do {\displaystyle x,y\en C} a incógnita + ( 1 − a ) y ∈ do . {\displaystyle rx+(1-r)y\en C.}
  2. Si es real y con entonces 0 < a < 1 {\estilo de visualización 0<r<1} incógnita , y ∈ do {\displaystyle x,y\en C} incógnita ≠ y , {\displaystyle x\neq y,} a incógnita + ( 1 − a ) y ∈ do . {\displaystyle rx+(1-r)y\en 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 F : incógnita → [ − ∞ , ∞ ] {\displaystyle f:X\to [-\infty ,\infty ]} [ − ∞ , ∞ ] = R ∪ { ± ∞ } {\displaystyle [-\infty ,\infty ]=\mathbb {R} \cup \{\pm \infty \}} dominio ⁡ F = incógnita {\displaystyle \operatorname {dominio} f=X} F : incógnita → [ − ∞ , ∞ ] {\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 0 < a < 1 {\estilo de visualización 0<r<1} incógnita , y ∈ incógnita {\displaystyle x,y\en X} incógnita ≠ y . {\displaystyle x\neq y.} F {\estilo de visualización f}

entonces se llama estrictamente convexo . [1] F {\estilo de visualización 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 F {\estilo de visualización 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 incógnita 2 + incógnita y + y 2 . {\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] F : incógnita → [ − ∞ , ∞ ] {\displaystyle f:X\to [-\infty ,\infty ]} dominio ⁡ F {\displaystyle \operatorname {dominio} 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 F : incógnita → [ − ∞ , ∞ ] {\displaystyle f:X\to [-\infty ,\infty ]} dominio ⁡ F ≠ ∅ {\displaystyle \operatorname {dom} f\neq \varnothing } F ( incógnita ) > − ∞ {\displaystyle f(x)>-\infty} incógnita ∈ dominio ⁡ F . {\displaystyle x\in \operatorname {dominio} f.} incógnita {\estilo de visualización x} F {\estilo de visualización f} F ( incógnita ) ∈ R {\displaystyle f(x)\in \mathbb {R}} F {\estilo de visualización f} − ∞ . {\estilo de visualización -\infty .} − ∞ , {\estilo de visualización -\infty ,} + ∞ . {\estilo de visualización +\infty .} F : R norte → [ − ∞ , ∞ ] {\displaystyle f:\mathbb {R} ^{n}\to [-\infty ,\infty ]} b ∈ R norte {\displaystyle b\in \mathbb {R} ^{n}} a ∈ R {\displaystyle r\in \mathbb {R}}

F ( incógnita ) ≥ incógnita ⋅ b − a {\displaystyle f(x)\geq x\cdot br}     Para cada uno incógnita {\estilo de visualización x}

donde denota el producto escalar de estos vectores. incógnita ⋅ b {\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] F : incógnita → [ − ∞ , ∞ ] {\displaystyle f:X\to [-\infty ,\infty ]} F ∗ : incógnita ∗ → [ − ∞ , ∞ ] {\displaystyle f^{*}:X^{*}\to [-\infty ,\infty ]} incógnita ∗ {\estilo de visualización X^{*}} incógnita , {\estilo de visualización X,}

F ∗ ( incógnita ∗ ) = sorber el ∈ incógnita { ⟨ incógnita ∗ , el ⟩ − F ( el ) } {\displaystyle f^{*}(x^{*})=\sup _{z\in X}\{\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 \izquierda\langle \cdot ,\cdot \derecha\rangle } ⟨ incógnita ∗ , el ⟩ := incógnita ∗ ( el ) . {\displaystyle \left\langle x^{*},z\right\rangle :=x^{*}(z).} F {\estilo de visualización f} F ∗ ∗ = ( F ∗ ) ∗ : incógnita → [ − ∞ , ∞ ] {\displaystyle f^{**}=\izquierda(f^{*}\derecha)^{*}:X\to [-\infty ,\infty ]} F ∗ ∗ ( incógnita ) := sorber el ∗ ∈ incógnita ∗ { ⟨ incógnita , el ∗ ⟩ − F ( el ∗ ) } {\displaystyle f^{**}(x):=\sup _{z^{*}\in X^{*}}\left\{\left\langle x,z^{*}\right\rangle -f\left(z^{*}\right)\right\}} incógnita ∈ incógnita . {\displaystyle x\en X.} Función ⁡ ( incógnita ; Y ) {\displaystyle \operatorname {Func} (X;Y)} Y {\displaystyle Y} X , {\displaystyle X,} Func ⁡ ( X ; [ − ∞ , ∞ ] ) → Func ⁡ ( X ∗ ; [ − ∞ , ∞ ] ) {\displaystyle \operatorname {Func} (X;[-\infty ,\infty ])\to \operatorname {Func} \left(X^{*};[-\infty ,\infty ]\right)} f ↦ f ∗ {\displaystyle f\mapsto f^{*}}

Conjunto subdiferencial y desigualdad de Fenchel-Young

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

∂ f ( x ) : = { x ∗ ∈ X ∗   :   f ( z ) ≥ f ( x ) + ⟨ x ∗ , z − x ⟩  for all  z ∈ X } ( “ z ∈ X ''  can be replaced with:  “ z ∈ X  such that  z ≠ x '' ) = { x ∗ ∈ X ∗   :   ⟨ x ∗ , x ⟩ − f ( x ) ≥ ⟨ x ∗ , z ⟩ − f ( z )  for all  z ∈ X } = { x ∗ ∈ X ∗   :   ⟨ x ∗ , x ⟩ − f ( x ) ≥ sup z ∈ X ⟨ x ∗ , z ⟩ − f ( z ) }  The right hand side is  f ∗ ( x ∗ ) = { x ∗ ∈ X ∗   :   ⟨ x ∗ , x ⟩ − f ( x ) = f ∗ ( x ∗ ) }  Taking  z := x  in the  sup  gives the inequality  ≤ . {\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: f = ‖ ⋅ ‖ {\displaystyle f=\|\cdot \|} X {\displaystyle X} 0 ≠ x ∈ X {\displaystyle 0\neq x\in X}

∂ f ( x ) = { x ∗ ∈ X ∗   :   ⟨ x ∗ , x ⟩ = ‖ x ‖  and  ‖ x ∗ ‖ = 1 } {\displaystyle \partial f(x)=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle =\|x\|{\text{ and }}\left\|x^{*}\right\|=1\right\}}     y     ∂ f ( 0 ) = { x ∗ ∈ X ∗   :   ‖ x ∗ ‖ ≤ 1 } . {\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 x ∈ X {\displaystyle x\in X} x ∗ ∈ X ∗ , {\displaystyle x^{*}\in X^{*},} f ( x ) + f ∗ ( x ∗ ) ≥ ⟨ x ∗ , x ⟩ , {\displaystyle f(x)+f^{*}\left(x^{*}\right)\geq \left\langle x^{*},x\right\rangle ,} f ( x ) + f ∗ ( x ∗ ) = ⟨ x ∗ , x ⟩ {\displaystyle f(x)+f^{*}\left(x^{*}\right)=\left\langle x^{*},x\right\rangle } x ∗ ∈ ∂ f ( x ) . {\displaystyle x^{*}\in \partial f(x).} ∂ f ( x ) {\displaystyle \partial f(x)} f ∗ ( x ∗ ) . {\displaystyle f^{*}\left(x^{*}\right).}

Biconjugado

El biconjugado de una función es el conjugado del conjugado, normalmente 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 ). f : X → [ − ∞ , ∞ ] {\displaystyle f:X\to [-\infty ,\infty ]} f ∗ ∗ : X → [ − ∞ , ∞ ] . {\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] x ∈ X , {\displaystyle x\in X,} f ∗ ∗ ( x ) ≤ f ( x ) {\displaystyle f^{**}(x)\leq f(x)} f = f ∗ ∗ {\displaystyle f=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 inf x ∈ M f ( x ) {\displaystyle \inf _{x\in M}f(x)} f : X → [ − ∞ , ∞ ] {\displaystyle f:X\to [-\infty ,\infty ]} M ⊆ X . {\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 ( X , X ∗ ) {\displaystyle \left(X,X^{*}\right)} ( Y , Y ∗ ) . {\displaystyle \left(Y,Y^{*}\right).} f : X → [ − ∞ , ∞ ] , {\displaystyle f:X\to [-\infty ,\infty ],} x {\displaystyle x}

inf x ∈ X f ( 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] f {\displaystyle f} f = f + I c o n s t r a i n t s {\displaystyle f=f+I_{\mathrm {constraints} }} I {\displaystyle I} F : X × Y → [ − ∞ , ∞ ] {\displaystyle F:X\times Y\to [-\infty ,\infty ]} F ( x , 0 ) = f ( x ) . {\displaystyle F(x,0)=f(x).}

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

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

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

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

sup y ∗ ∈ Y ∗ − F ∗ ( 0 , y ∗ ) ≤ inf x ∈ X F ( x , 0 ) . {\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:

Dualidad de Lagrange

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

min x f ( x ) {\displaystyle \min {}_{x}f(x)} sujeto a para g i ( x ) ≤ 0 {\displaystyle g_{i}(x)\leq 0} i = 1 , … , m . {\displaystyle i=1,\ldots ,m.}

El problema dual lagrangiano es

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

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

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

Véase también

Notas

  1. ^ ab Rockafellar, R. Tyrrell (1997) [1970]. Análisis convexo . Princeton, Nueva Jersey: Princeton University Press. ISBN 978-0-691-01586-6.
  2. ^ abc Rockafellar & Wets 2009, págs. 1–28.
  3. ^ ab 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. ^ ab 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. ∎ X = { 0 } {\displaystyle X=\{0\}} x ∈ X . {\displaystyle x\in X.} f {\displaystyle f} ∂ f ( x ) = { x ∗ ∈ X ∗   :   ⟨ x ∗ , x ⟩ − ‖ x ‖ ≥ ⟨ x ∗ , z ⟩ − ‖ z ‖  for all  z ∈ X } . {\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\}.} x ∗ ∈ ∂ f ( x ) {\displaystyle x^{*}\in \partial f(x)} r ≥ 0 {\displaystyle r\geq 0} z := r x {\displaystyle z:=rx} ⟨ x ∗ , x ⟩ − ‖ x ‖ ≥ ⟨ x ∗ , r x ⟩ − ‖ r x ‖ = r [ ⟨ x ∗ , x ⟩ − ‖ x ‖ ] , {\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],} r := 2 {\displaystyle r:=2} x ∗ ( x ) ≥ ‖ x ‖ {\displaystyle x^{*}(x)\geq \|x\|} r := 1 2 {\displaystyle r:={\frac {1}{2}}} x ∗ ( x ) ≤ ‖ x ‖ {\displaystyle x^{*}(x)\leq \|x\|} x ∗ ( x ) = ‖ x ‖ {\displaystyle x^{*}(x)=\|x\|} x ≠ 0 {\displaystyle x\neq 0} x ∗ ( x ‖ x ‖ ) = 1 , {\displaystyle x^{*}\left({\frac {x}{\|x\|}}\right)=1,} ‖ x ∗ ‖ ≥ 1. {\displaystyle \left\|x^{*}\right\|\geq 1.} ∂ f ( x ) ⊆ { x ∗ ∈ X ∗   :   x ∗ ( x ) = ‖ x ‖ } , {\displaystyle \partial f(x)\subseteq \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},} ∂ f ( x ) = ∂ f ( x ) ∩ { x ∗ ∈ X ∗   :   x ∗ ( x ) = ‖ x ‖ } , {\displaystyle \partial f(x)=\partial f(x)\cap \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},} ∂ f ( x ) = { x ∗ ∈ X ∗   :   x ∗ ( x ) = ‖ x ‖  and  ‖ z ‖ ≥ ⟨ x ∗ , z ⟩  for all  z ∈ X } , {\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\},} ‖ x ∗ ‖ ≤ 1 {\displaystyle \left\|x^{*}\right\|\leq 1} x ∗ ∈ ∂ f ( x ) . {\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 .
  • Medios relacionados con Análisis convexo en Wikimedia Commons
Retrieved from "https://en.wikipedia.org/w/index.php?title=Convex_analysis&oldid=1233679270"