Sobre problemas variacionales y optimización

Universidad de Sevilla Facultad de Matem´aticas Trabajo Fin de Estudios Grado en Matem´aticas Sobre problemas variacionales y optimizaci´on (On variational problems and optimization) Laura Mar´ıa Rodr´ıguez Llave Tutor Faustino Maestre Caballero Dpto. Ecuaciones Diferenciales y An´alisis Num´erico. Abstract The Calculus of Variations is a mathematical field that tries to find the functions that minimize or maximize the value of certain functional defined on a determined space. It is a classic topic in mathematics, interconnected with many other problems in this branch. It has multiple applications, among them is the use in optimal control. In this work we will analyze optimization problems within the framework of the Calculus of Variations, as well as the resolution of some partial differential equations. We will study the theory of existence and uniqueness of solution of certain optimization problems and we will see necessary and/or sufficient conditions of optimality, which will be important both from the theoretical and numerical point of view and they will allow us to characterize the optimum. In addition, we will describe numerical methods to solve minimization problems without constraints. Resumen El C´alculo de Variaciones es un campo de las matem´aticas que trata de encontrar las funciones que minimizan o maximizan el valor de un cierto funcional definido sobre un determinado espacio. Es un tema cl´asico en matem´aticas, interconectado con muchos otros problemas de esta rama. Tiene m´ultiples aplicaciones, entre ellas est´a el uso en control ´optimo. En este trabajo analizaremos problemas de optimizaci´on dentro del marco del C´alculo de Variaciones, as´ı como la resoluci´on de algunas ecuaciones en derivadas parciales no lineales. Estudiaremos la teor´ıa de existencia y unicidad de soluci´on de ciertos problemas de optimizaci´on y veremos condiciones necesarias y/o suficientes de optimalidad, que ser´an importantes tanto desde el punto de vista te´orico como num´erico y nos permitir´an caracterizar los ´optimos. Adem´as, describiremos m´etodos num´ericos para la resoluci´on de problemas de minimizaci´on sin restricciones. ´ Indice Introducci´on 3 1. Resultados previos de An´alisis Funcional 5 1.1. Teoremas de Representaci´on Riesz, de Lax-Milgram y de la Proyecci´on ...... 5 1.2. Resultados auxiliares sobre espacios de funciones .................. 8 1.3. Distribuciones ..................................... 10 1.4. Los espacios de Sobolev : H1(Ω), H1 0(Ω) y H−1(Ω) ................ 14 1.5. Trazas y f´ormulas de Green .............................. 17 1.6. Resultado de compacidad ............................... 18 1.7. Otros espacios : Hm(Ω), H(div) y Wm,p(Ω) ..................... 19 1.8. Convergencia d´ebil ................................... 21 2. Optimizaci´on 23 2.1. Introducci´on ....................................... 23 2.2. Ejemplos ........................................ 24 2.2.1. En dimensi´on finita .............................. 24 2.2.2. En dimensi´on infinita ............................. 26 2.3. Convexidad ....................................... 27 3. Optimizaci´on diferenciable 34 3.1. La diferencial de Fr´echet y de Gˆateaux ........................ 34 3.2. Condiciones de optimalidad (caso convexo) ..................... 39 4. M´etodos num´ericos en optimizaci´on sin restricciones 42 4.1. Algoritmo de gradiente con paso ´optimo ....................... 42 4.2. Algoritmo de gradiente con paso fijo ......................... 45 4.3. M´etodo del gradiente conjugado para funcionales cuadr´aticos ........... 46 5. Aplicaci´on: resoluci´on edp no lineal 51 5.1. Marco te´orico para la soluci´on del problema ..................... 51 5.2. Resoluci´on del problema con FreeFEM ........................ 57 5.2.1. En Ω = B(0,1) ................................. 57 5.2.2. En Ω una elipse con un agujero ........................ 62 Anexo 66 Bibliograf´ıa 74 1 ´ Indice de figuras 2.1. Fases del proceso de optimizaci´on .......................... 24 2.2. Conjunto no convexo ................................. 30 2.3. Conjunto convexo ................................... 30 5.1. Frontera del dominio .................................. 59 5.2. Malla del dominio ................................... 59 5.3. Funci´on f ........................................ 59 5.4. Funci´on u0: inicializaci´on AGPO ........................... 60 5.5. Primera iteracion del AGPO ............................. 60 5.6. Segunda iteracion del AGPO ............................. 60 5.7. Tercera iteracion del AGPO .............................. 61 5.8. 4 ª iteraci´on del Algoritmo de gradiente con paso fijo ................ 61 5.9. 17 ª iteraci´on del Algoritmo de gradiente con paso fijo ............... 62 5.10. 38 ª iteraci´on del Algoritmo de gradiente con paso fijo ............... 62 5.11. Frontera elipse ..................................... 63 5.12. Malla de la elipse .................................... 63 5.13. Funci´on f1........................................ 64 5.14. Funci´on u0: inicializaci´on AGPO (para la elipse y f1)................ 64 5.15. Primera iteracion del AGPO (para la elipse y f1).................. 64 5.16. Segunda iteracion del AGPO (para la elipse y f1).................. 65 5.17. Tercera iteracion del AGPO (para la elipse y f1).................. 65 2 Introducci´on La optimizaci´on dentro del C´alculo de Variaciones se enfoca en encontrar la funci´on que optimiza un cierto funcional, sujeta a ciertas restricciones o condiciones. Este ´area de investigaci´on tiene aplicaciones en diversos campos, como la f´ısica, la econom´ıa, la ingenier´ıa y la biolog´ıa, entre otros. Al encontrar la funci´on que minimiza o maximiza un funcional, se pueden obtener soluciones ´optimas para problemas de dise˜no, control, estimaci´on o predicci´on. La resoluci´on de ecuaciones en derividas parciales y la optimizaci´on en el C´alculo de Variaciones a menudo se entrelazan, ya que muchos problemas pr´acticos requieren encontrar funciones que optimicen ciertos criterios mientras satisfacen ciertas ecuaciones diferenciales. Estos problemas son abordados utilizando m´etodos num´ericos y t´ecnicas de optimizaci´on, como el m´etodo de los elementos finitos, el m´etodo de los m´ınimos cuadrados, los algoritmos de gradiente descendente y los m´etodos de optimizaci´on convexa. La presente Memoria est´a organizada como sigue: El Cap´ıtulo 1, recoge los conceptos b´asicos y algunos resultados fundamentales de An´alisis Funcional que ser´an necesarios para desarrollar esta memoria. Entre ellos, los teoremas cl´asicos de Representaci´on de Riesz y de Lax-Milgram. Introduciremos la teor´ıa de distribuciones, discutiremos ciertos aspectos esenciales sobre la teor´ıa de Espacios de Sobolev y trataremos la compacidad y la convergencia d´ebil. Todo ello nos permitir´a abordar diversos problemas variacionales. En el Cap´ıtulo 2, se presentar´an algunos ejemplos de optimizaci´on que provienen de diversos ´ambitos. Adem´as, estudiaremos el concepto de funcional el´ıptico (α-convexo) que ser´a necesario en el siguiente cap´ıtulo. Trataremos principalmente la cuesti´on de existencia y unicidad en optimizaci´on continua, donde ser´a fundamental el papel de la convexidad y distinguiremos entre problemas de optimizaci´on en dimensi´on finita e infinita, ya que requieren ser tratados de distinta forma. El Cap´ıtulo 3, est´a dedicado a la teor´ıa de la diferenciabilidad en dimensiones infinitas, centr´andonos en las diferenciales de Fr´echet y Gˆateaux, tanto de primer como de segundo orden. 3 Introducci´on 4 Discutiremos sus definiciones, propiedades y relaciones, as´ı como su aplicaci´on en la resoluci´on de problemas pr´acticos. Finalmente, estudiaremos condiciones de optimalidad en el caso en el que el conjunto de restricciones sea convexo, las cuales juegan un papel fundamental al determinar las soluciones ´optimas. En el Cap´ıtulo 4, se estudian varios de los m´etodos m´as importantes para la resoluci´on de problemas de optimizaci´on sin restricciones. Estos m´etodos combinan principios matem´aticos, algoritmos iterativos y capacidades computacionales para aproximarse a la soluci´on ´optima de manera eficiente y precisa. En particular, dos m´etodos num´ericos destacados en la optimizaci´on sin restricciones son el m´etodo de gradiente y el m´etodo de direcciones conjugadas. En el Cap´ıtulo 5, trabajaremos con un funcional el´ıptico concreto, consideraremos el problema de m´ınimos correspondiente y lo resolveremos mediante uno de los m´etodos num´ericos estudiados en el cap´ıtulo anterior, comprobando previamente que se cumplen las hip´otesis necesarias. Para ello, haremos un programa en FreeFEM. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 1 Resultados previos de An´alisis Funcional 1.1. Teoremas de Representaci´on Riesz, de Lax-Milgram y de la Proyecci´on Recordemos primero la definici´on de espacio de Banach y espacio de Hilbert. Definici´on 1.1 Diremos que V es un espacio de Banach si es un espacio vectorial normado y completo. Definici´on 1.2 Diremos que H es un espacio de Hilbert si es un espacio vectorial con un producto escalar cuya norma asociada es completa. Notaci´on: X, Y, . . . denotan espacios normados sobre R(espacio vectorial sobre Rcon una norma asociada). Denotaremos ∥·∥X,∥·∥Y, . . . las respectivas normas (o simplemente ∥·∥). H, V, . . . denotan espacios pre-hilbertianos sobre R(espacio vectorial sobre Rcon un producto escalar). Denotaremos ⟨·,·⟩H,⟨·,·⟩V, . . . los respectivos productos escalares (o simplemente ⟨·,·⟩). Teorema de Riesz Sean X, Y dos espacios normados sobre R. Consideraremos aplicaciones T:X−→ Ylineales y continuas, lo que llamaremos como operador lineal y continuo. Definici´on 1.3 Diremos que la aplicaci´on Tes lineal si T(αx +βy) = αT(x) + βT(y),∀α, β ∈R,∀x, y ∈X. 5 Cap´ıtulo 1. Resultados previos de An´alisis Funcional 12 Observaci´on 1.36 De las definiciones anteriores se tiene que si {φn}n≥1⊂ D(Ω) y φ∈ D(Ω) son tales que φn−→ φ en D(Ω), entonces φn−→ φen Ck 0(Ω),∀k≥0. Esta propiedad la escribiremos como D(Ω) ,→Ck 0(Ω). Diremos que D(Ω) se inyecta en Ck 0(Ω) con inyecci´on (secuencialmente) continua. Del mismo modo: D(Ω) ,→Ck 0(Ω) ,→Ck(Ω) ,→C0(Ω) ,→L1 Loc(Ω), D(Ω) ,→Lp(Ω) ,→L1 Loc(Ω),∀p∈[1,∞]. Definici´on 1.37 Una distribuci´on sobre Ωes cualquier aplicaci´on T:D(Ω) −→ Rlineal y secuencialmente continua, es decir, tal que si {φn}n≥1⊂ D(Ω) yφ∈ D(Ω) satisfacen φn−→ φ en D(Ω), entonces T(φn)−→ T(φ)en R. Notaci´on: D′(Ω) = {T:Tes distribuci´on sobre Ω}(1.19) Si T∈ D′(Ω) y φ∈ D(Ω) escribiremos ⟨T, φ⟩=T(φ)∈R Ejemplo 1.38 (La distribuci´on de Dirac) Fijemos x∈Ω con Ω ⊂RNun abierto. Definimos δxmediante δx:φ∈ D(Ω) 7−→ ⟨δx, φ⟩=φ(x)∈R. Se tiene δx∈ D′(Ω) pues es lineal y secuencialmente continua. Adem´as δxno es la distribuci´on nula, pues existe φ∈ D(Ω) tal que ⟨δx, φ⟩=φ(x) = 1. Definici´on 1.39 Dada una sucesi´on {Tn}n≥1⊂ D′(Ω), diremos que Tnconverge a un elemento T∈ D′(Ω) si para cada φ∈ D(Ω) se satisface ⟨Tn, φ⟩ −→ ⟨T, φ⟩en R, y escribiremos Tn−→ T en D′(Ω). Proposici´on 1.40 Dada f∈L1 Loc(Ω), definimos Tf:φ∈ D(Ω) 7−→ ⟨Tf, φ⟩=ZΩ fφ dx ∈R. Entonces, Tfest´a bien definida y Tf∈ D′(Ω). Adem´as, el operador T:f∈L1 Loc(Ω) 7−→ T (f) = Tf∈ D′(Ω) est´a bien definido, es lineal, inyectivo y secuencialmente continuo. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 1. Resultados previos de An´alisis Funcional 13 Observaci´on 1.41 Mediante el operador Testamos identificando de forma biun´ıvoca L1 Loc(Ω) con un subconjunto de D′(Ω). Como Tes secuencialmente continuo, hay una inclusi´on de las topolog´ıas. Escribiremos L1 Loc(Ω) ,→ D′(Ω) Definici´on 1.42 Sean T∈ D′(Ω) yα∈NNun multi´ındice. Se denomina derivada en el sentido de las distribuciones (o derivada distribucional) de orden α, ∂αT , como el elemento de D′(Ω) dado por ⟨∂αT, φ⟩= (−1)|α|⟨T, ∂αφ⟩,∀φ∈ D(Ω).(1.20) ∂αTest´a bien definida y ∂αT∈ D′(Ω) para todo α∈NN. Adem´as, la aplicaci´on ∂α:T∈ D′(Ω) 7−→ ∂αT∈ D′(Ω) es lineal y secuencialmente continua. El concepto de derivada distribucional es coherente con el concepto de derivada cl´asica: Proposici´on 1.43 Sea u∈C0(Ω) tal que ∃∂iu(x),∀x∈Ω,con ∂iu∈C0(Ω). Entonces ∂i(Tu) = T∂iu. Veamos un ejemplo sobre la derivada distribucional. Ejemplo 1.44 Calculamos la primera y segunda derivada en D′(Ω) de f(x) = |x|=(xsi x≥0 −xsi x < 0 En este caso tenemos Ω = R.Hay que comprobar que f∈L1 Loc(Ω), es decir, que la integral sobre cada compacto es finita. Sea K⊂Rcompacto. =⇒m´axK|x|=M∈(0,∞). ZK f(x)dx ≤M|K|<∞ f∈L1 Loc(Ω) =⇒f∈ D′(R). Escriberemos f(= Tf). f′∈ D′(R) =⇒ ⟨f′, φ⟩=−⟨f, φ′⟩=−ZR|x|φ′(x)dx ∀φ∈ D(R). Sea φ∈ D(R), entonces sop φ⊂(−M, M). ⟨f′, φ⟩=−ZM −M|x|φ′(x)dx =−Z0 −M−xφ′(x)dx +ZM 0 xφ′(x)dx =−Z0 −M φ(x)dx −xφ(x)|0 −M−ZM 0 φ(x)dx +xφ(x)|M 0 ∗ =−Z0 −M φ(x)dx −ZM 0 φ(x)dx=Z0 −M−φ(x)dx ZM 0 φ(x)dx =⟨g, φ⟩ =ZR g(x)φ(x)dx TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 1. Resultados previos de An´alisis Funcional 14 con g(x) = (1 si x≥0 −1 si x < 0 (∗) : φ(−M) = φ(M) = 0 pues sop φ⊂(−M, M). v=|x|es una funci´on continua, no derivable (es derivable a trozos) y posee derivada distribucional. Veamos ahora la segunda derivada. ⟨f′′, φ⟩=−⟨f′, φ′⟩=Z0 −M φ′(x)dx −ZM 0 φ′(x)dx =φ(0) −φ(−M)−φ(M) + φ(0) = 2φ(0) = ⟨2δ0, φ⟩. Por tanto, f′′ = 2δ0. 1.4. Los espacios de Sobolev : H1(Ω),H1 0(Ω) yH−1(Ω) El espacio H1(Ω) Todos los resultados de este apartado se detallan en [7]. Definici´on 1.45 Sea Ω⊂RNun abierto no vac´ıo. Definimos el espacio de Sobolev H1(Ω) como: H1(Ω) = {u∈L2(Ω) : ∂u ∂xi =∂iu∈L2(Ω),∀i: 1 ≤i≤N}.(1.21) Observaci´on 1.46 Las derivadas consideradas son las derivadas distribucionales : ∂u ∂xi∈L2(Ω) equivale a ∃vi∈L2(Ω) tal que −ZΩ u(x)∂φ ∂xi (x)dx =ZΩ vi(x)φ(x)dx ∀φ∈ D(Ω).(1.22) Diremos en este caso que ues derivable d´ebil (la derivada parcial de uen el sentido de las distribuciones es una funci´on). Cada vise llama i-´esima derivada parcial d´ebil de uy de ahora en adelante lo escribiremos como ∂u ∂xi . Proposici´on 1.47 El espacio de Sobolev H1(Ω) dotado del producto escalar ⟨u, v⟩H1(Ω) =ZΩ (u(x)v(x) + ∇u(x)·∇v(x)) dx (1.23) y la norma ∥u∥H1(Ω) =∥u∥1,2;Ω =RΩ|u(x)|2+|∇u(x)|21/2es un espacio de Hilbert. Adem´as sabemos que en H1(Ω) se cumple la f´ormula de integraci´on por partes. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 1. Resultados previos de An´alisis Funcional 15 Proposici´on 1.48 Sean a, b ∈R, a < b, entonces Zb a u(x)v′(x)dx =u(b)v(b)−u(a)v(a)−Zb a u(x)′v(x)dx ∀u, v ∈H1((a, b)) (1.24) En la pr´actica es importante saber si las funciones regulares son densas en H1(Ω) . Para ello vemos el siguiente resultado de densidad. Teorema 1.49 Si Ωes un conjunto abierto acotado regular de clase C1, o bien Ω = RN +, o incluso si Ω = RN, entonces D(Ω) es denso en H1(Ω). El espacio H1 0(Ω) Definamos ahora otro espacio de Sobolev que denotamos por H1 0(Ω) y es un subespacio de H1(Ω). Los siguientes resultados se detallan en [6]. Definici´on 1.50 H1 0(Ω) es la adherencia de D(Ω) en H1(Ω) , es decir, H1 0(Ω) = D(Ω)∥·∥H1(Ω) . Proposici´on 1.51 El espacio de Sobolev H1 0(Ω) dotado del producto escalar (1.23) (producto escalar de H1(Ω)) es un espacio de Hilbert. Teorema 1.52 (Desigualdad de Poincar´e) Sea Ω⊂RNabierto conexo acotado en alguna direcci´on. Entonces existe una constante C=C(Ω) >0tal que ZΩ|v(x)|2dx ≤CZΩ|∇v(x)|2dx ∀v∈H1 0(Ω) (1.25) Demostraci´on: Lo hacemos utilizando un razonamiento de densidad. D(Ω) es denso en H1 0(Ω). Consideramos Ω acotado en la direcci´on x1,Ω⊂(−M, M)×RN−1. Sea φ∈ D(Ω) =⇒sop (φ)⊂(−M, M)×RN−1=⇒φ(−M, x2,··· , xN)=(M, x2,··· , xN) = 0. x∈Ω, φ(x) = Zx1 −M ∂ ∂x1 φ(y1, x2,··· , xN)dy1 |φ(x)| ≤ Zx1 −M ∂ ∂x1 φ(y1, x2,··· , xN) dy1≤ZM −M 1· ∂ ∂x1 φ(y1, x2,··· , xN) dy1 H¨older ≤ ≤ZM −M 12dy1/2 · ZM −M ∂ ∂x1 φ(y1, x2,··· , xN) 2 dy1!1/2 =⇒ |φ(x)|2≤2MZM −M ∂ ∂x1 φ(y1, x2,··· , xN) 2 dy1 ZRN−1|φ(x)|2dx2··· dxN≤2MZM −MZRN−1 ∂φ ∂x1 (x) dx TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 1. Resultados previos de An´alisis Funcional 16 Z−MZRN−1|φ(x)|2dx ≤(2M)2ZM −MZRN−1 ∂φ ∂x1 (x) dx ≤(2M)2ZM −MZRN−1|∇φ(x)|2dx ⇐⇒ ⇐⇒ ZΩ|φ(x)|2dx ≤(2M)2ZΩ|∇φ(x)|2dx. Sea u∈H1 0(Ω) =⇒ ∃{φn}m≥1⊂ D(Ω) tal que φn−→ uen H1(Ω),es decir, φn−→ uen L2(Ω) y∂iφn−→ ∂iuen L2(Ω). Por tanto tenemos ZΩ|φn(x)|2dx ≤C(Ω) ZΩ|∇φn(x)|2dx. Tomando l´ımite en n: ZΩ|φn(x)|2dx =∥φn∥2 2;Ω −→ ∥u∥2 2;Ω ZΩ|φn ∂xi (x)|2dx =∥∂iφn∥2 2;Ω −→ ∥∂iu∥2 2;Ω        =⇒ZΩ|u(x)|2dx ≤C(Ω) ZΩ|∇u(x)|2dx □ Nota 1.53 La demostraci´on del Teorema 1.52 nos da un procedimiento constructivo, para calcular la constante C=C(Ω) en cada problema. Observaci´on 1.54 La Desigualdad de Poincar´e no es cierta en el espacio H1(Ω). Por ejemplo, tomamos Ω acotado yv≡1. Observamos que ∇v≡0 y por tanto ZΩ 12dx =|Ω|≰C·0 = 0 (|Ω| = 0) Gracias a la Desigualdad de Poincar´e podemos definir una norma equivalente en H1 0(Ω) Corolario 1.55 Sea Ω ⊂RNabierto conexo acotado en alguna direcci´on. Entonces la seminorma |v|H1 0(Ω) =|v|1,2;Ω =ZΩ|∇v(x)|2dx1/2 es una norma en H1 0(Ω), que es equivalente a la inducida por H1(Ω). Por lo tanto concluimos que (H1 0(Ω),|·|1,2;Ω) es un espacio de Hilbert. El espacio H−1(Ω) De forma gen´erica, sea H un espacio de Hilbert. Denotamos por H′a su dual, es decir, H′=L(H, R). V´ease [7]. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 1. Resultados previos de An´alisis Funcional 17 Definici´on 1.56 Denominaremos H−1(Ω) al dual topol´ogico de H1 0(Ω), es decir, H−1(Ω) = H′(H1 0(Ω)) = L(H1 0(Ω),R). Observaci´on 1.57 1. H−1(Ω) es el dual de un espacio de Hilbert. Por tanto, por el Teorema de Riesz, podr´ıamos identificarlo (mediante el porducto escalar de H1 0(Ω)) con H1 0(Ω), aunque no lo haremos. H1 0(Ω) es un subespacio de H1(Ω) y en particular un subespacio estricto de L2(Ω). Entonces, identificando L2(Ω) con su dual , que es ´el mismo, tenemos : H1 0(Ω) ⊂L2(Ω) ≡L2(Ω) ⊂H−1(Ω) 2. Si L∈H−1(Ω), ∥L∥H−1(Ω) = sup v∈H1 0(Ω),v=0 ⟨L, v⟩ ∥v∥1,2;Ω Veamos ahora una caracterizaci´on para H−1(Ω). Proposici´on 1.58 El espacio H−1(Ω) est´a caracterizado por H−1(Ω) = (f=v0+ N X i=1 ∂vi ∂xi con v0, v1, . . . , vN∈L2(Ω))(1.26) En otras palabras, toda forma lineal y continua L:H1 0(Ω) −→ R, L ∈H−1(Ω) , se escribe ∀Φ∈H1 0(Ω) L(Φ) = ZΩ v0Φ− N X i=1 vi ∂Φ ∂xi!dx con v0, v1, . . . , vN∈L2(Ω) 1.5. Trazas y f´ormulas de Green Si Ω = RN +={(x′, xN)∈RN:xN>0} ≡ RN−1×(0,+∞) con N≥2, entonces ∂RN +=RN−1×{0}yL2(∂Ω) = L2(RN−1). En el caso en que Ω es un abierto acotado regular de clase C1, tambi´en es posible definir L2(∂Ω). A la hora de definir los espacios Lp(Ω), en la Secci´on 1.2, vimos que no podemos hablar del valor de una funci´on de Lp(Ω) en un punto de Ω. Por tanto tenemos que ver si ocurre lo mismo sobre ∂Ω, ya que es un conjunto de medida nula. Para ellos utilizaremos el siguiente teorema. Teorema 1.59 (De Trazas) Sea Ω⊆RNun abierto acotado regular de clase C1, o bien RN +. Definimos el operador traza, γ0 H1(Ω) ∩C(Ω) −→ L2(∂Ω) ∩C(∂Ω) (1.27) TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 1. Resultados previos de An´alisis Funcional 18 v7−→ v|∂Ω=γ0(v) Este operador se puede extender por continuidad a H1(Ω) −→ L2(∂Ω) y se denominar´a ˜γ0, que por abuso de notaci´on lo llamaremos γ0. En particular ∥γ0(v)∥L2(∂Ω) ≤C∥v∥H1(Ω). Teorema 1.60 (F´ormula de Green) Sea Ω⊂RNun abierto acotado regular de clase C1. Sean u, v ∈H1(Ω), entonces satisfacen: ZΩ u(x)∂v ∂xi (x)dx =−ZΩ v(x)∂u ∂xi (x)dx +Z∂Ω u(x)v(x)ni(x)dS (1.28) donde n= (ni)1≤i≤N, con nilas componentes del vector normal exterior. Notaci´on: Por abuso del lenguaje, la mayor´ıa de las veces, denotaremos γ0(v) por v. Gracias al Teorema de Trazas 1.59 tenemos una caracterizaci´on para H1 0(Ω). Teorema 1.61 Sea Ω⊂RNun abierto acotado regular de clase C1. Entonces, H1 0(Ω) = ker(γ0) = {u∈H1(Ω) : γ0(u)=0}(1.29) Proposici´on 1.62 Se tiene que R(γ0) = Im(γ0) (rango o impagen de γ0) es un subespacio vectorial propio de L2(∂Ω), que llamaremos espacio de trazas sobre la frontera. R(γ0) = H1/2(∂Ω).(1.30) Podemos consultar los resultados de esta Secci´on en [1]. 1.6. Resultado de compacidad En un espacio de Hilbert de dimensi´on infinita, no es cierto que, de cada sucesi´on acotada se puede extraer una subsucesi´on convergente. Definici´on 1.63 Sea T∈ L(X, Y ). Se dice que Tes compacto si la imagen de T(B)de cualquier conjunto acotado B∈Xes relativamente compacta en Y. Si Xes un espacio de Banach, K⊂Xcompacto ⇐⇒ ∀{xn}n≥1⊂K, existe una subsuce- si´on {xnk}k≥1yx∈Ktal que {xnk} −→ xen X. Si Xes un espacio de Banach, K⊂Xes relativamente compacto ⇐⇒ ∀{xn}n≥1⊂K, existe una subsucesi´on {xnk}k≥1yx∈Xtal que {xnk} −→ xen X. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 1. Resultados previos de An´alisis Funcional 19 Denotamos por K(X, Y ) el conjunto de operadores lineales, continuos y compactos de Xen Y, es decir, K(X, Y ) = {T∈ L(X, Y ) : Tes compacto }⊂L(X, Y ). Es un subespacio vectorial de L(X, Y ). Si Y=X, entonces K(X) = K(X, X). Teorema 1.64 (Rellich-Kondrachov) Si Ωes un abierto acotado regular de clase C1, entonces de toda sucesi´on acotada de H1(Ω) se puede extraer una subsucesi´on convergente en L2(Ω). Decimos que la aplicaci´on inyecci´on i:v∈H1(Ω) 7−→ v∈L2(Ω) es compacta (H1(Ω) ⇒L2(Ω)). Lema 1.65 La inyecci´on i0:H1 0(Ω) −→ L2(Ω) es compacta. Para la elaboraci´on de esta Secci´on, se ha seguido principalmente la referencia [1]. 1.7. Otros espacios : Hm(Ω),H(div)yWm,p(Ω) Los espacios Hm(Ω) Para este apartado, v´ease [7]. Definici´on 1.66 De acuerdo con la notaci´on multi´ındice de Schwartz (Secci´on 1.3), sea m∈Z, m≥0. Definimos el espacio de Sobolev Hm(Ω) = {v∈L2(Ω) : ∀α, |α| ≤ m, ∂αv∈L2(Ω)}(1.31) donde la derivada parcial ∂αves en el sentido d´ebil. Proposici´on 1.67 Hm(Ω) dotado del producto escalar ⟨u, v⟩Hm(Ω) =ZΩX |α|≤m ∂αu(x)∂αv(x)dx (1.32) y la norma ∥u∥Hm(Ω) =q⟨u, u⟩Hm(Ω) es un espacio de Hilbert. Teorema 1.68 Sea Ωun abierto acotado regular de clase C1. Si m > N 2entonces Hm(Ω) es un subespacio de C(Ω). Teorema 1.69 Si Ωun abierto acotado regular de clase Cm, o bien Ω = RN +entonces D(Ω) es denso en Hm(Ω). Podemos generalizar el Teorema de Trazas 1.59 en el espacio Hm(Ω). Lo vemos para m= 2. Teorema 1.70 Sea Ωun abierto regular de clase C1. Definimos el operador de trazas γ1 H2(Ω) ∩C1(Ω) −→ L2(∂Ω) ∩C(∂Ω) (1.33) TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 1. Resultados previos de An´alisis Funcional 20 v7−→ γ1(v) = v|∂v ∂n =∇v·n donde n es el vector normal exterior a ∂Ω. Esta aplicaci´on se puede extender de manera continua aH2(Ω) −→ L2(∂Ω) y se denominar´a ˜γ1, que por abuso de notacion llamaremos γ1. En particular, ∀v∈H2(Ω) tenemos ∥γ1(v)∥=∥∂v ∂n ∥H2(Ω) ≤C∥v∥H2(Ω). Este teorema nos permite generalizarla F´ormula de Green 1.60 en H2(Ω). Teorema 1.71 Sea Ωun abierto, regular de clase C2. Si u∈H2(Ω) yv∈H1(Ω), entonces ZΩ ∆u(x)v(x)dx =−ZΩ∇u(x)·∇v(x) + ZΩ ∂u ∂n(x)v(x)dS (1.34) El espacio H(div) Los siguientes conceptos los podemos encontrar en [1]. Definici´on 1.72 Definimos el espacio H(div)como H(div) = {w∈L2(Ω)N:∇·w∈L2(Ω)}.(1.35) Proposici´on 1.73 H(div) dotado del producto escalar ⟨u, v⟩H(div)=ZΩ u(x)v(x)dx +ZΩ (∇·u(x))(∇·v(x)) dx (1.36) y la norma ∥u∥H(div)=q⟨u, u⟩H(div), es un espacio de Hilbert. Teorema 1.74 Sea Ωun abierto acotado regular de clase C1, o bien Ω = RN +. Entonces se tiene: 1. DΩ(RN)es denso es H(div). 2. ∃γn∈ L(H(div), H−1/2(∂Ω)) tal que γn(v) = v·n|∂Ωsi v∈H(div)∩C0(Ω)N. 3. ZΩ w(x)∇·v(x)dx =−ZΩ∇w(x)·v(x)dx +⟨γn(v), γ0(w)⟩H−1/2,H1/2∀w∈H1(Ω),∀v∈H(div). Los espacios Wm,p(Ω) M´as generalmente, podemos definir los espacios Wm,p(Ω) para un entero m≥0 y un real 1≤p≤+∞. Para m´as detalles, v´ease [6]. Definici´on 1.75 Para cada entero m≥0, definimos el espacio de Sobolev Wm,p(Ω) dado por Wm,p(Ω) = {v∈Lp(Ω) tal que ∀αcon |α| ≤ m, ∂αv∈Lp(Ω)},(1.37) donde ∂αves la derivada parcial en el sentido d´ebil. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 1. Resultados previos de An´alisis Funcional 21 Proposici´on 1.76 Considerando la norma ∥u∥Wm,p(Ω) = X |α|≤m∥∂αu∥p  1/p tenemos que Wm,p(Ω) son espacios de Banach. Observaci´on 1.77 Si consideramos p= 2, Wm,2(Ω) = Hm(Ω). Estos espacios son importantes para problemas no lineales y tambi´en para los lineales debido a las desigualdades de Sobolev. Proposici´on 1.78 Sea Ω un abierto regular, o bien Ω = RN, o bien Ω = RN +, entonces        Si p < N W1,p(Ω) ,→Lq(Ω) ∀q∈[1, p∗] con 1/p∗= 1/p −1/N Si p=N W1,p(Ω) ,→Lq(Ω) ∀q∈[1,+∞) Si p > N W1,p(Ω) ,→C(Ω) (1.38) 1.8. Convergencia d´ebil A lo largo de esta secci´on Xrepresenta un espacio normado con norma que ser´a denotada por ∥·∥.Recordemos que, dados una sucesi´on {xn}n≥1⊂Xy un elemento x∈X, se tiene que xnconverge hacia xen X(que denotaremos xn−→ xen X) si la sucesi´on real ∥xn−x∥converge hacia cero. En algunas ocasiones diremos que xnconverge en norma o fuertemente hacia x. Veamos otro concepto de convergencia, [8]. Definici´on 1.79 Sean {xn}n≥1⊂Xuna sucesi´on y x∈Xun elemento de X. Diremos que xn converge d´ebilmente hacia xsi para cualquier x′∈X′se tiene ⟨x′, xn⟩X′,X −→ ⟨x′, x⟩X′,X (1.39) En esta definici´on ⟨·,·⟩X′,X representa el producto de dualidad entre el espacio normado Xy su dual X′. Como su nombre indica, la convergencia d´ebil es una idea “m´as d´ebil” que la convergencia fuerte. Proposici´on 1.80 Cualquier sucesi´on {xn}n≥1⊂Xfuertemente convergente es d´ebilmente convergente. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 2. Optimizaci´on 28 Por tanto, el problema estudiado se denotar´a como ´ınf v∈K⊂VJ(v) (2.3) Cuando usamos la notaci´on ´ınf para un problema de optimizaci´on, esto indica que no se sabe a priori, si se alcanza el valor m´ınimo, es decir, si ∃v∈Ktal que J(v) = ´ınf v∈K⊂VJ(v). Si queremos indicar que se alcanza el valor m´ınimo, preferimos la notaci´on m´ın v∈K⊂VJ(v) (2.4) Lo mismo ocurre en los problemas de maximizaci´on reemplazando ´ınf y m´ın por sup y m´ax respectivamente. Podemos consultar los resultados de esta Secci´on en [7]y[11]. Definici´on 2.6 Diremos que ues un m´ınimo local (o punto m´ınimo) de Jsobre Ksi y solo si u∈Ky∃δ > 0tal que ∀v∈Kcon ∥v−u∥< δ se tiene J(u)≤J(v).(2.5) Adem´as, user´a un m´ınimo global de Jsobre Ksi y solo si u∈KyJ(u)≤J(v)∀v∈K. (2.6) Definici´on 2.7 Diremos ´ınfimo de Jsobre K(o m´as com´unmente, valor m´ınimo), que denotaremos por (2.3), para referirnos al l´ımite superior en Rde las constantes que limitan por debajo aJen K. Si Jno est´a acotado por debajo en K, entonces el ´ınfimo es −∞. Si Kes vac´ıo, por convenio, el ´ınfimo es +∞. Llamaremos sucesi´on minimizante Jsobre Ka la sucesi´on (un)n≥1tal que un∈K∀nyl´ım n→+∞J(un) = ´ınf v∈KJ(v) (2.7) Hay que diferenciar si nos encontramos en un espacio de dimensi´on finita o infinita, pues tienen distinto comportamiento. Resultados v´alidos para dimensi´on finita no son suficiente para dimensi´on infinita. Estudiamos a continuaci´on ambos casos. Optimizaci´on en dimensi´on finita: En este caso podemos suponer, sin p´erdida de generalidad, que V=RNcon el producto escalar habitual u·v= N X i=1 uiviy la norma eucl´ıdea ∥u∥=√u·u. El siguiente resultado nos garantiza la existencia de un m´ınimo. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 2. Optimizaci´on 29 Teorema 2.8 Sea Kun conjunto cerrado no vac´ıo de RN, y Juna funci´on continua sobre K que toma valores en Ry satisface la propiedad “infinito en infinito”, es decir, ∀(un)n≥1sucesi´on en K tal que l´ım n→∞ ∥un∥= +∞=⇒l´ım n→∞ J(un)=+∞(2.8) Entonces existe al menos un punto m´ınimo de Jsobre K. Adem´as en cada sucesi´on minimizante de Jsobre Kpodemos extraer una subsucesi´on que converge a un punto m´ınimo sobre K. Demostraci´on: Sea (un)n≥1una sucesi´on minimizante de Jsobre K. La condici´on (2.8) implica que (un)n≥1est´a acotada ya que J(un) es una sucesi´on de reales acotados. Por lo tanto, existe una subsucesi´on (unk)k≥1que converge a u∈RN. Como Kes cerrado, u∈K, y por continuidad J(unk) converge a J(u). Finalmente, por la Definici´on 2.7 J(u) = ´ınf v∈KJ(v). □ Optimizaci´on en dimensi´on infinita: Como dijimos antes, el estudio en este caso es distinto. En dimensi´on infinita un conjunto acotado y cerrado no es compacto. Si seguimos trabajando en un espacio vectorial Vcon norma ∥·∥ (como en el caso finito) no podremos continuar al tener que usar la compacidad como en el Teorema 2.8. Podr´ıamos seguir si se satisface la condici´on : ∀(un)n≥1en Ktal que sup n∈N∥un∥<∞tenemos l´ım n→∞ J(un) = l < ∞=⇒ ∃u∈Ktal que J(u)≤l. (2.9) No es verificable en general, pero si para los problemas de minimizaci´on convexa. La convexidad desempe˜na un importante papel en la programaci´on matem´atica, puesto que permite obtener resultados te´oricos y aplicar m´etodos espec´ıficos. Veremos el concepto de convexidad para conjuntos y para funciones, como tambi´en algunas caracterizaciones. Dentro de la optimizaci´on matem´atica tienen una extremada importancia los problemas convexos, que son aquellos de la forma: m´ın v∈KJ(v) (2.10) donde Kes un conjunto convexo y Juna funci´on convexa. En lo que sigue, supondremos que Ves un espacio de Hilbert equipado con producto escalar denotado ⟨u, v⟩y con norma asociada ∥v∥. Definici´on 2.9 Kes un conjunto convexo si contiene todos los segmentos que unen dos de sus puntos, es decir, si ∀x, y ∈Ky∀λ∈[0,1] se verifica λx + (1 −λ)y∈K. (2.11) TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 2. Optimizaci´on 30 Figura 2.2: Conjunto no convexo Figura 2.3: Conjunto convexo Definici´on 2.10 Diremos que una funci´on Jdefinida sobre un conjunto convexo no vac´ıo K⊂Vcon valores en Res convexa si y solo si J(θu + (1 −θ)v)≤θJ(u) + (1 −θ)J(v)∀u, v ∈K, ∀θ∈[0,1].(2.12) Adem´as, Jse dir´a estrictamente convexa si la desigualdad (2.12) es estricta cuando u=vy θ∈(0,1). Se dice que Jes (estrictamente) c´oncava si −Jes (estrictamente) convexa. Definici´on 2.11 Si Jes una aplicaci´on definida sobre Kcon valores en R, llamamos ep´ıgrafe de Jal conjunto Epi(J) = {(λ, v)∈R×K, λ ≥J(v)}(2.13) La demostraci´on de la siguiente Proposici´on puede encontrarse en [11]. Proposici´on 2.12 Jes convexo si y solo si Epi(J) es un conjunto convexo de R×V. En los casos que se plantean normalmente en la pr´actica, lo deseado siempre es encontrar soluciones globales, es decir, la mejor en t´erminos absolutos. Pero, desafortunadamente, la mayor parte de las t´ecnicas de optimizaci´on (principalmente las que est´an basadas en la derivabilidad) est´an encaminadas a la b´usqueda de ´optimos locales. Por esa raz´on, son necesarios resultados que permitan reconocer cu´ando los ´optimos locales son tambi´en globales. El m´as importante de tales resultados es el teorema siguiente. Teorema 2.13 Sea Jes una funci´on convexa en un conjunto convexo K. Entonces: i) Todo m´ınimo local de Jsobre Kes un m´ınimo global. ii) Adem´as, si Jes estrictamente convexa, entonces existe como m´aximo un punto m´ınimo. Demostraci´on: i) Sea uun m´ınimo local de Jsobre K, de la Definici´on 2.6 tenemos que ∃δ > 0|J(u)≤J(w)∀w∈Ktal que ∥w−u∥< δ. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 2. Optimizaci´on 31 Veamos que J(u)≤J(v)∀v∈K: Tomamos v∈K. Para θ∈(0,1) suficientemente peque˜no w0=θv + (1 −θ)usatisface ∥w0−u∥< δ yw0∈K, pues Kes convexo. Por tanto, J(u)≤J(w0). La convexidad de Jimplica que J(w0)≤θJ(v)+(1−θ)J(u), por tanto J(u)≤θJ(v) + (1−θ)J(u), que simplificando obtenemos J(u)≤J(v), es decir, ues un m´ınimo global sobre K. ii) Por i) deducimos que Js´olo tiene m´ınimos absolutos, pero por ser estrictamente convexa s´olo tiene un m´ınimo absoluto. En efecto, supongamos que u1, u2son dos m´ınimos absolutos, u1=u2. Necesariamente se tendr´a J(u1) = J(u2). Pero entonces para todo θ∈(0,1) se tiene: J(θu2+ (1 −θ)u1)< θJ(u2) + (1 −θ)J(u1) = J(u1) = J(u2) lo que contradice que u1yu2son m´ınimos absolutos. □ A partir de ahora, utilizaremos la idea de “convexidad fuerte” en vez de la convexidad estricta. Definici´on 2.14 Sea Vun espacio de Hilbert y K⊂Vun subconjunto convexo no vac´ıo. Diremos que una funci´on J:K⊂V−→ Res fuertemente convexa en Ksi Jes continua en Ky∃α > 0tal que, para cualesquiera u, v ∈Kyθ∈[0,1], se tiene: J((1 −θ)u+θv)≤(1 −θ)J(u) + θJ(v)−αθ(1 −θ) 2∥u−v∥2(2.14) Tambi´en se dice que Jes α-convexa o que es un funcional el´ıptico. Para la Proposici´on 2.16 necesitaremos previamente el siguiente resultado. Teorema 2.15 (Separaci´on de un punto y un conjunto convexo) Sean Kun conjunto cerrado no vac´ıo convexo de un espacio de Hilbert Vyx0/∈K. Entonces existe un hiperplano cerrado de Vque separa estrictamente x0yK, es decir, existe una forma lineal L∈V′y α∈Rtales que L(x0)< α < L(x)∀x∈K. (2.15) Demostraci´on: Denotemos por xKla proyecci´on de x0sobre K. Como x0/∈K, tenemos xK−x0= 0. Sea Lla forma lineal definida para todo y∈Vpor L(y) = ⟨xK−x0, y⟩y sea α=L(xK)+L(x0) 2. De (1.8) tenemos L(x)≥L(xK)> α > L(x0)∀x∈K, lo que finaliza la prueba. □ TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 2. Optimizaci´on 32 Proposici´on 2.16 Si Jes convexa y continua sobre un conjunto no vac´ıo cerrado y convexo K, entonces existe una forma lineal L∈V′y una constante δ∈Rtal que J(v)≥L(v) + δ∀v∈K. (2.16) Si adem´as Jes fuertemente convexa sobre K, entonces existen dos constantes γ > 0 y δ∈Rtal que J(v)≥γ∥v∥2−δ∀v∈K. (2.17) Demostraci´on: Como Jes continua y convexa sobre K, se tiene que Epi(J) es un subconjunto cerrado (pues Jes continuo sobre K), convexo (pues Jes convexo en U) y no vac´ıo. Tomemos v0∈Kyλ0∈Rtales que λ0≤J(v0). Como (λ0, v0)/∈Epi(J), podemos aplicar el Teorema de separaci´on de un punto y un convexo, deduciendo la existencia de α, β ∈Ry una forma lineal L∈V′tales que βλ +L(v)> α > βλ0+L(v0)∀(λ, v)∈Epi(J).(2.18) Como, para vfija, podemos tomar λarbitrariamente grande en el lado izquierdo de (2.18), es evidente que β≥0. Adem´as, como podemos tomar v=v0en el lado izquierdo de (2.18), βno puede ser cero. Por tanto, tenemos β > 0 y deducimos que J(v) + L(v) β>α β∀v∈K, lo que prueba (2.16). Veamos ahora (2.17). Consideramos v0∈Kfijo. Para v∈K(2.14) y (2.16) implican J(v) 2+J(v0) 2≥Jv+v0 2+α 8∥v−v0∥2≥L(v) + L(v0) 2+α 8∥v−v0∥2+δ. De aqu´ı deducimos J(v)≥α 4∥v∥2−α 2⟨v, v0⟩+L(v) + C1, con C1=α 4∥v0∥2+L(v0)−J(v0) + 2δ. Aplicando la desigualdad de Cauchy-Schwarz, deducimos J(v)≥α 4∥v∥2−∥L∥V′+α∥v0∥ 2∥v∥+C1≥α 8∥v∥2−C, para cierta constante C. □ Para los resultados de existencia y unicidad Vser´a un espacio de Hilbert, Kun conjunto cerrado convexo de VyJuna funci´on continua convexa sobre K. Veamos un primer resultado en el caso que Jes fuertemente convexa. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 2. Optimizaci´on 33 Teorema 2.17 Sea Kun conjunto no vac´ıo cerrado convexo de un espacio de Hilbert VyJ una funci´on continua α-convexa sobre K. Entonces, existe un ´unico m´ınimo ude Jsobre K. Adem´as, se cumple ∥v−u∥2≤4 α(J(v)−J(u)) ∀v∈K. (2.19) Demostraci´on: Sea (un)n≥1una sucesi´on minimizante de Jsobre K. De (2.17) deducimos que Jest´a acotada inferiormente sobre K, y para n, m ∈N, (2.14), tomando θ=1 2, implica que α 8∥un−um∥2+Jun+um 2−´ınf v∈KJ(v)≤1 2J(un)−´ınf v∈KJ(v)+1 2J(um)−´ınf v∈KJ(v). Esto demuestra que la sucesi´on (un)n≥1es de Cauchy y por tanto converge a uque es un punto m´ınimo de Jsobre K, ya que Jes continua y Kcerrado. La unicidad la hemos probado en el Teorema 2.13. Finalmente, si consideramos v∈K, como Kes convexo u+v 2∈K, y aplicando (2.14) con θ=1 2obtenemos α 8∥u−v∥2≤J(u) 2+J(v) 2−Ju+v 2≤J(u)−J(v) 2, ya que J(u)≤Ju+v 2. □ Es posible generalizar el Teorema 2.17 al caso de funciones Jque son s´olo convexas (y no fuertemente convexas). Teorema 2.18 Sea Kun conjunto convexo cerrado no vac´ıo de un espacio de Banach reflexivo VyJuna funci´on continua convexa sobre Ky que satisface la propiedad “infinito en infinito” (2.8) . Entonces existe un m´ınimo de Jsobre K. Demostraci´on: Sea (un)n≥1una sucesi´on minimizante de Jsobre K, de (2.8) deducimos que (un)n≥1est´a acotada. Gracias al Lema 1.82, podemos considerar una subsucesi´on (unk)k≥1 que converge d´ebilmente al l´ımite u∈V. Por ser Juna funci´on continua y convexa se satisface J(u)≤l´ım k´ınf J(unk) = ´ınf v∈KJ(v), de donde se concluye que ues un m´ınimo de Jsobre K. □ Observaci´on 2.19 El Teorema 2.18 nos garantiza la existencia de un m´ınimo, pero no dice nada acerca de la unicidad o la estimaci´on del error. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 3 Optimizaci´on diferenciable La Teor´ıa de la diferenciaci´on en espacios de dimensi´on infinita tiene sus comienzos en 1887 con V. Volterra, al considerar ´este las derivadas variacionales de funciones de C([a, b]) en R. Una de las m´as importantes motivaciones para el desarrollo del C´alculo Diferencial en espacios de dimensi´on infinita proviene de la teor´ıa cl´asica del C´alculo de Variaciones. A partir de ahora, supondremos que Ves un espacio real de Hilbert y que Jes una funci´on continua con valores en R.El producto escalar en Vse denota ⟨u, v⟩y la norma asociada ∥u∥. 3.1. La diferencial de Fr´echet y de Gˆateaux Para la elaboraci´on de esta Secci´on, se han seguido principalmente [7] y [13]. Definici´on 3.1 Diremos que la funci´on J, definida en un entorno de u∈Vcon valores en R, es diferenciable en el sentido de Fr´echet en usi existe una forma lineal continua en V,L∈V′, tal que J(u+w) = J(u) + L(w) + o(w),con l´ım w→0|o(w)| ∥w∥= 0 (3.1) Llamamos a Lla derivada de Jen uy denotamos L=J′(u). Observaci´on 3.2 La Definici´on 3.1 es de hecho v´alida si Ves s´olo un espacio de Banach (no usamos el producto escalar en (3.1)). Podemos generalizar la definici´on anterior en el caso de que el espacio de llegada sea otro espacio de Hilbert W. Definici´on 3.3 La funci´on f, definida en un entorno de u∈Vcon valores en W, es diferenciable en el sentido de Fr´echet en usi existe una aplicaci´on lineal y continua, L:V−→ W, tal que f(u+w) = f(u) + L(w) + o(w),con l´ım w→0∥o(w)∥ ∥w∥= 0 (3.2) 34 Cap´ıtulo 3. Optimizaci´on diferenciable 35 Ejemplo 3.4 Sea (X, ∥·∥) un espacio normado, para la funci´on real J:X−→ Rdefinida por J(x) = ∥x∥2, se tiene que Jes diferenciable en el origen y su diferencial es la aplicaci´on nula en X. En efecto, l´ım w→0 J(0 + w)−J(0) −L(w) ∥w∥= l´ım w→0∥w∥2 ∥w∥= 0 considerando Lcomo la aplicaci´on nula en X. Existen otras ideas de diferenciabilidad, m´as d´ebiles que en el sentido de Fr´echet. Definici´on 3.5 Diremos que la funci´on J, definida en un entorno de u∈Vcon valores en R, es diferenciable en el sentido de Gˆateaux en uy en la direcci´on w∈Vsi existe el siguiente l´ımite: l´ım δ→0 J(u+δw)−J(u) δ(3.3) Diremos que es diferenciable en el sentido de Gˆateaux en u∈Vsi el l´ımite (3.3) existe ∀w∈V. Vemos a continuaci´on dos ejemplos en los cuales en uno se cumple que la funci´on es diferenciable en el sentido de Gˆateaux y en el otro no. Ejemplo 3.6 Consideremos el espacio de Banach X:= C([a, b]) con su norma usual y consideremos el funcional J:X−→ Rdefinido por J(u) = Zb a (sen3(x) + u2(x)) dx el cual est´a definido en todo X. Veamos ahora la variaci´on de Gˆateaux en una direcci´on wy en un punto u. Tenemos que evaluar: J(u+δw)−J(u) δ=1 δZb a ((u+δw)2(x)−u2(x)) dx =1 δZb a (u2(x)+2δw(x)u(x) + δ2w2(x)−u2(x)) dx = 2 Zb a u(x)w(x)dx +δZb a w2(x)dx Con lo cual se tiene que l´ım δ→0 J(u+δw)−J(u) δ= 2 Zb a u(x)w(x)dx Esto significa que existe la derivada de Gˆateaux en toda direcci´on y adem´as es una aplicaci´on lineal y continua por lo tanto es Gˆateaux diferenciable. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 3. Optimizaci´on diferenciable 36 Ejemplo 3.7 Sea (X, ∥·∥) un espacio normado y J:X−→ Rdefinida por J(x) = ∥x∥. Si w∈Xes no nulo, y tomamos u= 0 obtenemos el siguiente l´ımite l´ım δ→0|δ|∥w∥ δ Es evidente que no existe, por lo tanto el funcional Fno tiene derivada de Gˆateaux en ninguna direcci´on en el punto u= 0. Proposici´on 3.8 Sea F:V−→ Runa funci´on diferenciable en el sentido de Fr´echet en u0 entonces, F es diferenciable en el sentido de Gˆateaux en ese punto. ([12]) Demostraci´on: Sea w∈Vun vector no nulo. En efecto, como Fes diferenciable Fr´echet sabemos que L∈V′con lo cual fijado wse tendr´a que l´ım δ→0 F(u0+δw)−F(u0)−L(u0)(δw) ∥δw∥= 0 lo que implica que l´ım δ→0|δ| δ F(u0+δw)−F(u0)−δL(u0)(w) |δ|∥w∥= 0 y simplificando l´ım δ→0F(u0+δw)−F(u0) δ−L(u0)(w)= 0 Por tanto hemos probado que si Fes diferenciable en el sentido de Fr´echet entonces tambi´en lo es en el sentido de Gˆateaux. □ Veamos un ejemplo que muestra que la implicaci´on contraria es falsa. Ejemplo 3.9 F(x, y) =      xy3 x2+y6si (x, y)= (0,0) 0 si (x, y) = (0,0) Esta funci´on no es continua en el punto (0, 0) y entonces no puede ser diferenciable Fr´echet en dicho punto. Sin embargo, las derivadas direccionales son todas nulas, y por lo tanto la funci´on es diferenciable Gˆateaux en el origen. Proposici´on 3.10 Sea Juna aplicaci´on diferenciable Gˆateaux de Ven Ryα > 0. Las siguientes afirmaciones son equivalentes Jes α-convexa sobre V(3.4) J(v)≥J(u) + ⟨J′(u), v −u⟩+α 2∥v−u∥2,∀u, v ∈V(3.5) ⟨J′(u)−J′(v), u −v⟩ ≥ α∥u−v∥2,∀u, v ∈V(3.6) TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 3. Optimizaci´on diferenciable 37 Demostraci´on: Veamos en primero lugar (3.4) =⇒(3.5). Suponemos que Jes α-convexa sobre V, entoneces aplicando (2.14) con θ∈(0,1), obtenemos J(u+θ(v−u)) −J(u) θ≤J(v)−J(u)−α 2(1 −θ)∥v−u∥2. Tomando l´ımite cuando θ→0+, deducimos (3.5). Veamos ahora (3.5) =⇒(3.6). Consideramos (3.5), u, v ∈Vy lo aplicamos a (u, v), (v, u) y sumamos: J(v)≥J(u) + ⟨J′(u), v −u⟩+α 2∥v−u∥2, J(u)≥J(v) + ⟨J′(v), u −v⟩+α 2∥u−v∥2, entonces −⟨J′(u), v −u⟩−⟨J′(v), u −v⟩ ≥ α∥u−v∥2, de donde deducimos ⟨J′(u)−J′(v), u −v⟩ ≥ α∥u−v∥2. Por ´ultimo, (3.6) =⇒(3.4). Para u, v ∈V, t ∈R, consederamos φ(t) = J(u+t(v−u)). Entonces φes derivable y por lo tanto continua en R, φ′(t) = ⟨J′(u+t(v−u)), v −u⟩. De (3.6), φ′(t)−φ′(s) = α(t−s)∥v−u∥2,si t≥s. Tomando θ∈(0,1) e integrando respecto de ten el intervalo [θ, 1] y respecto de sen el intervalo [0, θ], obtenemos θφ(1) + (1 −θ)φ(0) −φ(θ)≥αθ(1 −θ) 2∥v−u∥2, es decir, Jes α-convexa sobre V. □ Observaci´on 3.11 Un caso particular de la proposici´on anterior es el caso α= 0, en el que Jes convexa sobre V. Proposici´on 3.12 Sea Juna funci´on diferenciable Gˆateaux sobre V. Ser´a estrictamente convexa si y solo si J(w)> J(v) + ⟨J′(v), w −v⟩,∀v, w ∈V, v =w. (3.7) Demostraci´on: Sean v, w ∈V, dos puntos distintos de Vyµ∈(0,1). Sea λ∈(0,1) un n´umero fijo. Como v+µ(w−v) = 1−µ λv+µ λ(v+λ(w−v)), se deduce: J(v+µ(w−v)) ≤1−µ λJ(v) + µ λJ(v+λ(w−v)),0≤µ≤λ. Por tanto, si la funci´on Jes estrictamente convexa, puesto que λ < 1 se tiene: J(v+µ(w−v)) −J(v) µ≤J(v+µ(w−v)) −J(v) λ< J(w)−J(v),0≤µ≤λ TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 4. M´etodos num´ericos en optimizaci´on sin restricciones 44 En efecto, puesto que ϕn:R−→ Res continua, estrictamente convexa y coercitiva se deduce que tiene un ´unico m´ınimo ρnen R, ϕn(ρn) = ´ınf ρ∈Rϕn(ρ) es decir: J(un−ρnJ′(un)) = ´ınf ρ∈RJ(un−ρJ′(un)). Por tanto ρnes el paso ´optimo buscado y un+1 =un−ρnJ′(un). Se tendr´a que (ϕn)′(ρn) = 0 y entonces 0=(ϕn)′(ρn) = −J′(un)′J′(un−ρnJ′(un)) = −⟨J′(un+1), J′(un)⟩ 3. La sucesi´on {J(un)}n≥0es mon´onota estrictamente decreciente. En efecto, dado un+1 =un−ρnJ′(un) tenemos un+1 −un=−ρnJ′(un) y por tanto ⟨J′(un+1), un+1 −un⟩= 0. Utilizando de nuevo la Proposici´on 3.10 : J(un)≥J(un+1) + ⟨J′(un+1), un−un+1⟩+α 2∥un−un+1∥2 =J(un+1) + α 2∥un−un+1∥2(4.3) 4. l´ım n→∞ ∥un−un+1∥= 0 y l´ım n→∞ ∥J′(un)−J′(un+1)∥= 0 La sucesi´on {J(un)}n≥0es mon´onota decreciente y acotada inferiormente por J(u). Por tanto, es convergente y el primer l´ımite se concluye de la desigualdad (4.3). Por ser {J(un)}n≥0mon´onota decreciente y Jcoercitiva se deduce que {un}n≥0es acotada. Adem´as, J′(·) es continua (Jes α-convexa) y por tanto uniformemente continua sobre compactos. De ello y de l´ımn→∞ ∥un−un+1∥= 0 se deduce que l´ımn→∞ ∥J′(un)−J′(un+1)∥= 0. 5. l´ım n→∞ J′(un)=0. En primer lugar debido a la ortogonalidad de dos direcciones consecutivas se tiene: ∥J′(un)∥2=⟨J′(un), J′(un)−J′(un+1)⟩≤∥J′(un)∥∥J′(un)−J′(un+1)∥ y por tanto, ∥J′(un)∥≤∥J′(un)−J′(un+1)∥. El resultado se concluye de 4. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 4. M´etodos num´ericos en optimizaci´on sin restricciones 45 6. l´ım n→∞ un=uy adem´as ∥un−u∥ ≤ 1 α∥J′(un)∥(4.4) α∥un−u∥2≤ ⟨J′(un)−J′(u), un−u⟩=⟨J′(un), un−u⟩≤∥J′(un)∥∥un−u∥, de donde se concluyen ambos resultados al aplicar 5. □ 4.2. Algoritmo de gradiente con paso fijo Se trata de un m´etodo m´as simple que el de gradiente con paso ´optimo ya que en cada etapa nen lugar de calcular ρnresolviendo un problema de m´ınimos unidimensional, consideramos ρ un par´ametro positivo fijo. Por tanto, la sucesi´on (un) viene dada por un+1 =un−ρJ′(un) (4.5) Este algoritmo se puede encontrar en [7]. Teorema 4.2 Suponemos que Jes α-convexa y diferenciable y que Jes Lipschitziana sobre V, es decir que existe una constante C > 0tal que ∥J′(v)−J′(w)∥ ≤ C∥v−w∥,∀v, w ∈V. (4.6) Entonces, si 0<ρ< 2α C2, el algoritmo de gradiente con paso fijo converge: para cualquier u0, la sucesi´on (un)definida por un+1 =un−ρJ′(un)converge a la soluci´on ude (4.1). Demostaci´on : Tomamos vn=un−u. Bajo las condiciones del enunciado se tiene que el funcional Jadmite un ´unico m´ınimo u∈Vque satisface la ecuaci´on de Euler J′(u)=0 en V. Por tanto, vn+1 =vn−ρ(J′(un)−J′(u)), de donde deducimos lo siguiente: ∥vn+1∥2=∥vn∥2−2ρ⟨J′(un)−J′(u), un−u⟩+ρ2∥J′(un)−J′(u)∥2 ≤ ∥vn∥2−2ρ⟨J′(un)−J′(u), un−u⟩+ρ2C2∥un−u∥2 ≤ ∥vn∥2−2ρα∥un−u∥2+ρ2C2∥un−u∥2 = (1 −2ρα +ρ2C2)∥vn∥2 Consideramos ahora el polinomio P(ρ)=1−2ρα +ρ2C2. Calculamos P′(ρ) = −2α+ 2ρC2yP(0) = 1. m´ın ρ≥0P(ρ) = P(α C2)=1−α2 C2,veamos cuando se cumple 0 <1−2ρα +ρ2C2<1 TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 4. M´etodos num´ericos en optimizaci´on sin restricciones 46 Si ρ(C2ρ−2α)<0 =⇒ρ < 0 o C2ρ−2α < 0. No es posible ρ < 0 pues por estar en el Algoritmo de gradiente con paso fijo sabemos que ρ≤0, por tanto tenemos C2ρ−2α < 0. De ah´ı deducimos ρ < 2α C2. Concluimos que para 0 <ρ< 2α C2tenemos 1−2ρα+ρ2C2∈(0,1) y por tanto deducimos la convergencia. □ En la pr´actica para elegir el algoritmo con el que trabajaremos utilizaremos la tasa de convergencia del algoritmo, que fija el n´umero de iteraciones necesarias que hay que hacer para que el error un−usea menor que una tolerancia fijada a priori. 4.3. M´etodo del gradiente conjugado para funcionales cuadr´aticos Los m´etodos anteriores utilizaban en cada iteraci´on una direcci´on de descenso localmente ´optima ligada al funcional Jconsiderado (la de J′(un)). Sin embargo, es posible encontrar direcciones de descenso mejoradas con respecto a la del gradiente. Se trata de m´etodos iterativos que aplicados al caso de un funcional cuadr´atico J:RN−→ R obtienen el ´optimo en un n´umero de pasos menor o igual que N. Este m´etodo se puede encontrar en [13]. Veamos primero una breve introducci´on sobre los m´etodos de direcciones conjugadas. Sea J:RN−→ Run funcional cuadr´atico cualquiera, J(v) = 1 2⟨Av, v⟩−⟨b, v⟩=1 2v′Av −v′b, donde, A∈ MN×Nes una matriz sim´etrica, definida positiva y b∈RN. El principio de los m´etodos de direcciones conjugadas consiste en a partir de un punto u0∈RN, minimizar J(v) siguiendo sucesivamente Ndirecciones linealmente independientes d0, d1, . . . , dN−1que poseen la propiedad de ser mutuamente conjugadas con respecto a la forma cuadr´atica J(v), es decir, (di)′Adj= 0, i =j, 0≤i, j ≤N−1. Supongamos entonces que para n= 0, . . . , N −2, un+1 se calcula a partir de unde la forma: un+1 =un+ρndn, J(un+ρndn) = m´ın ρ∈RJ(un+ρdn). Entonces el punto uNobtenido en la etapa N, es decir: uN=uN−1+ρN−1dN−1=··· =u0+ N−1 X j=0 ρjdj, TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 4. M´etodos num´ericos en optimizaci´on sin restricciones 47 es necesariamente el ´optimo del problema, es decir, verifica: J′(uN) = AuN−b= 0 Como ρkminimiza la funci´on ϕn(ρ) = J(un+ρdn), se tendr´a, (ϕn)′(ρn) = 0, es decir: (dn)′J′(un+1)=(dn)′J′(un+ρndn) = (dn)′(A(un+ρndn)−b) Por tanto, (dn)′(Aun−b) + ρn(dn)′Adn= 0, de donde deducimos ρn=−(dn)′(Aun−b) (dn)′Adn Obs´ervese que el denominador en la f´ormula anterior no se anula por ser la matriz Adefinida positiva. Teniendo en cuenta que un=u0+ n−1 X j=0 ρjdj, se puede escribir (dn)′Aun= (dn)′Au0+ n−1 X j=0 ρj(dn)′Adj= (dn)′Au0 y por tanto tenemos equivalentemente ρn=−(dn)′(Au0−b) (dn)′Adn Ahora podemos probar la siguiente propiedad, caracter´ıstica de los m´etodos de direcciones conjugadas. Teorema 4.3 Para todo n (1 ≤n≤N)el punto: un=u0+ n−1 X j=0 ρjdj, es el ´optimo de Jen la variedad af´ın Vn=u0+⟨d0, d1, . . . , dn−1⟩. En particular, uN=u0+ N−1 X j=0 ρjdj, es el ´optimo de Jen RN. Demostraci´on: Observamos que para todo i(0 ≤i≤n−1) (di)′Aun= (di)′Au0+ n−1 X j=0 ρj(di)′Adj= (di)′Au0+ρi(di)′Adi, de donde se deduce, utilizando la expresi´on encontrada anteriormente para ρi: TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 4. M´etodos num´ericos en optimizaci´on sin restricciones 48 (di)′Aun= (di)′Au0−(di)′(Au0−b) y finalmente (di)′(Aun−b)=0, i = 0,1, . . . , n−1. Esto demuestra que J′(un) = Aun−bes ortogonal a la variedad lineal Vn, es decir, J′(un)(v−w)=0,∀v, w ∈Vn, y por tanto unes el ´optimo de Jen Vn. En particular, para n=N, VN=RN(pues d0, d1, . . . , dN−1son Nvectores linealmente independientes) y uNes el m´ınimo de Jen RN. □ As´ı pues, un m´etodo de direcciones conjugadas converge en Netapas, a lo sumo, cuando se trata de minimizar un funcional cuadr´atico en RN. Como existen diversas posibilidades de elecci´on de direcciones conjugadas d0, d1, . . . , dN−1, se pueden construir numerosos algoritmos basados en el principio general de direcciones conjugadas. Veamos el m´etodo del gradiente conjugado. Consideramos J:RN−→ Run funcional cuadr´atico cualquiera, J(v) = 1 2⟨Av, v⟩−⟨b, v⟩=1 2v′Av −v′b, donde, A∈ MN×Nes una matriz sim´etrica, definida positiva y b∈RN. La idea del m´etodo del gradiente conjugado, introducido por Hestenes y Stieffel en 1952, es construir progresivamente las direcciones d0, d1, . . . , dN−1, mutuamente conjugadas con respecto a la matriz A. En cada etapa n, la direcci´on dnes obtenida por combinaci´on lineal de −J′(un) y de las direcciones precedentes d0, d1, . . . , dn−1, dn=−J′(un) + n−1 X j=0 βjdj=−(Aun−b) + n−1 X j=0 βjdj, eligiendo los coeficientes βjde la combinaci´on lineal para que dnsea conjugada con las direcciones anteriores. Notamos por gn:= J′(un) = Aun−b. Entonces el m´etodo toma la forma siguiente u0∈RNdado. Sean g0=Au0−b, d0=−g0,        un+1 =un+ρndn,con ρn=−⟨dn, gn⟩ ⟨Adn, dn⟩n≥0 dn+1 =−gn+1 +βndn,con βn=⟨Adn, gn+1⟩ ⟨Adn, dn⟩n≥0 Para demostrar que el algortimo converge en Netapas es suficiente verificar que las direcciones d0, d1, . . . , dN−1, son mutuamente conjugadas con respecto a la matriz A. Teorema 4.4 En una iteraci´on n cualquiera del algoritmo en la que el ´optimo aun no se haya alcanzado, es decir, J′(ui) = Aui−b= 0, i = 0,1, . . . , n, se tiene TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 4. M´etodos num´ericos en optimizaci´on sin restricciones 49 ρn=⟨gn, gn⟩ ⟨Adn, dn⟩= 0, βn=⟨gn+1 −gn, gn+1⟩ ⟨gn, gn⟩=⟨gn+1, gn+1⟩ ⟨gn, gn⟩. Adem´as, las direcciones d0, d1, . . . , dn+1 generadas por el algoritmo son mumtuamente conjugadas. Demostraci´on: Se razona por inducci´on en nsuponiendo que d0, d1, . . . , dnson conjugadas. De la definici´on del algoritmo se tiene dn=−gn+βn−1dn−1, ρn=−⟨dn, gn⟩ ⟨Adn, dn⟩=⟨gn, gn⟩ ⟨Adn, dn⟩−βn⟨gn, dn−1⟩ ⟨Adn, dn⟩ Como d0, d1, . . . , dn−1son conjugadas, unes el m´ınimo de Jsobre la variedad Vn=u0+⟨d0, d1, . . . , dn−1⟩. Por tanto, ⟨gn, dn−1⟩= 0 y se obtiene la expresi´on deseada para ρn. Notemos ahora que gn+1 −gn=A(un+1 −un) = ρnAdn. Se tiene entonces que ⟨Adn, gn+1⟩=1 ρn⟨gn+1 −gn, gn+1⟩. Utilizando la expresion que acabamos de obtener para ρn, podemos poner: βn=⟨Adn, gn+1⟩ ⟨Adn, dn⟩=⟨Adn, dn⟩ ⟨gn, gn⟩·⟨gn+1 −gn, gn+1⟩ ⟨Adn, dn⟩ =⟨gn+1 −gn, gn+1⟩ ⟨gn, gn⟩=⟨gn+1, gn+1⟩ ⟨gn, gn⟩ donde la ´ultima igualdad es consecuencia de que gn=dn−βn−1dn−1∈ ⟨d0, d1, . . . , dn⟩ ygn+1 es ortogonal a este subespacio. Probamos ahora que dn+1 es una direcci´on conjugada con d0, d1, . . . , dn:⟨Adi, dn+1⟩= 0, i= 0,1, . . . , n. En primer lugar se tiene por la definici´on de dn+1 yβn: ⟨Adn, dn+1⟩=⟨Adn,−gn+1 +βndn⟩=−⟨Adn, gn+1⟩+βn⟨Adn, dn⟩= 0. Falta verificar que ⟨Adi, dn+1⟩= 0, i = 0,1, . . . , n −1. Se tiene por la hip´otesis de inducci´on: ⟨Adi, dn+1⟩=−⟨Adi, gn+1⟩+βn⟨Adi, dn⟩=−⟨Adi, gn+1⟩. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 4. M´etodos num´ericos en optimizaci´on sin restricciones 50 Puesto que ui+1 =ui+ρidiyρi= 0 tenemos: Adi=1 ρiA(ui+1 −ui) = 1 ρi(gi+1 −gi), i = 0,1, . . . , n −1. Poniendo gi+1 =−di+1 +βidiygi=−di+βi−1di−1, se deduce que Adies una combinaci´on lineal de di−1, diydi+1 (para i= 0, g0=−d0yAd0es una combinaci´on lineal de d1y d0). Puesto que d0, d1, . . . , dnson conjugadas se sabe que el punto un+1 es el m´ınimo de J en la variedad Vn+1 =u0+⟨d0, d1, . . . , dn⟩. Por tanto, gn+1 =J′(un+1) es ortogonal al subespacio ⟨d0, d1, . . . , dn⟩. Como Adipertenece al subespacio para i= 0,1, . . . , n −1 se deduce ⟨Adi, gn+1⟩. □ El algoritmo del m´etodo iterativo de gradiente conjugado para resolver sistemas de la forma Au =bcon matriz Asim´etrica y definida positiva es el siguiente: (consideramos rn=−gn=b−Aun) 1. Elegir u0∈RN, ε, δ > 0. Tomamos r0=b−Au0, d0=r0. 2. Dado n≥0, si ∥dn∥< δ paramos el algoritmo. 3. Calcular ρn=⟨rn, rn⟩ ⟨dn, Adn⟩, hacer un+1 =un+ρndnyrn+1 =rn−ρnAdn. Si ∥rn+1∥< ε paramos el algoritmo. 4. En caso contario calculamos βn=⟨rn+1, rn+1⟩ ⟨rn, rn⟩ydn+1 =rn+1 +βndny volvemos al paso 2. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 5 Aplicaci´on: resoluci´on edp no lineal Sea Ω un abierto acotado regular de R2con ∂Ω=Γ0∪Γ1yJ:V−→ Rel funcional dado por J(v) = 1 2ZΩ|∇v|2dx +1 4ZΩ|v|4dx +1 2ZΩ|v|2dx −1 2ZΩ fv dx ∀v∈V, definido sobre V={v∈H1(Ω) : v|Γ0= 0}espacio de Hilbert para el producto escalar ⟨v, w⟩=⟨v, w⟩H1(Ω) =⟨v, w⟩L2(Ω) +⟨∇v, ∇w⟩L2(Ω) ∀v, w ∈Vyf∈L2(Ω). ∥v∥=∥v∥H1(Ω) =∥v∥1,2;Ω =RΩ|v(x)|2+|∇v(x)|21/2∀v∈V. Consideramos el problema de m´ınimos: (P) Hallar u∈Vtal que J(u) = m´ın v∈VJ(v). Nuestro objetivo es resolver (P) mediante el Algoritmo del Gradiente con Paso ´ Optimo. 5.1. Marco te´orico para la soluci´on del problema En primer lugar comprobemos que nuestro problema (P) admite una ´unica soluci´on u∈V. Veamos que se cumplen las hip´otesis del Teorema 2.17: 1. Jest´a bien definido. Es cierto pues cada una de las integrales est´a bien definida. Tomando v∈V, todas las integrales que intervienen en Json finitas, por lo que Jest´a bien definido en Vy toma valores en R. Viendo la continuidad de Jestamos comprobando lo que nos piden. Aplicando la Desigualdad de H¨older (Proposici´on 1.30) tenemos: ZΩ|∇v|2dx ≤ ∥∇v∥2 2,Ω≤ ∥v∥2 1,2,Ω, 51 Cap´ıtulo 5. Aplicaci´on: resoluci´on edp no lineal 52 ZΩ|v|2dx ≤ ∥v∥2 2,Ω≤ ∥v∥2 1,2,Ω, ZΩ fv dx ≤ ∥f∥2 2,Ω∥v∥2 2,Ω≤ ∥f∥2 2,Ω∥v∥2 1,2,Ω. Y gracias a la Proposici´on 1.78 tenemos que W1,2,→L4(Ω), por lo que se cumple que ZΩ|v4|dx < ∞. 2. Jes F-derivable en V. Veamos en primer lugar que Jes diferenciable en el sentido de Gˆateaux, es decir, que existe el l´ımite (3.3). J(u+δw) = 1 2ZΩ|∇(u+δw)|2dx +1 4ZΩ|u+δw|4dx +1 2ZΩ|u+δw|2dx −ZΩ f(u+δw) =1 2ZΩ (|∇u|2+δ2|∇w|2+ 2δ∇u∇w)dx +1 4ZΩ (u4+ 6δ2u2w2+ 4δu3w)dx +1 4ZΩ (4δ3uw3+δ4w4)dx +1 2ZΩ (u2+δ2w2+ 2δuw)−ZΩ (fu +δfw)dx. J(u+δw)−J(u) δ=1 2ZΩ (δ|∇w|2+ 2∇u∇w+δw2+ 2uw)dx +1 4ZΩ (6δu2w2+ 4u3w)dx +1 4ZΩ (δ3w4+ 2δ2uw3)dx −ZΩ fw dx. Tomando l´ımite cuando δ→0 obtenemos: l´ım δ→0 J(u+δw)−J(u) δ=ZΩ (∇u∇w+uw +u3w−fw)dx =δF(u), por tanto, existe el l´ımite y Jes diferenciable en el sentido de Gˆateaux. Por la Proposici´on 3.8 sabemos que si Jes diferenciable en el sentido de Fr´echet entonces tambi´en lo es en sentido de Gˆateaux. En tal caso, ambas derivadas coinciden. Consideramos la diferencial de Jen el sentido de Gˆateaux y vemos que es diferenciable Fr´echet. |o(w)| ∥w∥=|J(u+w)−J(u)−δF(u)| ∥w∥ = 1 2ZΩ|∇w|2dx +1 2ZΩ|w|2dx +1 4ZΩ (6u2w2+ 2w4+ 4uw3)dx ∥w∥ ≤ 1 2∥∇w∥2 2,Ω+1 2∥w∥2 2,Ω+1 2∥w∥4+∥u∥∥w∥3+3 2∥u∥2∥w∥2 ∥w∥ ≤ 1 2∥w∥2+1 2∥w∥2+1 2∥w∥4+∥u∥∥w∥3+3 2∥u∥2∥w∥2 ∥w∥ w→0 −→ 0 TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 5. Aplicaci´on: resoluci´on edp no lineal 53 Hemos probado que Jes diferenciable en el sentido de Fr´echet y que J′(u)(w) = ZΩ (∇u∇w+uw +u3w−fw)dx. 3. Jes un funcional α-convexo en V(con α= 1). Por la Proposici´on 3.15 sabemos que si Jes dos veces diferenciable de Ven Rentonces que Jsea α-convexo es equivalente a J′′(u)(w, w)≥α∥w∥2∀u, w ∈V. Basta comprobar que J′′(u)(w, w)≥ ∥w∥2. Calculamos J′′(u)(w, w). Primero la diferencial en el sentido de Gˆateaux: J′(u+δw2)−J′(u)(w1) δ=ZΩ (∇w2∇w1+w1w2+3δuw2 2w1+3u2w2w1+δw2 2w1)dx (5.1) (5.1)δ→0 −→ ZΩ (∇w2∇w1+w1w2+ 3u2w2w1)dx =δ2J. Del mismo modo que para calcular J′, vemos que es diferenciable Fr´echet. |o(w)| ∥w2∥=|J′(u+w2)−J′(u)(w1)−δ2J| ∥w2∥=ZΩ (3uw2 2w1+w1w3 2)dx ∥w2∥ ≤ZΩ (|3uw2 2w1|+|w1w3 2|)dx ∥w2∥ Aplicando la Desigualdas de Cauchy-Schwarz tenemos que ZΩ (|3uw2 2w1|+|w1w3 2|)dx ∥w2∥ w2→0 −→ 0 Por tanto, J′′(u)(w1, w2) = ZΩ (∇w2∇w1+w1w2+ 3u2w2w1)dx. J′′(u)(w, w) = ZΩ (|∇w|2+w2+ 3u3w2)dx ≥ZΩ (|∇w|2+w2)dx =∥w∥2 Concluimos que Jes un funcional α-convexo en V. Como hemos probado que Jes un funcional continuo α-convexo sobre Vy considerando el espacio de Hilbert H1(Ω),estamos en las condiciones para aplicar el Teorema 2.17. Por dicho teorema concluimos que existe un ´unico minimo ude Jen V. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 5. Aplicaci´on: resoluci´on edp no lineal 60 Figura 5.4: Funci´on u0: inicializaci´on AGPO Figura 5.5: Primera iteracion del AGPO Figura 5.6: Segunda iteracion del AGPO TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 5. Aplicaci´on: resoluci´on edp no lineal 61 Figura 5.7: Tercera iteracion del AGPO Adem´as, ∥uex∥L2(Ω) = 0.796376, ∥u3∥L2(Ω) = 0.782665 y ∥u3−uex∥L2(Ω) = 0.00694, por lo que verificamos la convergencia del algoritmo. Si tomamos, por ejemplo, n= 140, calculamos ∥u3−uex∥L2(Ω) = 0.00298 y comprobamos que dicho error va disminuyendo respecto al caso anterior (n= 100) al considerar una malla m´as fina. Para este caso, tambi´en han sido necesarias 3 iteraciones. Empleando Paso Fijo: Queremos resolver nuestro problema con el algoritmo de gradiente con paso fijo (visto en la Secci´on 4.2) en lugar de con (AGPO) para comparar ambos m´etodos. Tomamos Nmax = 50. Con este algoritmo son necesarias 38 iteraciones, muchas m´as que en el caso anterior y adem´as ∥u38 −uex∥L2(Ω) = 0.01128, por lo que la aproximaci´on era mejor con el (AGPO). Veamos algunas de las iteraciones: Figura 5.8: 4 ª iteraci´on del Algoritmo de gradiente con paso fijo TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 5. Aplicaci´on: resoluci´on edp no lineal 62 Figura 5.9: 17 ª iteraci´on del Algoritmo de gradiente con paso fijo Figura 5.10: 38 ª iteraci´on del Algoritmo de gradiente con paso fijo 5.2.2. En Ωuna elipse con un agujero Tambi´en podemos aplicar el c´odigo de FreeFEM de la resoluci´on mediante el (AGPO) a una funci´on fgeneral, de la cual no conocemos la soluci´on. Adem´as, consideramos el siguiente dominio: Ω = Ω1\B(0,0.25) ⊂R2donde Ω1={(x, y)∈R2|x= cos(t), y = 0.5 sin(t)}, ∂Ω=Γ0∪Γ1 con Γ1=∂B(0,0.25). Volvemos a considerar el funcional Jdefinido al comienzo del cap´ıtulo y el espacio de Hilbert V={v∈H1(Ω) : v|Γ0= 0}dotado del producto escalar ⟨v, w⟩=⟨v, w⟩H1(Ω) ∀v, w ∈V. Sea el problema de m´ınimos: (P) Hallar u∈Vtal que J(u) = m´ın v∈VJ(v). Nuestro objetivo es resolver (P) mediante el Algoritmo del Gradiente con Paso ´ Optimo. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 5. Aplicaci´on: resoluci´on edp no lineal 63 En este caso, tomamos por ejemplo f1= 10(x2+x+y2). Todos los argumentos probados en la Secci´on 5.1 tambi´en son v´alidos para este dominio y esta funci´on f1. Adem´as, consideramos epsagpo = 10−6. En las gr´aficas siguientes podemos ver tanto el dominio y su mallado, como las iteraciones del algoritmo. Ser´an necesarias tambi´en 3 iteraciones. Figura 5.11: Frontera elipse Figura 5.12: Malla de la elipse En la primera iteraci´on el algor´ıtmo de b´usqueda del intervalo con paso fijo nos da el intervalo [0.9,1.1] y el de la secci´on de oro nos dice que el m´ınimo se encuentra en ρ1= 0.995359 y f(ρ1) = −0.699045. En la segunda iteraci´on el intervalo que contiene al m´ınimo es [0.9,1.1] y este se encuentra en ρ2= 0.993496 y f(ρ2) = −0.699048. En la tercera iteraci´on el intervalo que contiene al m´ınimo es [0.9,1.1] y este se encuentra en ρ2= 0.987347 y f(ρ2) = −0.699048. Finalmente, ∥u3∥L2(Ω) = 0.231649. TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 5. Aplicaci´on: resoluci´on edp no lineal 64 Figura 5.13: Funci´on f1 Figura 5.14: Funci´on u0: inicializaci´on AGPO (para la elipse y f1) Figura 5.15: Primera iteracion del AGPO (para la elipse y f1) TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 5. Aplicaci´on: resoluci´on edp no lineal 65 Figura 5.16: Segunda iteracion del AGPO (para la elipse y f1) Figura 5.17: Tercera iteracion del AGPO (para la elipse y f1) TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Anexo Adjuntamos a continuaci´on los c´odigos de FreeFEM empleados para la resoluci´on de los distintos problemas del Cap´ıtulo 5. Comenzamos con el programa utilizado para resolver el problema original planteado en B(0,1) y la funci´on f. 1// RESOLUCION DEL PROBLEMA PLANTEADO . 2// DOMINIO : B (0 ,1) 3 4// DATOS 5 6real R=1.; // Radio de la bola 7real pi2 = 0.5* pi; // pi /2 8int n =100; // Numero de divisiones en la frontera de Omega 9int L0=9, L1 =12; // Etiquetas para la frontera 10 11 // DATOS PARA LA BUSQUEDA NO RESTRINGIDA 12 real a,b; // Extremos del intervalo buscado 13 real x0=0.; // Valor inicial 14 real s =0.1; // Paso 15 real nmax = 1. e6 ; // Numero maximo de iteraciones 16 17 18 // DATOS PARA LA SECCION DE ORO 19 real gamma =0.5*(1+ sqrt (5)); // Constante gamma 20 real gamma1 = gamma -1, gamma2 =2 - gamma ; 21 real x1= a* gamma1 +b* gamma2 ; 22 real x2= a* gamma2 +b* gamma1 ; 23 real epsoro = 1.e -3; // Epsilon : precision del test de parada , para medir la amplitud del intervalo 24 25 // DATOS ( AGPO ) 26 func u0 = 0; // Valor inicial 27 real Nmax =20; // Numero maximo de iteraciones 28 int k; // Parametro para las iteraciones 29 real epsagpo = 1.e -3; // Epsilon : precision del test de parada 30 31 32 // Frontera del dominio Omega =B (0 ,1) 66 Cap´ıtulo 5. Aplicaci´on: resoluci´on edp no lineal 67 33 border C0 (t=0, pi2 ) {x=R*cos(t); y=R*sin (t) ; label =L0 ;}; 34 border Gamma1 (t=pi2 ,3* pi2) {x=R*cos (t); y=R* sin (t) ; label =L1 ;}; 35 border C2 (t=3* pi2 ,4* pi2 ) {x=R*cos(t); y=R*sin(t) ; label =L0 ;}; 36 37 // Dibujamos la frontera del dominio 38 plot ( C0 (0.25* n)+ Gamma1 (0.5* n)+C2 (0.25* n) ,cmm = " Frontera del dominio ", wait = true); 39 40 41 //Mallado del dominio 42 mesh Th = buildmesh ( C0 (0.25* n)+ Gamma1 (0.5* n)+C2 (0.25* n)); 43 plot (Th , cmm = " Malla del dominio ", wait = true); 44 45 46 // funciones 47 func uex = (1 -x*x -y*y) *(1 - x*x-y* y); // Solucion exacta 48 func f = 8*(1 -2*x*x -2* y*y) + uex + uex * uex * uex ; // Funcion del segundo miembro 49 50 51 // Espacio de elementos finitos 52 fespace Vh(Th , P1 ); 53 Vh g, v; // Variables asociadas a la formulacion variacional del problema Gradiente 54 Vh u; // 55 Vh uexh = uex ; // Funcion uex como elemento de Vh 56 Vh fh = f; // Funcion f como elemento de Vh 57 58 59 // Dibujamos la funcion f como elemento de Vh 60 plot (fh , value = true, fill = true, cmm = "f: funcion segundo miembro", wait =true); 61 62 63 // CALCULO DEL GRADIENTE 64 // Tenemos que resolver el siguiente problema . Para ello definimos previamente el macro grad: 65 66 macro grad (u) [dx(u),dy(u)] // EOM 67 68 problem Gradiente (g ,v, init = 1) = 69 int2d ( Th )( grad (g) ‘* grad (v)) + int2d ( Th )(g*v ) 70 - int2d ( Th )( grad (u) ‘* grad (v)) 71 - int2d ( Th )(u* v) -int2d ( Th)(u*u* u*v) + int2d ( Th)(fh *v) 72 + on(L0 ,g =0.) ; 73 74 75 // FUNCION AUXILIAR PARA EL CALCULO DE LOS COEFICIENTES TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 5. Aplicaci´on: resoluci´on edp no lineal 68 76 // Con esta funcion coefpol calculamos los 5 coeficientes necesarios para el polinomio 77 // el cual queremos calcular su minimo : 78 //p(rho)= c4*x^4 + c3*x^3 + c2*x^2 + c1*x + c0 , 79 func real[int ] coefpol ( real [ int ] vu , real [int] vg) 80 { 81 Vh u, g; 82 u []= vu ; 83 g []= vg ; 84 85 real c0 ,c1 ,c2 ,c3 ,c4; 86 // Definimos los 5 coeficientes 87 c4 = 0.25* int2d ( Th )(g*g*g*g); 88 c3 = - int2d ( Th )(u*g *g* g); 89 c2 = 0.5* int2d ( Th)( grad (g ) ‘* grad (g)) 90 +1.5* int2d ( Th )(u*u* g*g ) + 0.5* int2d ( Th )(g*g ); 91 92 c1 = - int2d ( Th )( grad (g) ‘* grad (u)) 93 - int2d ( Th )(u*u*u*g)- int2d ( Th )(u*g )+ int2d ( Th )( fh *g); 94 95 c0 = 0.5* int2d ( Th)( grad (u ) ‘* grad (u)) 96 + 0.25* int2d ( Th )(u *u* u*u) + 0.5* int2d ( Th)(u*u) - int2d ( Th )( fh *u ); 97 98 real[int ] b =[c4 ,c3 ,c2 ,c1 ,c0 ]; // Devuelve un vector 99 return b; 100 } 101 102 103 // Resolvemos finalmente mediante el Algoritmo de Gradiente con Paso Optimo . 104 105 // ( AGPO ) 106 u= u0; // Inicializamos 107 // Pintamos la solucion inicial 108 plot (u, nbiso = 40 , dim = 3, fill=true, 109 cmm = " u0 : u inicial " , wait = true); 110 111 // Comenzamos el bucle con las iteraciones : 112 for ( k=1; k< Nmax +1; k ++) { 113 114 Gradiente ; // Resolvemos el problema Gradiente y obtenemos g. 115 116 // Algoritmo de Busqueda no Restringida del intervalo con paso fijo 117 // Definicion de la funcion f(x) que queremos minimizar , en nuestro caso es el polinomio p(rho ): 118 func real f(real x) { 119 return coefpol (u [] ,g []) [0]* x^4 + coefpol (u[] ,g []) [1]* x^3 + coefpol (u[] ,g []) [2]* x^2 + coefpol (u [] ,g []) [3]* x + coefpol (u[],g []) [4]; 120 } TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas Cap´ıtulo 5. Aplicaci´on: resoluci´on edp no lineal 69 121 122 // Calculo del minimo de la funcion 123 real f0 = f(x0 ); 124 real f1 = f(x0 + s); 125 126 if (f1 == f0 ) { 127 // El minimo esta en [x0 , x0 + s] 128 a = x0; 129 b = x0 + s; 130 }else if (f1 < f0) { 131 real xi = x0 + s; 132 real fi = f1; 133 real xiprev = x0 ; 134 real fiprev = f0 ; 135 int i; 136 while ( i< nmax +1 && fi < fiprev ) { 137 xiprev = x0 + (i -1) * s;; 138 fiprev = f(xiprev); 139 xi = x0 + i * s; 140 fi = f(xi); 141 i++; 142 } 143 // El minimo esta en [x {i -1} , x{i +1}] 144 a = xiprev -s; 145 b = xi; 146 }else { 147 real xi = x0 - s; 148 real fi = f(xi ); 149 real xiprev = x0 ; 150 real fiprev = f0 ; 151 int i = 1; 152 153 while (i < nmax +1 && fi < fiprev ) { 154 xiprev = x0 - (i -1) * s; 155 fiprev = f(xiprev); 156 xi = x0 - i * s; 157 fi = f(xi); 158 i++; 159 } 160 161 // El minimo esta en [x {-(i+1) }, x{ -(i -1) }] 162 a = xi ; 163 b = xiprev + s; 164 } 165 166 // Imprimir el resultado 167 cout << " Intervalo que contiene el minimo : [" << a << " , " << b << "]" << endl; 168 TFG Laura Mar´ıa Rodr´ıguez Llave. Grado en Matem´aticas