Elementos de análisis y optimización convexa

Universidad de Sevilla Facultad de Matem´aticas Trabajo Fin de Estudios Grado en Matem´aticas Elementos de an´alisis y optimizaci´on convexa Mar´ıa Jos´e G´omez Notario Tutor Manuel Luna Laynez Dpto. Ecuaciones Diferenciales y An´alisis Num´erico Abstract This work serves as an introduction to Convex Optimization, which involves the study of minimization problems where the objective functional and a set of constraints satisfy certain convexity properties. The treatment of these problems has led to a series of specific techniques that comprise what is known as Convex Analysis. The first part of the thesis is dedicated to the study of some of these tools, such as the Legendre-Fenchel transform and the subdifferential. In the second part, these techniques are applied to the study of optimization problems, providing necessary and sufficient conditions for optimality. Among other results, the Kuhn-Tucker Theorem is demonstrated, the theory of duality is introduced, and the notion of the Lagrangian is studied along with some of its fundamental properties. All these techniques are applied to the study of certain linear quadratic control problems. Resumen Este trabajo constituye una introducci´on a la Optimizaci´on Convexa, es decir, al estudio de problemas de minimizaci´on en los que intervienen un funcional objetivo y un conjunto de restricciones que satisfacen ciertas propiedades de convexidad. El tratamiento de estos problemas ha dado lugar a una serie de t´ecnicas espec´ıficas que constituyen lo que se conoce como el An´alisis Convexo. La primera parte de la memoria se dedica al estudio de algunas de estas herramientas, como son la transformada de Legendre-Fenchel y el subdiferencial. En la segunda parte estas t´ecnicas se aplican al estudio de problemas de optimizaci´on, proporcionando condiciones necesarias y suficientes de ´optimo. Entre otros, se demuestra el Teorema de Kuhn-Tucker, se introduce la teor´ıa de dualidad y la noci´on de Lagrangiano, estudiando algunas de sus propiedades fundamentales. Todas estas t´ecnicas se aplican al estudio de algunos problemas de control lineal cuadr´atico. ´ Indice Introducci´on 5 1. Funciones convexas 8 1.1. Funciones convexas reales unidimensionales ..................... 8 1.2. Funciones convexas en espacios normados ...................... 13 1.3. Diferenciabilidad de las funciones convexas ..................... 20 2. Conjugaci´on y subdiferenciabilidad 24 2.1. La transformada de Legendre-Fenchel ........................ 24 2.1.1. Interpretaciones de la transformada de Legendre-Fenchel .......... 25 2.1.2. Ejemplo ..................................... 25 2.1.3. Algunas propiedades .............................. 26 2.1.4. La biconjugada ................................. 33 2.2. Subdiferenciabilidad .................................. 33 2.2.1. Ejemplos .................................... 34 2.2.2. Algunas propiedades .............................. 36 2.2.3. El subdiferencial de fyf∗.......................... 38 2.2.4. Relaci´on con la derivada de Gˆateaux ..................... 40 3. Introducci´on a la optimizaci´on convexa 42 3.1. El problema de minimizaci´on ............................. 42 3.2. Condiciones de optimalidad .............................. 42 3.2.1. El Teorema de Kuhn-Tucker .......................... 44 4. Dualidad en optimizaci´on convexa 50 4.1. Problemas perturbados ................................. 50 4.2. El Lagrangiano ..................................... 53 4.3. Aplicaci´on a la estabilidad en dualidad convexa ................... 57 4.4. Aplicaci´on a un problema particular ......................... 57 5. Un problema de control lineal cuadr´atico 60 5.1. Problema de control lineal cuadr´atico ........................ 60 5.2. Problema de control lineal cuadr´atico con restricciones sobre el estado ...... 65 A. Convergencia d´ebil en espacios normados 72 A.1. Topolog´ıa d´ebil σ(X, X∗)............................... 72 A.2. Topolog´ıa d´ebil-∗σ(X∗, X).............................. 72 2 Cap´ıtulo 0. ´ Indice 3 B. Algunos resultados de separaci´on 74 Bibliograf´ıa 76 TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas ´ Indice de figuras 1.1. Ep´ıgrafo de f...................................... 14 2.1. Representaci´on geom´etrica de la transformada de Legendre-Fenchel si X=R.. . 25 2.2. Representaci´on de fy∂f(x). ............................. 34 2.3. Cono normal de Cen x................................. 35 4 Cap´ıtulo 1. Funciones convexas 11 An´alogamente se tiene: f′ −(x1) = l´ım x→x− 1 φ(x) = sup x∈(−∞,x1)∩I φ(x). Tomamos x0, z0, x1, z1∈Icon x0< z0< x1< z1y por la desigualdad (1.3): f(z0)−f(x0) z0−x0 ≤f(z0)−f(x1) z0−x1 ≤f(z1)−f(x1) z1−x1 . Como nuestro objetivo es probar que f′ +(x) es una funci´on creciente, veamos que dados x0, x1 con x0< x1se tiene f′ +(x0)≤f′ +(x1). En la desigualdad anterior hacemos tender z0→x+ 0por lo que nos queda: f′ +(x0)≤f(z1)−f(x1) z1−x1 . Ahora si z1→x+ 1, tendremos que f′ +(x0)≤f′ +(x1) para x0< x1por lo tanto f′ +es creciente. An´alogamente se prueba que f′ −es creciente en int I. □ El siguiente teorema nos permite expresar una funci´on convexa como la integral de su derivada a derecha e izquierda. Teorema 1.7 Sea f: (a, b)−→ Runa funci´on convexa. Entonces ∀c, x ∈(a, b)se tiene: f(x)−f(c) = Zx c f′ +(t)dt =Zx c f′ −(t)dt. Demostraci´on: En primer lugar se tiene la integrabilidad por ser f′ +yf′ −crecientes en el intervalo compacto de extremos cyx. Sea c≤x, consideremos una partici´on del intervalo [c, x], c =x0< x1<· · · < xn=x. Para todo k= 1, . . . , n, se tiene f′ +(xk−1)≤f(xk)−f(xk−1) xk−xk−1 ≤f′ +(xk), de donde se deduce n X k=1 f′ +(xk−1)(xk−xk−1)≤ n X k=1 f(xk)−f(xk−1)≤ n X k=1 f′ +(xk)(xk−xk−1). Si vamos refinando la partici´on de manera que m´ax k=1,...,n |xk−xk−1| → 0 =⇒Zx c f′ +(t)dt ≤f(x)−f(c)≤Zx c f′ +(t)dt, TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 1. Funciones convexas 12 y de aqu´ı se deduce una de las igualdades del resultado. De manera an´aloga se tiene la desigualdad para f′ −. □ Mediante el siguiente teorema relacionamos el concepto de monoton´ıa y convexidad, en particular la posibilidad de expresar una funci´on convexa como la integral de una funci´on creciente. Proposici´on 1.8 Sea g: [a, b]−→ Runa funci´on creciente, sea c∈[a, b] entonces la funci´on f: [a, b]−→ Rdefinida por: f(x) = Zx c g(t)dt es convexa. Demostraci´on: Sean x1, x2∈[a, b] con x1≤x2yα, β ≥0 tal que α+β= 1. Nuestro objetivo es probar la convexidad de fpor tanto: f(αx1+βx2)≤αf(x1) + βf(x2)⇐⇒ αf(x1) + βf(x2)−f(αx1+βx2)≥0⇐⇒ αf(x1) + βf(x2)−(α+β)f(αx1+βx2)≥0⇐⇒ αZx1 c g(t)dt +βZx2 c g(t)dt −(α+β)Zαx1+βx2 c g(t)dt ≥0⇐⇒ αZx1 c g(t)dt −Zαx1+βx2 c g(t)dt+βZx2 c g(t)dt −Zαx1+βx2 c g(t)dt≥0⇐⇒ βZx2 αx1+βx2 g(t)dt −αZαx1+βx2 x1 g(t)dt ≥0. Por otro lado, al ser guna funci´on creciente: βZx2 αx1+βx2 g(t)dt −αZαx1+βx2 x1 g(t)dt ≥β g(αx1+βx2)Zx2 αx1+βx2 dt −α g(αx1+βx2)Zαx1+βx2 x1 dt =β g(αx1+βx2)(x2−αx1−βx2)−αg(αx1+βx2)(αx1+βx2−x1) = 0, lo que prueba la convexidad de la funci´on f. □ TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 1. Funciones convexas 13 Teorema 1.9 Sea f: [a, b]−→ Runa funci´on derivable en (a, b)y continua en [a, b]tal que f′ es creciente en (a, b)entonces fes convexa en [a, b]. Demostraci´on: La funci´on f′es integrable Riemann en cualquier subintervalo compacto de (a, b). Sea c, x ∈(a, b). Supongamos que c≤x. Sea c=x0≤ · · · ≤ cn=xuna partici´on del intervalo [c, x]. Para todo kcon 0 ≤k≤n−1,aplicando el Teorema del valor medio se tiene que ∃zk∈(ck, ck+1) tal que f(ck+1)−f(ck) = f′(zk)(ck+1 −ck) =⇒f(x)−f(c) = n−1 X k=0 f′(zk)(ck+1 −ck). Si l´ımk→∞ |ck+1 −ck|= 0, el t´ermino de la derecha de la igualdad anteror tiende a Zx c f′(t)dt, por lo tanto f(x)−f(c) = Zx c f′(t)dt ∀c, x ∈(a, b), y por la Proposici´on 1.8 se tiene la convexidad de fen (a, b).Gracias a la continuidad tambi´en se tiene en [a, b]. □ Observaci´on 1.10 Del anterior teorema se deduce la bien conocidad propiedad de que f′′ ≥0 implica fconvexa. 1.2 Funciones convexas en espacios normados En esta secci´on nos centramos en extender los resultados de convexidad para funciones de variable real a funciones definidas en espacios normados. Dichos resultados nos ofrecen las herramientas necesarias para abordar en los pr´oximos cap´ıtulos la resoluci´on de problemas de optimizaci´on convexa. Comenzamos con unas definiciones elementales. Definici´on 1.11 Sea un conjunto Xy una funci´on f:X−→ R. Definimos el dominio de la funci´on fcomo el siguiente conjunto: dom f ={x∈X:f(x)<+∞}. Definici´on 1.12 Dada una funci´on f:X−→ R, al conjunto epi f ={(x, t)∈X×R:f(x)≤t} TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 1. Funciones convexas 14 se le llama ep´ıgrafo de f. Figura 1.1: Ep´ıgrafo de f Definici´on 1.13 Dada una funci´on f:X−→ R, se define argmin f como argmin f ={u∈X:f(u) = ´ınf w∈Xf(w)}. Observar que el conjunto argmin f podr´ıa ser el conjunto vac´ıo. Definici´on 1.14 Sea Xun espacio vectorial, diremos que una funci´on f:X−→ Res convexa si ∀x1, x2∈dom f y∀λ∈[0,1] tenemos f(λx1+ (1 −λ)x2)≤λf(x1) + (1 −λ)f(x2),(1.4) yfestrictamente convexa si ∀x1, x2∈dom f con x1=x2y∀λ∈(0,1) tenemos f(λx1+ (1 −λ)x2)< λf(x1) + (1 −λ)f(x2). Observaci´on 1.15 Una forma equivalente de definir una funci´on convexa en un espacio vectorial es la siguiente: La funci´on f:X−→ Res convexa si y solo si ∀p∈N∀t1, . . . , tp≥0 tal que p X k=1 tk= 1 y ∀x1, . . . , xp∈dom f, se tiene f p X k=1 tkxk!≤ p X k=1 tkf(xk). Proposici´on 1.16 Una funci´on f:X−→ Res convexa si y s´olo si epi f es convexo. Demostraci´on: =⇒Supongamos que f:X−→ Res convexa. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 1. Funciones convexas 15 Sean (x1, t1),(x2, t2)∈epi f yλ∈[0,1]. Por ser fconvexa se tiene f(λx1+ (1 −λ)x2)≤λf(x1) + (1 −λ)f(x2) ≤λt1+ (1 −λ)t2por (x1, t1),(x2, t2)∈epi f. Por tanto λ(x1, t1) + (1 −λ)(x2, t2)∈epi f. ⇐= Supongamos epi f convexo. Para todo x1, x2∈dom f se tiene (x1, f(x1)),(x2, f(x2)) ∈epi f. Al ser epi f convexo por hip´otesis se tiene λ(x1, f(x1)) + (1 −λ)(x2, f(x2)) ∈epi f, por tanto f(λx1+ (1 −λ)x2)≤λf(x1) + (1 −λ)f(x2), lo que prueba la convexidad de f. □ Observaci´on 1.17 La suma de dos funciones convexas con valores en R∪ {+∞} es convexa. Proposici´on 1.18 Sean X, Y espacios vectoriales y sea F:X×Y−→ Runa funci´on convexa. La funci´on p:Y−→ R u7−→ ´ınf x∈XF(x, u) es convexa. Demostraci´on: Sean u, v ∈Ytal que p(u)<+∞yp(v)<+∞. Sean t∈[0,1], λ, µ ∈Rtales que p(u)< λ y p(v)< µ. Aplicando la definici´on de ´ınfimo p(u) = ´ınf x∈XF(x, u) se tiene p(u)≤F(x, u)∀x∈X, entonces ∀ε > 0,existe xε∈Xtal que F(xε, u)−ε<p(u) y como t∈[0,1], tF(xε, u)≤t(p(u) + ε)∀ε > 0. An´alogamente, por la definici´on de p(v) = ´ınfx∈XF(x, v) se tiene p(v)≤F(x, v) para todo x∈X. Adem´as ∀ε > 0,existe zε∈Xtal que F(zε, v)−ε<p(v).Como t∈[0,1], se tiene (1 −t)F(zε, v)<(1 −t)(p(v) + ε)∀ε > 0. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 1. Funciones convexas 16 Entonces por la convexidad de la funci´on F p(tu + (1 −t)v)≤tF(xε, u) + (1 −t)F(zε, v) ≤tp(u) + (1 −t)p(v) + tε + (1 −t)ε∀ε > 0. Haciendo ε→0+se tiene p(tu + (1 −t)v)≤tp(u) + (1 −t)p(v), lo que prueba la convexidad de la funci´on p. □ Introducimos ahora una operaci´on fundamental en an´alisis convexo: la suma epigr´afica o infconvoluci´on. Definici´on 1.19 Sea Xun espacio vectorial y sean f, g :X−→ R∪ {+∞}. Se define la suma epigr´afica (o inf-convoluci´on) de f y g como la funci´on f+eg:X−→ R x7−→ ´ınf z∈X(f(z) + g(x−z)) = ´ınf x1+x2=x(f(x1) + g(x2)). Se dice que la suma epigr´afica es exacta en xsi (f+eg)(x) = m´ınz∈X(f(z) + g(x−z)). Se dice que la suma epigr´afica es exacta si es exacta en x, ∀x∈X. Proposici´on 1.20 Sea Xun espacio vectorial y sean f, g :X−→ R∪ {+∞} funciones convexas, entonces f+eges convexa. Demostraci´on: Definimos la funci´on F:X×X−→ R∪ {+∞} (z, x)7−→ f(z) + g(z−x). Aplicando la Observaci´on 1.17 se tiene la convexidad de Fal ser fygdos funciones con valores en R∪ {+∞} y convexas, por tanto aplicando la Proposici´on 1.18,f+eges convexa. □ A continuaci´on, veamos las condiciones en las que la convexidad de una funci´on implica su continuidad. Teorema 1.21 Sea Xun espacio normado y sea f:X−→ Runa funci´on convexa acotada superiormente en un entorno de a∈f−1(R), entonces fes continua en a. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 1. Funciones convexas 17 Demostraci´on: Nuestro objetivo es probar que fes continua en alo que equivale a probar que la funci´on x7−→ g(x) = f(a+x)−f(a) es continua en 0. Al estar facotada superiormente en un entorno de a,gest´a acotada superiormente en un entorno de 0. Suponemos sin p´erdida de generalidad que a= 0 y f(a) = 0. Sean r > 0 y M∈Rtales que f(u)≤M, ∀u∈B(0, r).Sean ε∈(0,1) y v∈ε B(0, r) = B(0, rε). Reescribimos vcomo v= (1 −ε)·0 + ε·v ε=⇒ =⇒f(v)≤(1 −ε)f(0) + ε f(v ε)≤ε M. Por otro lado 0 = v 1 + ε+ε 1 + ε−v ε=⇒f(0) ≤1 1 + εf(v) + ε 1 + εf−v ε≤1 1 + εf(v) + ε 1 + εM. Y despejando se tiene f(v)≥(1 + ε)f(0) −εM =−εM =⇒ |f(v)| ≤ εM ∀v∈B(0, rε). Por lo tanto se tiene la continuidad de fen 0. □ Proposici´on 1.22 Sean Xun espacio normado, f:X−→ Rconvexa. Las siguientes propiedades son equivalentes: 1. fes continua en a∈f−1(R) 2. Existe λ∈Rtal que a∈int ([f≤λ])2 3. Existe λ∈Rtal que (a, λ)∈int (epi f) Demostraci´on: (1) =⇒(2) Trivial. (2) =⇒(3) Sea r > 0 tal que B(a, r)⊂[f≤λ] entonces B(a, r)×[λ, +∞)⊂epi f, por lo que ∃λ∈Rtal que (a, λ)∈int(epi f). (3) =⇒(1) Consideramos un entorno de (a, λ). 2[f≤λ]) = {x∈X:f(x)≤λ} TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 1. Funciones convexas 18 Sea r > 0, η > 0 tal que B(a, r)×[λ−η, λ +η]⊂epi f, entonces B(a, r)× {λ} ⊂ epi f y en consecuencia f(u)≤λ, ∀u∈B(a, η) y por lo tanto fes continua en a. □ Teorema 1.23 Sea f:X−→ R∪{+∞} una funci´on convexa continua en a∈dom f, entonces ∃r > 0tal que fes Lipschitziana en B(a, r). Demostraci´on: Por hip´otesis se tiene la continuidad de fen alo que implica que fest´a acotada en un entorno de a. Por lo tanto ∃r > 0, ε > 0 y m, M ∈Rtales que m≤f(z)≤M, ∀z∈B(a, r +ε). Sean x, y ∈B(a, r) con x=y, y sea zdado por z=y+εy−x ∥y−x∥∈B(a, r +ε). Entonces, para λ=∥y−x∥ ∥y−x∥+ε∈(0,1) se tiene y=λz + (1 −λ)x Usando la convexidad de fse prueba f(y)≤λf(z) + (1 −λ)f(x) = λ(f(z)−f(x)) + f(x) =⇒ f(y)−f(x)≤∥y−x∥ ∥y−x∥+ε(M−m)≤M−m ε∥y−x∥. Como esta desigualdad sigue siendo cierta cambiando entre si xey, se si |f(x)−f(y)| ≤ M−m ε∥y−x∥ ∀x, y ∈B(a, r). □ A continuaci´on, introducimos el concepto de semicontinuidad, especialmente ´util en casos en los que las funciones no son continuas en el sentido tradicional. Definici´on 1.24 Diremos que una funci´on fes semicontinua inferiormente si ∀x∈Xse tiene f(x)≤l´ım ´ınf z→xf(z). An´alogamente, tenemos la siguiente definici´on. Definici´on 1.25 Diremos que una funci´on fser´a semicontinua superiormente si ∀x∈Xse tiene f(x)≥l´ım sup z→x f(z). TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 1. Funciones convexas 19 Teorema 1.26 Sea Xun espacio de Banach y sea f:X−→ R∪ {+∞} una funci´on convexa semicontinua inferiormente, entonces fes continua en int(dom f). Demostraci´on: Sea a∈int(dom f). Podemos expresar dom f como dom f =[ n∈N {x∈X:f(x)≤n}=[ n∈N [f≤n]. Los conjuntos {x∈X:f(x)≤n}= [f≤n] son cerrados gracias a la semicontinuidad inferior de f. Adem´as dom f =Sn∈N[f≤n]=∅. Como a∈int(dom f), entonces int(Sn∈NFn)=∅. Estamos entonces en condiciones de aplicar el Teorema de Baire,3y por tanto ∃n∈Ntal que int ([f≤n]) =∅yn>f(a). Sea b∈int ([f≤n]), consideremos la funci´on φ(t) = f(a+t(b−a)) con t∈R. Como a∈int(dom f) entonces ∃η > 0 tal que B(a, η∥b−a∥)⊂dom f, lo que implica que [−η, η]⊂dom φ, por lo tanto 0 ∈int(dom φ) y aplicando el Teorema 1.5,φes continua en 0. Como φ(0) < n, ∃α > 0 tal que φ(t)< n en [−α, 0]. Tomamos c=a−α(b−a). Se tiene c∈[f < n] y b∈int([f≤n]). Como a∈[b, c), por una proposici´on auxiliar con C= [f < n]4,a∈int([f≤n]) y entonces por la Proposici´on 1.22 se tiene la continuidad de de fen a. □ Teorema 1.27 Sea f:Rp−→ R∪ {+∞} una funci´on convexa. Entonces fes continua en int(dom f). Demostraci´on: Sea a∈int(dom f). Entonces ∃e0, . . . , ep∈Rpyr > 0 tales que B(a, r)⊂co [e0, . . . , ep]⊂dom f, con co [e0, . . . , ep] la evolvente convexa de e0, . . . , ep. Para todo x∈B(a, r) existe t0, . . . , tp≥0 con p X k=0 tk= 1 y x= p X k=0 tkek, y por ser fconvexa f(x)≤ p X k=0 tkf(ek)≤ p X k=0 tk!m´ax 0≤k≤pf(ek)≤M 3Teorema de Baire: Sea (Fn)n∈Nun conjunto de cerrados de un espacio de Banach tal que int [ n∈N Fn!=∅ entonces ∃n∈Ntal que int Fn=∅. 4Sea C⊂Xun convexo de un espacio normado y sea u∈int(C) y v∈C. Entonces [u, v)⊂int(C) con [u, v) = {λv + (1 −λ)u:λ∈[0,1]}. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 1. Funciones convexas 20 y en consecuencia fcontinua en apor el Teorema 1.21. □ 1.3 Diferenciabilidad de las funciones convexas Sea Xun espacio normado y f:X−→ R∪ {+∞} una funci´on convexa. Proposici´on 1.28 Dado un punto a∈dom f yu∈X, la funci´on φ(t) = 1 tf(a+tu)−f(a) es creciente en (0,+∞). Demostraci´on: Sea 0 < s < t, se tiene a+su =s t(a+tu) + 1−s ta, y por ser fconvexa resulta f(a+su)≤s tf(a+tu) + 1−s tf(a) =⇒φ(s)≤φ(t). □ Definici´on 1.29 A la funci´on f′(a;u) = l´ım t↓0 f(a+tu)−f(a) t∈[−∞,+∞] se le conoce como derivada direccional de fen a. Si f′(a;u)∈R∀u∈Xdiremos que fes derivable direccionalmente en a. Definici´on 1.30 Diremos que una funci´on fes diferenciable en el sentido de Gˆateaux en a si ∃ℓ∈X∗tal que f′(a;·) = ℓ. Observaci´on 1.31 La derivada direccional f′(a;·) es positivamente homog´enea, es decir f′(a;λu) = λf′(a;u)∀u∈Xyλ > 0. Observaci´on 1.32 La derivada direccional f′(a;·) ser´a convexa ya que ∀u∈Xtenemos f′(a, u) = l´ım t→0φt(u) donde φt=1 t(f(a+t(·)) −f(a)) es convexa ∀t > 0. Proposici´on 1.33 Sea f:X−→ R∪+∞una funci´on convexa y sea a∈dom f. Entonces: f(x)≥f(a) + f′(a;x−a)∀x∈X. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 2. Conjugaci´on y subdiferenciabilidad 27 Demostraci´on: Nuestro objetivo es probar que la f∗es convexa y semicontinua inferiormente. Definimos f∗ como f∗= sup u∈dom f φu donde φu:X∗−→ R ℓ7−→ ℓ(u)−f(u) Sean ℓ1, ℓ2∈X∗yα∈[0,1], φu(αℓ1+ (1 −α)ℓ2) = (α ℓ1+ (1 −α)ℓ2)(u)−f(u) =α ℓ1(u) + (1 −α)ℓ2(u)−f(u) =α(ℓ1(u)−f(u)) + (1 −α) (ℓ2(u)−f(u)) =α φu(ℓ1) + (1 −α)φu(ℓ2). Con lo que queda probada la linealidad de φuy en particular su convexidad. Probamos que f∗es convexa, ∀ε > 0∃uε∈dom f, por la definici´on de f∗se tiene: f∗(α ℓ1+ (1 −α)ℓ2)≤φuε(α ℓ1+ (1 −α)ℓ2) + ε ≤α φuε(ℓ1) + (1 −α)φuε(ℓ2) + εpor ser φuεconvexa α f∗(ℓ1) + (1 −α)f∗(ℓ2) + ε, ∀ε > 0 y tomando l´ımite ε→0, se tiene lo que quer´ıamos probar. Veamos que φu: (X∗, σ(X∗, X)) −→ Res semicontinua inferiormente. Sean {ℓn}n≥1una sucesi´on en X∗yℓ0∈X∗tal que ℓn ∗ ⇀ ℓ0en X∗, veamos que φu(ℓ0)≤l´ım infnφu(ℓn) l´ım nφu(ℓn) = l´ım n[ℓn(u)−f(u)] = ℓ0(u)−f(u) = φu(ℓ0) Con lo que hemos probado que φues semicontinua inferiormente, de hecho es continua en X∗ con la topolog´ıa d´ebil-∗. Probamos que f∗es semicontinua inferiormente, para ello supongamos ℓn ∗ ⇀ ℓ0en X∗. Tambi´en ∀ε > 0,∃uεtal que f∗(ℓ0)≤φuε(ℓ0) + ε f∗(ℓ0) = sup u∈dom f φu(ℓ0)≤φuε(ℓ0) + ε ≤l´ım inf nφuε(ℓn) + ε≤l´ım inf nφuε(ℓn) + ε≤l´ım inf nf∗(ℓn) + ε y tomando l´ımite ε→0 se tiene lo que quer´ıamos probar. □ TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 2. Conjugaci´on y subdiferenciabilidad 28 El siguiente teorema establece una relaci´on entre el ´ınfimo de la suma de dos funciones y el m´aximo de la suma de su correspondientes transformadas de Legendre-Fenchel. Este resultado es fundamental de cara a problemas de optimizaci´on. Teorema 2.4 Sean f, g :X−→ R∪ {+∞} funciones convexas tal que existe u0∈dom g con f continua en u0. Entonces ´ınf x∈X(f(x) + g(x)) = m´ax ℓ∈X∗(−f∗(ℓ)−g∗(−ℓ)). Demostraci´on: Sean u∈Xyℓ∈X∗. Por definici´on f∗(ℓ) = sup u∈X (ℓ(u)−f(u)) lo que implica −f∗(ℓ)≤f(u)−ℓ(u)∀u∈X, ∀ℓ∈X∗. An´alogamente, −g∗(−ℓ)≤ℓ(u) + g(u)∀u∈X, ∀ℓ∈X∗. Sumando las dos expresiones, −f∗(ℓ)−g∗(−ℓ)≤f(u) + g(u)∀u∈X, ∀ℓ∈X∗. Tomando en el miembro derecho de la desigualdad el´ınfimo y el supremo en el miembro izquierdo, se tiene: sup ℓ∈X∗ (−f∗(ℓ)−g∗(−ℓ)) | {z } β ≤´ınf u∈X(f(u) + g(u)) | {z } α Sea u0∈dom f ∩dom g, nos planteamos dos posibles casos: Si α=−∞, Tendremos ´ınf u∈Xf(u) + g(u) = −∞, como α≥βentonces β=−∞ con lo que ya tendr´ıamos sup ℓ∈X∗ (−f∗(ℓ)−g∗(−ℓ)) = ´ınf u∈X(f(u) + g(u)), como quer´ıamos probar. Si α∈R, Definimos C=int(epi f) y D={(u, t)∈X×R:t≤α−g(u)} =∅. Al ser fconvexo, epi f tambi´en es convexo, C=∅por ser fcontinua en u0yC∩D=∅ ya que si (u, t)∈Centonces t > f(u) y por la definici´on de α,t > f(u)≥α−g(u), por tanto (u, t)∈ DyC∩D=∅. Aplicando el Teorema B.3 de separaci´on, ∃(ℓ0, s0)∈X∗×R\ {(0,0)}yc∈Rtal que ℓ0(v) + ss0≥c∀(v, s)∈D(2.1) c≥ℓ0(w) + σs0∀(w, σ)∈C(2.2) TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 2. Conjugaci´on y subdiferenciabilidad 29 Tomando l´ımite σ→+∞en c≥ℓ0(w) + σs0deducimos, s0≤0. Supongamos s0= 0, es decir s0<0. De hecho, supongamos sin p´erdida de generalidad s0≡ −1. Por la Proposici´on B.1 la desigualdad (2.2) se extiende a CyC=epi(f), lo que implica, −ℓ0(v) + s≤ −c∀(v, s)∈D. Como se tiene para todo (v, s)∈D, en particular para s=α−g(v) −ℓ0(v) + α−g(v)≤ −c∀v∈X y c≥ℓ0(w)−σ∀(w, σ)∈epi f. Tomando sup v∈X en −ℓ0(v) + α−g(v)≤ −cse tiene g∗(ℓ0)≤ −c−αy por otro lado c≥ℓ0(w)−σ≥ℓ0(w)−f(w) por (w, σ)∈int(epi f) −f∗(ℓ0)≥ −c −g∗(−ℓ0)≥c+α y sumando ambas expresiones α≤ −f∗(ℓ0)−g∗(−ℓ0)≤β≤α. Con lo que ya tendr´ıamos sup ℓ∈X∗ (−f∗(ℓ)−g∗(−ℓ)) = ´ınf u∈X(f(u) + g(u)) para α∈R, como quer´ıamos probar. Nos queda por ver que s0= 0. Por reducci´on al absurdo, supongamos s0= 0. Supongamos r > 0 tal que B(u0, r)⊂dom f, sea z∈B(u0, r) entonces z=u0+wpara w∈B(0, r). Por las desigualdades (2.1), (2.2), ℓ0(u0+w)≤c≤ℓ0(u0)∀w∈B(0, r). Como se tiene ℓ0(u0) + ℓ(w)≤ℓ0(u0), veamos que ℓ(w)≥0. Por reducci´on al absurdo, supongamos 0 ≥ℓ(w)∀w∈B(0, r). Si w∈B(0, r) entonces −w∈B(0, r) por lo tanto 0 ≥ℓ0(−w) = −ℓ0(w) y por lo tanto ℓ0(w)≥0, contradicci´on. Quedando probado ℓ0(w)=0∀z∈B(0, r), contradicci´on pues hab´ıamos supuesto (ℓ0, s0)∈X∗×R\ {(0,0)}. □ TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 2. Conjugaci´on y subdiferenciabilidad 30 Corolario 2.5 Sea f:X−→ R∪ {+∞} una funci´on convexa continua en u∈X, entonces f(u) = m´ax ℓ∈X∗(ℓ(u)−f∗(ℓ)). Proposici´on 2.6 Sea Xun espacio normado y sea φ:R−→ Runa funci´on convexa par. La conjugada de la funci´on f(x) = φ(∥x∥) es la funci´on f∗(x∗) = φ∗(∥x∗∥∗). Demostraci´on: f∗(x∗) = sup x∈R {⟨x, x∗⟩ − φ(∥x∥)} = sup t≥0 sup ∥x∥=tnt⟨x t, x∗⟩ − φ(t)o = sup t≥0 {t∥x∗∥∗−φ(t)} = sup t∈R {t∥x∗∥∗−φ(t)}(por ser φ(t) par) =φ∗(∥x∗∥∗). □ El siguiente teorema establece que una funci´on semicontinua inferiormente siempre tiene una funci´on af´ın que se sit´ua por debajo de la funci´on convexa dada, proporcionando una cota inferior. Teorema 2.7 Sea f:X−→ R∪ {+∞} una funci´on convexa semicontinua inferiormente. Entonces ftiene un minorante af´ın continuo: ∃(ℓ0, c)∈X∗×Rtal que f(w)≥ℓ0(w)−c∀w∈X. Demostraci´on: Podemos suponer sin p´erdida de generalidad que fes propia, es decir que f(x)>−∞ para todo x∈Xyf≡ +∞. Sea u∈dom f yt∈Rtal que t<f(u) entonces (u, t)∈ epi f. Aplicando el Teorema B.4 del Ap´endice, sabemos que existe (ℓ0, s0)∈X∗×R\ {(0,0)}yc∈R tal que ℓ0(u) + ts0> c c > ℓ0(w) + σs0∀(w, σ)∈epi f. Tomando (w, σ)=(u, f(u)) en la desigualdad anterior tendremos ℓ0(u) + s0f(u)< c < ℓ0(u) + s0t, TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 2. Conjugaci´on y subdiferenciabilidad 31 por lo que tendremos s0<0. Dividiendo las desigualdades anteriores por |s0|, podemos suponer s0=−1. Entonces tendremos c≥ℓ0(w)−f(w)∀w∈Xpor lo tanto ℓ0(·)−ces minorante af´ın continuo de f. □ Teorema 2.8 Sea f:X−→ R∪ {+∞} una funci´on convexa semicontinua inferiormente. Entonces ∀u∈X, f(u) = sup ℓ∈X∗ (ℓ(u)−f∗(ℓ)). Demostraci´on: Supongamos que fno es propia, f∗(ℓ) = sup u∈X (ℓ(u)−f(u)) = −∞. Por lo tanto se tiene f(u) = sup ℓ∈X∗ (ℓ(u)−f∗(ℓ)) si fno es propia. Supongamos fpropia. Por la definici´on de f∗se tiene f∗(ℓ)≥ℓ(u)−f(u)∀u∈Xy∀ℓ∈X∗. Tomando supremo f(u)≥sup ℓ∈X∗ (ℓ(u)−f∗(ℓ)). Veamos la otra desigualdad. Sea u∈Xyt∈Rtal que t<f(u). Observamos que (u, t)∈ epi f, y aplicando el Teorema B.4, podemos separar estrictamente {(u, t)}de epi f,∃(ℓ0, s0)∈X∗×R\ {(0,0)}yc∈Rtal que ℓ0(u) + ts0> c (2.3) c > ℓ0(w) + σs0∀(w, σ)∈epi f (2.4) En esta ´ultima desigualdad tomando σ→+∞, deducimos s0≤0. Supongamos s0<0. Suponemos sin p´erdida de generalidad s0=−1: ℓ0(u)−t>c c>ℓ0(w)−σ∀(w, σ)∈epi f. Como se tiene para todo (w, σ)∈epi f, entonces f(w)≤σ, y c≤ℓ0(w)−f(w)∀w∈X, y tomando supremo en X,c≥f∗(ℓ0) y t<ℓ0(u)−c≤ℓ0(u)−f∗(ℓ0)≤sup ℓ∈X∗ (ℓ(u)−f∗(ℓ)). Haciendo t→f(u), resulta f(u)≤sup ℓ∈X∗ (ℓ(u)−f∗(ℓ)). TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 2. Conjugaci´on y subdiferenciabilidad 32 Supongamos s0= 0. Aplicando el teorema anterior, ∃(ℓ, c)∈X∗×Rtal que f(w)≥ℓ(w)−c∀w∈X. Por las desigualdades (2.3) y (2.4) con s0= 0, resulta ℓ0(u)> c c > ℓ0(w)∀w∈dom f. Sea β > 0, por la desigualdad anterior 0 > ℓ0(w)−c f(w)≥ℓ(w)−c+β(ℓ0(w)−c)∀w∈X. Denotando ˜ ℓ=ℓ+βℓ0, se tiene ˜ ℓ(w)−f(w)≤c+βc ∀w∈dom f, y tomando supremo en X, f∗(˜ ℓ)≤c+βc Por lo tanto se tiene ˜ ℓ(u)−f∗(˜ ℓ) = ℓ+βℓ0−f∗(˜ ℓ) ≥ℓ+βℓ0−c−βc =ℓ−c+β(ℓ0−c). Al ser ℓ0(u)−c > 0 y tomando β > 0 suficientemente grande, se deduce ℓ(u)−c+β(ℓ0(u)−c)> t. Tomando supremo en ℓ∈X∗, sup ℓ∈X∗ (ℓ(u)−f∗(ℓ)) ≥˜ ℓ(u)−f∗(˜ ℓ)≥ℓ(u)−c+β(ℓ0(u)−c)> t. Tomando l´ımite t→f(u), f(u)≤sup ℓ∈X∗ (ℓ(u)−f∗(ℓ)). □ Definici´on 2.9 Denotamos por Γ0(X) al conjunto de funciones f:X−→ R∪ {+∞} convexas semicontinuas inferiormente y propias. Definici´on 2.10 Denotamos Γ0(X∗) el conjunto de funciones f∗:X∗−→ R∪ {+∞} convexas semicontinuas inferiormente para la topolog´ıa σ(X∗, X) y propias. Observaci´on 2.11 En la Definici´on 2.9 no podemos cambiar la topolog´ıa σ(X∗, X) por la topolog´ıa fuerte de X∗, salvo si Xes reflexivo. Sin embargo, en la Definici´on 2.10 no es necesario considerar la topolog´ıa σ(X, X∗) ya que la semicontinuidad para esta topolog´ıa y la topolog´ıa fuerte es equivalente para funciones convexas. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 2. Conjugaci´on y subdiferenciabilidad 33 2.1.4. La biconjugada Definici´on 2.12 Sea Yun espacio normado y sea X=Y∗dotado de la topolog´ıa σ(Y∗, Y ). La conjugada de una funci´on g:X∗−→ Res la funci´on g∗:X−→ Rdefinida por g∗(x) = sup ℓ∈X∗ (ℓ(u)−g(ℓ)) ∀x∈X. Definici´on 2.13 Sea X∗dotado de la topolog´ıa de la norma, la biconjugada de una funci´on f:X−→ Res la funci´on f∗∗ :X∗∗ −→ Rdefinida por f∗∗(λ) = sup ℓ∈X∗ (λ(ℓ)−f∗(ℓ)) ∀λ∈X∗∗. 2.2 Subdiferenciabilidad El concepto de subdiferenciabilidad surge como soluci´on a la falta de derivabilidad de determinadas funciones. El objetivo principal del subdiferencial de una funci´on es el de detectar puntos m´ınimos. Definici´on 2.14 Sea f:X−→ R∪ {+∞} ya∈dom f. La subdiferencial de fen aes el conjunto (que puede ser vac´ıo) de ℓ∈X∗tales que ∂f(a) = {ℓ∈X∗|ℓ(x−a)≤f(x)−f(a),∀x∈X}. Llamamos subgradiente de fen aa cada ℓ∈∂f(a).Si ∂f(a)=∅decimos que fes subdiferenciable en a. De la propia definici´on se deduce que ∂f(a) es convexo y σ(X∗, X)-cerrado. Otra definici´on an´aloga para el concepto del subdiferencial en espacios de Hilbert es la siguiente: Sea Xun espacio de Hilbert y X∗su dual topol´ogico. Identificando Xcon su dual topol´ogico, entonces el subdiferencial de una funci´on f:X−→ R∪ {+∞} es un subconjunto de Xy tendremos ∂f(a) = {y∈X|⟨x−a, y⟩ ≤ f(x)−f(a),∀x∈X}. Obs´ervese que la funci´on f:X−→ R∪ {+∞} alcanza su m´ınimo en a∈dom f si y solo si 0∈∂f(a). Esta sustituye la condici´on de optimalidad ∂f(a) = 0 para el caso de fdiferenciable. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 2. Conjugaci´on y subdiferenciabilidad 34 2.2.1. Ejemplos Ejemplo 2.15 Sea f:X∈R7−→ f(x) = |x|, entonces ∂f(x) = −1 si x < 0, ∂f(x)=[−1,1] si x= 0, ∂f(x) = 1 si x > 0. Figura 2.2: Representaci´on de fy∂f(x). Proposici´on 2.16 Sea f:R−→ R∪{+∞} una funci´on convexa y sea a∈int(dom f), se tiene ∂f(a)=[f′ −(a), f′ +(a)]. Demostraci´on: Supongamos ℓ∈∂f(a) entonces, ℓ(x−a)≤f(x)−f(a)∀x > a. Suponemos sin p´erdida de generalidad que ℓ:x7−→ sx ∀x∈R. s(x−a)≤f(x)−f(a)∀x > a. Dividiendo por x−acon x>ay tomando l´ımite x→a+, s≤l´ım x→a+ f(x)−f(a) x−a=f′ +(a). An´alogamente, de s(x−a)≤f(x)−f(a)∀x<a llegamos a s≥f(x)−f(a) x−a∀x < a. Tomando l´ımite x→a−, obtenemos la desigualdad s≥f′ −(a). TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 2. Conjugaci´on y subdiferenciabilidad 35 Hemos probado ∂f(a)⊂[f′ −(a), f′ +(a)]. Veamos a continuaci´on la otra inclusi´on. Supongamos s∈[f′ −(a), f′ +(a)], entonces f′ −(a)≤s≤f′ +(a), a su vez, f(x)−f(a) x−a≤f′ −(a)∀x < a, y f′ +(a)≤f(x)−f(a) x−a∀x > a. Por lo tanto, f(x)−f(a)≤s(x−a)∀x<a ys(x−a)≤f(x)−f(a)∀x > a, de donde se deduce f(x)−f(a)≥s(x−a)∀x∈R, y finalmente s∈∂f(a). □ Definici´on 2.17 Sea A⊂X, la funci´on indicatriz iAde Ase define por iA(x) =    0 si x∈A +∞si x∈X\A. Definici´on 2.18 Sea C⊂Xun conjunto y x∈C. El cono normal de Cen x∈Ces el conjunto NC(x) = ∂iC(x) = {ℓ∈X∗:ℓ(y−x)≤0∀y∈C}. Figura 2.3: Cono normal de Cen x. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 2. Conjugaci´on y subdiferenciabilidad 36 2.2.2. Algunas propiedades Proposici´on 2.19 Sea f:X−→ R∪ {+∞} una funci´on convexa y a∈dom f. Las siguientes propiedades son equivalentes: a) ℓ∈∂f(a), b) f(a) + f∗(ℓ)≤ℓ(a), c) f(a) + f∗(ℓ) = ℓ(a). Demostraci´on (a) =⇒(b). Supongamos ℓ∈∂f(a), entonces por definici´on, ℓ(x−a)≤f(x)−f(a) =⇒ℓ(x)−f(x)≤ℓ(a)−f(a). y tomando sup x∈X se tiene f(a) + f∗(ℓ)≤ℓ(a). (b) =⇒(c). Por la definici´on de la conjugada de Fenchel se tiene f∗(ℓ)≥ℓ(x)−f(x)∀x∈X, en particular se tiene f∗(ℓ)≥ℓ(a)−f(a), y junto con (b) se tiene f(a) + f∗(ℓ) = ℓ(a). (c) =⇒(a). Por hip´otesis, f(a) + f∗(ℓ) = ℓ(a) =⇒f(a) + f∗(ℓ)−ℓ(a)=0, por la definici´on de f∗, f(a) + f∗(ℓ)−ℓ(a)≥f(a) + ℓ(x)−f(x)−ℓ(a), por lo tanto, f(x)≥f(a) + ℓ(x−a) y finalmente ℓ∈∂f(a). □ Observaci´on 2.20 Sea ℓ∈∂f(a), se tiene ℓ(· − a) + f(a) es un minorante af´ın continuo de f. El siguiente teorema nos garantiza la existencia de subgradiente en funciones convexas y continuas. Teorema 2.21 Sea f:X−→ R∪ {+∞} una funci´on convexa y continua en a∈dom f. El conjunto ∂f(a)es no vac´ıo, acotado y σ(X∗, X)-compacto. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 3. Introducci´on a la optimizaci´on convexa 43 Corolario 3.2 Sean K1, . . . , Kn⊂Xsubconjuntos convexos tales que n \ i=1 int(Ki)= 0. Entonces ∀x∈K:= n \ i=1 int(Ki), se tiene NK(x) = NK1(x) + · · · +NKn(x). Demostraci´on: Por un lado, sabemos que iK=iK1+· · · +iKn. Sea x0∈ n \ i=1 int(Ki), entonces iK1, . . . , iKnson funciones continuas en x0. Por el teorema anterior, NK(x) = ∂(iK1+· · · +iKn)(x) =∂iK1(x) + · · · +∂iKn(x) =NK1(x) + · · · +NKn(x). □ Teorema 3.3 (Condici´on de optimalidad) Sea f:X−→ R∪ {+∞} una funci´on convexa. Sea K⊂Xun convexo en el que se verifica una de las siguientes hip´otesis: a) fes continua en un punto u∈K, b) int(K)∩dom f =∅. Entonces, xes un m´ınimo global de (f+iK)si y s´olo si ∂f(x)∩(−NK(x)) =∅. Demostraci´on: Se tiene que xes un m´ınimo global de f+iKsi y solo si 0 ∈∂(f+iK)(x). Supongamos que se tiene a), en ese caso fes continua en un punto de dom(iK). Por otro lado supongamos que se cumple b). Entonces, iKes continua en un punto de int(K)∩ dom f por ser 0 en un entorno de dicho punto. En ambos casos, aplicando el Teorema 3.1 se tiene ∂(f+iK)(x) = ∂f(x) = ∂f(x) + ∂iK(x) = ∂f(x) + NK(x). Finalmente, 0 ∈∂(f+iK)(x) si y solo si ∂f(x)∩(−NK(x)) =∅, con lo que se tiene lo que quer´ıamos probar. □ La demostraci´on del siguiente teorema y su corolario se pueden encontrar en [1]. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 3. Introducci´on a la optimizaci´on convexa 44 Teorema 3.4 Sea f:X−→ Runa funci´on convexa continua tal que [f < 0] =∅, sea K= [f≤0] yx0∈K, se tiene NK(x0) =    {0}si f(x0)<0 R+(∂f(x0)) si f(x0)=0. Corolario 3.5 Sea f:X−→ Runa funci´on convexa continua tal que [f < 0] =∅, y sea K= [f≤0]. Entonces para todo x∈K, las siguientes propiedades son equivalentes: a) ℓ∈NK(x), b) existe λ≥0 tal que ℓ∈λ∂f(x) y λf(x) = 0. 3.2.1. El Teorema de Kuhn-Tucker En lo sucesivo consideramos el siguiente problema de minimizaci´on: P(f, f1, . . . , fn) : m´ın x∈X(f(x) + iK(x)) donde f:X−→ R∪{+∞} es una funci´on convexa, f1, . . . , fn:X−→ Rson funciones convexas y donde Kest´a definido por K= n \ i=1 Ki con Ki={x∈X:fi≤0}:= [fi≤0]. Consideramos la siguiente hip´otesis (H1), (H1)fes continua en un punto x0∈ n \ i=1 [fi<0]. Veamos una condici´on necesaria y suficiente para el problema P(f, f1, . . . , fn). Teorema 3.6 (Teorema de Kuhn-Tucker) Supongamos que se verifica la hip´otesis (H1). Entonces, x∈Xes soluci´on de P(f, f1, . . . , fn)si y solo si existe (λ1, . . . , λn)∈Rn +tal que    0∈∂f(x) + λ1∂f1(x) + · · · +λn∂fn(x) λifi(x)=0 ∀i∈[1, n]. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 3. Introducci´on a la optimizaci´on convexa 45 Demostraci´on: Se tiene que xes soluci´on de P(f, f1, . . . , fn) si y solo si 0∈∂(f+iK)(x). Por otro lado, fes continua en x0∈ n \ i=1 [fi<0] ⊂int(K) por hip´otesis, es decir fes continua en x0∈dom(iK). Aplicando el Teorema 3.1 resulta 0∈∂(f+iK)(x) = ∂f(x) + ∂iK(x) = ∂f(x) + NK(x), y aplicando el Corolario 3.2 0∈∂f(x) + NK1(x) + · · · +NKn(x). Finalmente, como n \ i=1 [fi<0] =∅, aplicando el Corolario 3.5 se tiene lo que quer´ıamos probar. □ Definici´on 3.7 Definimos el conjunto de vectores de Kuhn-Tucker asociados al problema P(f, f1, . . . , fn), como el conjunto dado por KT (f, f1, . . . , fn) = (λ∈Rn +: ´ınf X f+ n X i=1 λifi!= ´ınf X(f+iK)∈R). Observaci´on 3.8 Para la definici´on de vectores de Kuhn-Tucker estamos imponiendo que −∞ <´ınf x∈X(f(x) + iK(x)) <+∞. Teorema 3.9 Supongamos que se verifica la hip´otesis (H1), sea x∈Xuna soluci´on de P(f, f1, . . . , fn). Entonces existe λ∈ KT (f, f1, . . . , fn)tal que x∈argmin f+ n X i=1 λifi!. Demostraci´on: Por el teorema anterior, al ser xuna soluci´on de P(f, f1, . . . , fn), existe (λ1, . . . , λn)∈Rn +tal que 0∈∂f(x) + λ1∂f1(x) + · · · +λn∂fn(x)⊂∂ f+ n X i=1 λifi!(x). Por lo tanto x∈argmin f+ n X i=1 λifi!. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 3. Introducci´on a la optimizaci´on convexa 46 Por otro lado, como λifi(x) = 0 para todo i= 1, . . . , n, se tiene f+ n X i=1 λifi!(x) = f(x) = ´ınf X(f+iK)∈R. Por lo tanto λ∈ KT (f, f1, . . . , fn) y queda finalizada la prueba. □ Definici´on 3.10 Llamamos funci´on valor asociada al problema P(f, f1, . . . , fn) a la funci´on definida como p:Rn−→ R y7−→ ´ınf P(f, f1−y1, . . . , fn−yn) = ´ınf{f(x) : f1(x)≤y1, . . . , fn(x)≤yn}. Observaci´on 3.11 La funci´on valor pdefinida anteriormente es convexa. Ve´amoslo. Para ello definimos la funci´on F:X×Rn−→ R∪ {+∞} (x, y)7−→ f(x) + iC(x, y) con C={(x, y)∈X×Rn:f1(x)≤y1, . . . , fn(x)≤yn}conjunto convexo. La funci´on Fes convexa. Entonces, basta con apliclar la Proposici´on 1.18 a p(y) = ´ınf x∈XF(x, y) para deducir que pes convexa. Mediante el siguiente teorema obtenemos una caracterizaci´on del conjunto de vectores de Kuhn- Tucker. Teorema 3.12 Se tiene la siguiente igualdad KT (f, f1, . . . , fn) = −∂p(0). Demostraci´on: Veamos ⊂. Sea λ∈ KT (f, f1, . . . , fn). Por la definici´on de p, p(0) = ´ınf x∈X(f(x) + iK(x)) = ´ınf x∈X f(x) + n X i=1 λifi(x)!, TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 3. Introducci´on a la optimizaci´on convexa 47 por lo que se tiene p(0) ∈R. Para todo x∈Xtal que fi(x)≤yicon i= 1, . . . , n, se satisface p(0) ≤´ınf x∈X f(x) + n X i=1 λiyi!, o lo que es lo mismo p(0) ≤´ınf x∈X{f(x)|fi(x)≤yi∀i= 1, . . . , n}+ n X i=1 λiyi p(0) ≤p(y) + n X i=1 λiyi. Esto implica λy ≤p(y)−p(0) y −λ∈∂p(0) y finalmente λ∈ −∂p(0). Por otro lado, veamos ⊃. Sea λ∈ −∂p(0). En primer lugar veamos que λ∈Rn +. Sea u∈Rn +, entonces p(u)≤p(0) ya que {x∈X:f1(x)≤0, . . . , fn(x)≤0}⊂{x∈X:f1(x)≤u1, . . . , fn(x)≤un} Como p(u)≤p(0) para cualquier u∈Rn +, se tiene p′(0; u) = l´ım t↓0 p(tu)−p(0) t≤0. Por otro lado, como −λ∈∂p(0) aplicando la definici´on del subdiferencial p(tei)≥p(0) −λ(tei) para todo ty para todo i∈ {1, . . . , n}. Luego −λi=⟨−λ, ei⟩ ≤ p′(0; ei)≤0, por lo que λ∈Rn +. Nos queda probar ´ınf x∈X f(x) + n X i=1 λifi!= ´ınf x∈X(f(x) + iK(x)) = p(0). Sea x∈Xtal que fi(x) = yipara todo i∈ {1, . . . , n}. Se tiene p(0) ≤p(y) + ⟨λ, y⟩ ≤ f(x) + n X i=1 λifi(x), y tomando ´ınfimo, resulta p(0) ≤´ınf x∈X f(x) + n X i=1 λifi(x)!. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 3. Introducci´on a la optimizaci´on convexa 48 Sea f1, . . . , fntal que f1(x)≤0, . . . , fn(x)≤0, como hemos probado λi≥0 para i∈ {1, . . . , n}, se tiene f(x)≥f(x) + n X i=1 λifi(x)≥´ınf x∈X f+ n X i=1 λifi!. Tomando ´ınfimo en el miembro de la izquierda de la desigualdad, deducimos p(0) ≥´ınf x∈X f(x) + n X i=1 λifi(x)!, y finalmente ´ınf x∈X f(x) + n X i=1 λifi(x)!= ´ınf x∈X(f(x) + iK(x)) ∈R Esto da que λ∈ KT (f, f1, . . . , fn), como quer´ıamos probar. □ El siguiente resultado nos facilita una estimaci´on de la variaci´on de la funci´on valor p. Teorema 3.13 Sean y, y ∈Ry sean λ∈ KT (f, f1−y1, . . . , fn−yn), λ ∈ KT (f, f1−y1, . . . , fn−yn). Entonces ⟨λ, y −y⟩ ≤ p(y)−p(y)≤ ⟨λ, y −y⟩. Demostraci´on: Denotamos, para todo z∈Rn q(z) = p(y+z). Como −λ∈∂q(0) se tiene −λ∈∂p(y), y en consecuencia ⟨−λ, y −y⟩ ≤ p(y)−p(y) =⇒p(y)−p(y)≤ ⟨λ, y −y⟩. Si cambiamos ypor y, se obtiene la otra desigualdad buscada. □ TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 4 Dualidad en optimizaci´on convexa En este cap´ıtulo continuamos nuestro estudio de problemas de optimizaci´on convexa. Para ello introducimos la noci´on de problemas perturbados as´ı como el de Lagrangiano de la funci´on de perturbaci´on, y estudiaremos algunas de sus propiedades. Un estudio m´as detallado se puede encontrar en [4] y en [7]. 4.1 Problemas perturbados Consideramos los espacios normados X, W y sus respectivos duales topol´ogicos X∗yW∗. Consideramos tambi´en una funci´on convexa F:X×W−→ R∪ {+∞} a la que nos referimos como la funci´on de perturbaci´on. Como en otros cap´ıtulos de esta memoria, denotamos por ⟨w, w∗⟩el valor de la forma lineal w∗∈W∗en el punto w∈W. Observamos que (X×W)∗=X∗×W∗por lo tanto para (x∗, w∗)∈X∗×W∗y para (x, w)∈ X×Wtendremos ⟨(x, w),(x∗, w∗)⟩=⟨x, x∗⟩+⟨w, w∗⟩. Consideramos el problema primal asociado a la funci´on de perturbaci´on F (P) m´ın x∈XF(x, 0). Consideramos tambi´en, de manera similar a como ya hicimos en el Cap´ıtulo 3, la funci´on valor p:W−→ Rcomo p(w) = ´ınf x∈XF(x, w). Observaci´on 4.1 La funci´on p:W−→ Res convexa. Demostraci´on: Trivial por la Proposici´on 1.18. □ Observaci´on 4.2 Para todo w∗∈W∗tenemos, p∗(w∗) = F∗(0, w∗) 50 Cap´ıtulo 4. Dualidad en optimizaci´on convexa 51 ya que, p∗(w∗) = sup w∈W (⟨w, w∗⟩ − ´ınf x∈XF(x, w)) = sup (x,w)∈X×W (⟨x, 0⟩+⟨w, w∗⟩ − F(x, w)) = sup (x,w)∈X×W (⟨(x, w),(0, w∗)⟩ − F(x, w)) = F∗(0, w∗). Definimos el problema dual asociado a la funci´on de perturbaci´on Fpor (D) m´ın w∗∈W∗F∗(0, w∗). Proposici´on 4.3 Siempre se cumple ´ınf(P)≥ −´ınf(D). Demostraci´on: Para todo x∈Xyw∗∈W∗, por la definici´on de F∗(0, w∗), se satisface F(x, 0) + F∗(0, w∗)≥ ⟨(x, 0),(0, w∗)⟩=⟨x, 0⟩+⟨0, w∗⟩= 0 y tomando ´ınf en x∈Xy en w∗∈W∗se obtiene lo que quer´ıamos probar. □ Proposici´on 4.4 Supongamos psubdiferenciable en 0. Sea w∗∈∂p(0), entonces w∗es soluci´on de Dy ´ınf(P) = −´ınf(D)∈R. Demostraci´on: Por hip´otesis, como w∗∈∂p(0), aplicando la Proposici´on 2.19, se obtiene 0 = ⟨0, w∗⟩=p(0) + p∗(w∗) = ´ınf(P) + p∗(w∗). En consecuencia, ´ınf(D)≤F∗(0, w∗) = p∗(w∗) = −´ınf(P)≤´ınf(D), y por tanto tenemos la igualdad que quer´ıamos probar. □ Teorema 4.5 Sea Xun espacio normado, g:X−→ Runa funci´on convexa y sea x0∈Xtal que existe t0∈Rcon (x0, t0)∈int(epi g). Entonces, si g(x0)∈Rtendremos g(x)>−∞ para todo x∈X. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 4. Dualidad en optimizaci´on convexa 52 Demostraci´on: Sea s0∈Rtal que s<g(x0), por lo tanto (x0, s0)∈ epi g. Al ser gconvexa se tiene la convexidad de epi g por lo que aplicando el Teorema B.3 con epi g yD={(x0, s0)}, existe (ℓ, α)∈X∗×R\ {(0,0)}, tal que ℓ(x0) + αs0≤ℓ(x)≤ℓ(x) + αt ∀(x, t)∈epi g. Si tomamos t→+∞, de la segunda desigualdad se deduce que α≥0. De hecho se tiene α > 0. Para comprobarlo, razonemos por reducci´on al absurdo. Supongamos α= 0, entonces ℓ(x0)≤ℓ(x)∀x∈dom g. Como (t0, x0)∈int(epi g), existe r > 0, tal que la bola B(x0, r)⊂dom g, y entonces la desigualdad anterior da ℓ(x0)≤ℓ(x)∀x∈B(x0, r), lo que implica ℓ= 0. Por lo tanto (ℓ, α) = (0,0),llegando a contradicci´on. Sabiendo que α > 0, podemos dividir ℓ(x0) + αs0≤ℓ(x) + αt por α, obteniendo t≥1 αℓ(x0−x) + s0∀(x, t)∈epi g, y en particular para t=g(x), esto da g(x)≥1 αℓ(x0−x) + s0∀x∈X, con lo cual g(x)>−∞ para todo x∈X, como quer´ıamos probar. □ Teorema 4.6 Supongamos que ´ınf(P)∈R y que se cumple la siguiente hip´otesis (H1) existe x0∈Xtal que F(x0,·)est´a acotada y es continua en 0. Entonces, pes continua en 0, w∗∈∂p(0) si y solo si w∗es soluci´on de D, ´ınf P=−m´ın D ∈ R. Demostraci´on: TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 4. Dualidad en optimizaci´on convexa 59 Para terminar, veamos cuales son los puntos silla de F. Por el Teorema 4.13, (x, w∗) es un punto silla del Lagrangiano asociado a Fsi y solo si F(x, 0) = −F∗(0, w∗) es decir, Φ(A(x)) + Ψ(x) = −Φ∗(w∗)−Ψ∗(−A∗(w∗)). Como por definici´on ⟨A(x), w∗⟩=⟨x, A∗(w∗)⟩, la anterior desigualdad se puede reescribir Φ(A(x)) + Φ∗(w∗)− ⟨A(x), w∗⟩+ Ψ(x)+Ψ∗(−A∗(w∗)) + ⟨x, A∗(w∗)⟩= 0. Por la definici´on de la transformada de Legendre-Fenchel se tiene Φ(A(x)) + Φ∗(w∗)− ⟨A(x), w∗⟩ ≥ 0 y Ψ(x)+Ψ∗(−A∗(w∗)) + ⟨x, A∗(w∗)⟩ ≥ 0, y en consecuencia Φ(A(x)) + Φ∗(w∗)− ⟨A(x), w∗⟩= 0 y Ψ(x)+Ψ∗(−A∗(w∗)) + ⟨x, A∗(w∗)⟩= 0. Por la Proposici´on 2.19 esto equivale a w∗∈∂Φ(A(x)) y −A∗(w∗)∈∂Ψ(x). En resumen, un punto (x, w∗)∈X×Yes un punto silla de Lsi y solo si w∗∈∂Φ(A(x)) y −A∗(w∗)∈∂Ψ(x). . TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 5 Un problema de control lineal cuadr´atico En este cap´ıtulo veremos c´omo la teor´ıa de dualidad convexa permite tratar manera muy sencilla la b´usqueda de condiciones necesarias y suficientes de optimalidad para un problema de control lineal cuadr´atico. 5.1 Problema de control lineal cuadr´atico Veamos la primera aplicaci´on en la que nos centraremos en la obtenci´on de condiciones necesarias y suficientes de optimalidad de un sistema de control. En primer lugar consideramos Vy (H, ⟨·,·⟩) dos espacios de Hilbert tal que la inyecci´on de V en Hes continua y densa. Por el Teorema de Riesz, identificando Hcon su dual topol´ogico H∗, se tiene H⊂V∗. La acci´on de un elemento de f∈H(que puede ser visto como uno en V∗) sobre v∈Vser´a ⟨v, f⟩, y entonces por la continuidad que hemos supuesto en la inyecci´on de V en H, se tendr´a |⟨v, f⟩| ≤ ∥f∥H∥v∥H≤c∥f∥H∥v∥V, lo que prueba que la inyecci´on de Hen V∗es continua. Tambi´en se tiene la densidad de la inyecci´on Hen V∗ya que, si existe v∈Vtal que ⟨v, f⟩= 0 para todo f∈H, entonces tomando f=vse obtiene ∥v∥2 H= 0 luego v= 0. Denotamos tambi´enpor ⟨v, ℓ⟩la dualidad entre v∈Vyℓ∈V∗. Sea a(·,·) : V×V−→ Runa forma bilineal continua y coercitiva en V. Sea A:V−→ V∗el isomorfismo definido por A(u) = a(u, ·)∀u∈V. 60 Cap´ıtulo 5. Un problema de control lineal cuadr´atico 61 Recordemos que si definimos a∗:V×V−→ Rpor a∗(u, v) = a(v, u), entonces A∗(v) = a∗(·, v)∀v∈V. Sean Uel espacio de Hilbert de control y Hun espacio de Hilbert. Sean B∈ L(U, V ∗) y C∈ L(V, H). Sea tambi´en N∈ L(U,U) un operador lineal sim´etrico definido positivamente. Consideramos el siguiente problema de control ´optimo: Sean Uad un convexo cerrado de U,f∈V∗yzd∈ H. Para todo v∈ Uad existe un ´unico elemento y∈Vtal que A(y) = B(v) + f. Nuestro objetivo es hallar u∈ Uad tal que v7−→ 1 2∥C(y)−zd∥2 H+1 2⟨Nv, v⟩U alcance el m´ınimo en Uad en v=u. En la funci´on a minimizar, yes el estado asociado a v, es decir, la soluci´on de A(y) = B(v) + f, mientras que C(y) representa una observaci´on sobre dicho estado. La soluci´on u∈ Uad es un control optimal. Por lo tanto buscamos resolver el siguiente problema de minimizaci´on: (P) m´ın v∈Uad 1 2∥CA−1(B(v) + f)−zd∥2 H+1 2⟨Nv, v⟩U Nos encontramos en un caso de optimizaci´on de una funci´on convexa ya que J:U −→ R∪{+∞} definida para todo v∈ U por J(v) = 1 2∥CA−1(B(v) + f)−zd∥2 H+1 2⟨Nv, v⟩U+iUad (v) es estrictamente convexa, propia, semicontinua inferiormente (de hecho es continua) y coercitiva. Por ello, el problema m´ın v∈Uad 1 2∥CA−1(B(v) + f)−zd∥2 H+1 2⟨Nv, v⟩U tiene una ´unica soluci´on. Vamos a transformar la funci´on de la cual nos interesa hallar el m´ınimo en una funci´on perturbada con el fin de poder aplicar la teor´ıa de dualidad. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 5. Un problema de control lineal cuadr´atico 62 (P) es equivalente al siguiente problema m´ın (y,v)∈V×U F((y, v),0) donde F: (V× U)×V∗−→ R∪ {+∞} est´a definida para todo ((y, v), g)∈(V× U)×V∗por F((y, v), g) = 1 2∥Cy −zd∥2 H+1 2⟨Nv, v⟩U+iC((y, v), g), con C={((y, v), g)∈(V× Uad)×V∗:Ay =f+Bv +g}. Ahora veamos el Lagrangiano asociado al problema (P). En primer lugar, por definici´on, L((y, v), p) = ´ınf g∈V∗ 1 2∥Cy −zd∥2 H+1 2⟨Nv, v⟩U+iC((y, v), g)− ⟨p, g⟩. Por otro lado, iC((y, v), g) =    0 si v∈ Uad yg=A(y)−B(v)−f +∞en c.c. Por lo tanto, L((y, v), p) = 1 2∥Cy −zd∥2 H+1 2⟨Nv, v⟩U− ⟨p, Ay −f−Bv⟩+iUad (v)∀((y, v), p)∈(V×U)×V. Introducimos la funci´on valor asociada a F, que por existir en nuestra formulaci´on la variable p, denotaremos por φ(ver Definici´on 3.10), φ(g) = ´ınf (y,v)∈V×U F((y, v), g) Nuestro objetivo es probar la existencia de soluci´on del problema dual asociado, por lo que buscamos aplicar el Teorema 4.6. Al ser A:V−→ V∗un isomorfismo, existe ρ > 0 tal que supg∈BV∗∥A−1(f+Bv +g)∥V≤ρ. Por otro lado sup g∈BV∗ φ(g)≤1 2∥Cy −zd∥2 H+1 2⟨Nv, v⟩U+iC((y, v), g)∀(y, v)∈V× Uad, o lo que es lo mismo, sup g∈BV∗ φ(g)≤1 2∥CA−1(f+Bv +g)−zd∥2 H+1 2⟨Nv, v⟩U∀v∈ Uad. Aplicando la desigualdad triangular, sup g∈BV∗ φ(g)≤1 2(∥CA−1(f+Bv +g)∥H+∥zd∥H)2+1 2⟨Nv, v⟩U∀v∈ Uad, TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 5. Un problema de control lineal cuadr´atico 63 y que C∈ L(V, H), se obtiene sup g∈BV∗ φ(g)≤1 2(∥C∥L(V,H)∥A−1(f+Bv +g)∥H+∥zd∥H)2+1 2⟨Nv, v⟩U∀v∈ Uad. Por otro lado, ∥A−1(f+Bv +g)∥H≤c∥A−1(f+Bv +g)∥V≤cρ. Finalmente, por ser Nun operador lineal sim´etrico definido positivo, sup g∈BV∗ φ(g)≤1 2(∥C∥L(V,H)cρ +∥zd∥H)2+1 2∥N∥∥v∥2 Por lo que tenemos la continuidad de φen 0, y aplicando el teorema mencionado tendremos la existencia de soluci´on y tambi´en que ´ınf(P) = −´ınf(D). Continuamos con la obtenci´on de una condici´on necasaria y suficiente de optimalidad del problema (P). Tanto el problema (P) como su dual asociado tienen soluci´on. Sea (y, v)∈V× Uad la soluci´on de Pyp∈Vsoluci´on del problema dual (D). Por el Teorema 4.13, ((y, v), p) es un punto silla del Lagrangiano Ly por la Observaci´on 4.12, L′ (y,v)(((y, v), p); (y, v)−(y, v)) ≥0∀(y, v)∈V× Uad (5.1) y L′ p(((y, v), p); (y, v)−(y, v)) ≤0∀p∈V, con L′ (y,v)(((y, v), p); (z, w)) = l´ım t↓0 L((y+tz, v +tw), p)−L((y, v), p) t y L′ p(((y, v), p); q) = l´ım t↓0 L((y, v), p +tq)−L((y, v), p) t. Estudiemos el valor de L′ (y,v)(((y, v), p); (z, w)). Por un lado L((y+tz, v +tw), p) = 1 2∥C(y+tz)−zd∥2 H+1 2⟨N(v+tw), v +tw⟩−⟨p, A(y+tz)−f−B(v+tw)⟩. Desarrollando 1 2∥C(y+tz)−zd∥2 Htenemos 1 2∥C(y+tz)−zd∥2 H=1 2∥Cy +tCz −zd∥2 =1 2∥Cy −zd∥2+t⟨Cy −zd, Cz⟩+t2∥Cz∥2. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 5. Un problema de control lineal cuadr´atico 64 Desarrollando 1 2⟨N(v+tw), v +tw⟩y teniendo en cuenta que Nes sim´etrico, deducimos 1 2⟨N(v+tw), v +tw⟩=1 2⟨Nv +tNw), v +tw⟩ =1 2(⟨Nv, v +tw⟩+t⟨Nw, v +tw⟩) =1 2⟨Nv, v⟩+1 2t⟨Nv, w⟩+1 2t⟨Nw, v⟩+1 2t2⟨Nw, w⟩ =1 2⟨Nv, v⟩+t⟨Nv, w⟩+1 2t2⟨Nw, w⟩, con ayuda de las expresiones anteriores, teniendo en cuenta que L((y, v), p) = 1 2∥Cy −zd∥2+1 2⟨Nv, v⟩−⟨p, Ay −f−Bv⟩ restando, dividiendo por ty tomando el l´ımite cuando t↓0, la condici´on 5.1 da ⟨Cy −zd, C(y−y)⟩H− ⟨A(y−y), p⟩+⟨Nv, v −v⟩U+⟨B(v−v), p⟩ ≥ 0 para todo (y, v)∈V× Uad. Procediendo an´alogamente para L′ p(((y, v), p); q) deducimos ⟨A(y)−f−Bv, p −p⟩ ≥ 0∀p∈V. Por lo tanto, tenemos ⟨C(y)−zd, C(y−y)⟩H− ⟨A(y−y), p⟩ ≥ 0∀y∈V ⟨Nv, v −v⟩U+⟨B(v−v), p⟩ ≥ 0∀v∈ Uad y ⟨A(y)−f−Bv, p −p⟩ ≥ 0∀p∈V. Al ser p∈Vsoluci´on del problema dual, Ay =f+Bv. Recordemos que B∈ L(U, V ∗) y C∈ L(V, H). As´ı mismo B∗∈ L(V, U∗) y C∗∈ L(H∗, V ∗). Sean ΛH:H −→ H∗y ΛU:U −→ U∗los isomorfismos de Riesz que identifican HyU con sus respectivos duales topol´ogicos. Con ayuda de estos isomorfismos podemos reescribir las desigualdades anteriores como ⟨C∗ΛH(Cy −zd)−A∗p, y −y⟩ ≥ 0∀y∈V y ⟨Λ−1 UB∗p+Nv, v −v⟩U≥0∀v∈ Uad. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 5. Un problema de control lineal cuadr´atico 65 Las condiciones necesarias y suficientes de optimalidad por lo tanto son las siguientes:          Ay =f+Bv A∗p=C∗ΛH(Cy −zd) ⟨Λ−1 UB∗p+Nv, v −v⟩U≥0 para todo v∈ Uad. En el caso particular de U=Uad, entonces estas condiciones quedar´ıan          Ay =f+Bv A∗p=C∗ΛH(Cy −zd) Λ−1 UB∗p+Nv = 0. La soluci´on del problema dual, pes el estado adjunto del sistema. El conjunto de estados adjuntos es el conjunto ∂φ(0). En esta secci´on estudiamos otra aplicaci´on de la teor´ıa de dualidad convexa a la resoluci´on de problema de control lineal cuadr´atico, en este caso con restricciones sobre el estado de control. Muchos desarrollos son similares a los de la aplicaci´on de la secci´on anterior, por lo que no se mostrar´an con tanto detalle. 5.2 Problema de control lineal cuadr´atico con restricciones sobre el estado De nuevo, sean Vy (H, ⟨·,·⟩) espacios de Hilbert tal que la inyecci´on de Ven Hes continua y densa. Por el Teorema de Riesz, identificando Hcon su dual topol´ogico H∗, se tiene H⊂V∗. Entonces, como vimos en la secci´on anterior la inyecci´on de Hen V∗es continua y densa. Denoramos por ⟨v, ℓ⟩la dualidad entre v∈Vyℓ∈V∗. Sea a(·,·) : V×V−→ Runa forma bilineal continua y coercitiva en V. Sea A:V−→ V∗el isomorfismo definido por A(u) = a(u, ·)∀u∈V Recordemos que si definimos a∗:V×V−→ Rpor a∗(u, v) = a(v, u) entonces A∗(v) = a∗(·, v)∀v∈V Sean Uel espacio de Hilbert de control y Hun espacio de Hilbert. Sean B∈ L(U, V ∗) y C∈ L(V, H). TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 5. Un problema de control lineal cuadr´atico 66 Sea un espacio de Banach Z⊂Hcuya inyecci´on es continua y densa, de igual forma la inyecci´on de Zen V∗es continua. Para todo g∈Zyv∈V, |⟨v, g⟩| ≤ ∥g∥H∥v∥H≤c∥g∥Z∥v∥V con ∥g∥V∗≤c∥g∥Z. Sea f∈V∗y un convexo cerrado K⊂Vtal que A(K)∩(f+B(Uad)) =∅. Buscamos hallar (y, v)∈K× Uad que minimice (y, v)7−→ 1 2∥C(y)−zd∥2 H+1 2⟨Nv, v⟩U con (y, v) tal que A(y) = B(v) + f. Este problema equivale a resolver (P) m´ın {v∈U,B(v)∈A(K)−f} 1 2∥CA−1(B(v) + f)−zd∥2 H+1 2⟨Nv, v⟩U o bien a resolver m´ın (y,v)∈V×U F((y, v),0) con F: (V× U)×Z−→ R∪ {+∞} dada por F((y, v), g) = 1 2∥Cy −zd∥2 H+1 2⟨Nv, v⟩U+iK(y) + iC((y, v), g) donde C={((y, v), g)∈(V× Uad)×Z:Ay =f+Bv +g}. El conjunto Ces un conjunto cerrado convexo de (V× Uad)×Z. Consideramos la siguiente hip´otesis: (SZ)Z⊂R+(−f−B(Uad) + A(K)) En las condiciones anteriores, razonando como en la Secci´on 5.1, se prueban las siguientes condiciones de optimalidad para (P): 1. Se tiene que (y, v)∈K× Uad es ´optimo para el problema (P) si y solo si existe q∈Z∗y p∈Vtal que          A(y) = f+Bv A∗p=C∗ΛH(Cy −zd) ⟨A(y−y), p⟩H− ⟨A(y−y)−B(v−v, q⟩Z,Z∗+⟨Nv, v −v⟩U≥0 TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 5. Un problema de control lineal cuadr´atico 67 para todo (y, v)∈ D con D={(y, v)∈K× Uad :A(y)−f−B(v)∈Z} ={(y, v)∈K× Uad :A(y−y)−B(v−v)∈Z}. En el caso de Z=HyB∈ L(U, H) la condici´on de optimalidad se escribe                  Ay =f+Bv A∗p=C∗ΛH(Cy −zd) ⟨A(y−y), p −q⟩ ≥ 0 para todo y∈(y+A−1(H)) ∩K ⟨Nv + Λ−1 UB∗q, v −v⟩U≥0 para todo v∈ Uad y adem´as se tiene q∈H. Justifiquemos estas afirmaciones. Est´a claro que nos encontramos en un caso de optimizaci´on convexa ya que la funci´on (y, v)7−→ F((y, v),0) es estrictamente convexa, propia, semicontinua inferiormente y coercitiva. Por lo tanto el problema (P) admite una ´unica soluci´on. Como consecuencia directa de la hip´otesis (SZ), para todo g∈Zse tiene la existencia de v∈ Uad ey∈Ktal que λ−1g=−f−B(v) + A(y) por lo tanto y como y∈Kentonces λ−1g∈dom p lo que prueba Z=R+(dom p). Aplicando el Teorema 4.14, deducimos que el dual admite soluci´on y que ´ınf (y,v)∈K×Uad F((y, v),0) = −m´ın q∈Z∗F∗((0,0), q). Procedemos al c´alculo del Lagrangiano asociado al problema P: L((y, v), q) = ´ınf g∈Z 1 2∥Cy −zd∥2 H+1 2⟨Nv, v⟩U+iK(y) + iC((y, v), g)− ⟨g, q⟩Z,Z∗ con iC((y, v), g) =    0 si v∈ Uad yg=A(y)−B(v)−f +∞en c.c . Se tiene L((y, v), q) = 1 2∥Cy −zd∥2 H+1 2⟨Nv, v⟩U+iK(y)− ⟨Ay −f−Bv, q⟩+iD(y, v) TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Cap´ıtulo 5. Un problema de control lineal cuadr´atico 68 con D={(y, v)∈V× Uad :A(y)−f−B(v)∈Z} Por la linealidad de AyB, se verifica que D={(y, v)∈V× Uad :A(y−y)−B(v−v)∈Z}. Procediendo de la misma forma que en la secci´on anterior, se tiene que ((y, v), q)∈ D ×Z∗ es ´optimo si y solo si ⟨C(y−zd, C(y−y)⟩H− ⟨A(y−y)−B(v−v), q⟩Z,Z∗+⟨Nv, v −v⟩U≥0 y ⟨A(y)−f−Bv, q −q⟩ ≥ 0 para todo q∈Z∗. Denotando por p∈Vla ´unica soluci´on de A∗p=C∗ΛH(Cy −zd), la condici´on de optimalidad anterior es equivalente a ⟨A(y−y), p⟩−⟨A(y−y)−B(v−v), q⟩Z,Z∗+⟨Nv, v −v⟩U≥0∀(y, v)∈ D con qsoluci´on del problema dual, A(y)−f−Bv = 0. En conclusi´on, las condiciones de optimalidad para nuestro problema son          A(y) = f+Bv A∗p=C∗ΛH(Cy −zd) ⟨A(y−y), p⟩−⟨A(y−y)−B(v−v), q⟩Z,Z∗+⟨Nv, v −v⟩U≥0 para todo (y, v)∈ D con D={(y, v)∈V× Uad :A(y−y)−B(v−v)∈Z}. Si suponemos Z=HyB∈ L(U, H), entonces                  A(y) = f+Bv A∗p=C∗ΛH(Cy −zd) ⟨A(y−y), p −q⟩ ≥ 0 para todo y∈(y+A−1(H)) ∩K ⟨Nv + Λ−1 UB∗q, v −v⟩U≥0 para todo v∈ Uad y se tiene q∈H. TFG Mar´ıa Jos´e G´omez Notario. Grado en Matem´aticas Bibliograf´ıa [1] D. Az´e, ´ El´ements d’analyse convexe et variationnelle. Ellipses, 1997. [2] S. P. Boyd & L. Vandenberghe, Convex optimization. Cambridge University Press, 2004. [3] H. Brezis, Analyse fonctionnelle. Th´eorie et applications. Masson, 1983. [4] I. Ekeland & R. Temam, Convex analysis and variational problems. Siam, 1999. [5] J.B. Hiriart-Urruty, Bases, outils et principes pour l’analyse variationnelle . Springer, 2010. [6] R. Lucchetti, Convexity and well-posed problems. Springer, 2006. [7] W. Schirotzek, Nonsmooth analysis. Springer, 2006. [8] H. Tuy, Convex analysis and global optimization. Springer, 1997. 76