Complexidade de métodos de ponto interior aplicados a problemas de otimização de dimensão infinita

Nuno Miguel Silva Teles Oliveira Complexidade de métodos de ponto interior aplicados a problemas de otimização de dimensão infinita Nuno Miguel Silva Teles Oliveira julho de 2019 UMinho | 2019 Complexidade de métodos de ponto interior aplicados a problemas de otimização de dimensão infinita Universidade do Minho Escola de Ciências julho de 2019 Tese de Doutoramento em Ciências Especialização em Matemática Trabalho efectuado sob a orientação do Gueorgui Vitalievitch Smirnov Nuno Miguel Silva Teles Oliveira Complexidade de métodos de ponto interior aplicados a problemas de otimização de dimensão infinita Universidade do Minho Escola de Ciências DIREITOS DE AUTOR E CONDIÇÕES DE UTILIZAÇÃO DO TRABALHO POR TERCEIROS Este é um trabalho académico que pode ser utilizado por terceiros desde que respeitadas as regras e boas práticas internacionalmente aceites, no que concerne aos direitos de autor e direitos conexos. Assim, o presente trabalho pode ser utilizado nos termos previstos na licença abaixo indicada. Caso o utilizador necessite de permissão para poder fazer um uso do trabalho em condições não previstas no licenciamento indicado, deverá contactar o autor, através do RepositóriUM da Universidade do Minho. Licença concedida aos utilizadores deste trabalho Atribuição CC BY https://creativecommons.org/licenses/by/4.0/ Agradecimentos Ao professor Gueorgui Smirnov, orientador deste trabalho, pelo esforc¸o que a ele dedicou. Ao professor Delfim Torres, pelo seu valioso suporte bibliogr´ afico. A Stanislav Antontsev, pelas suas valiosas sugest˜ oes. ` A Fundac¸˜ ao para a Ciˆ encia e a Tecnologia (FCT), pelo financiamento, atrav´ es da bolsa de doutoramento com referˆ encia SFRH/BD/111854/2015. A todos que, de alguma forma, tornaram poss´ ıvel a realizac¸˜ ao deste trabalho. iii DECLARAÇÃO DE INTEGRIDADE Declaro ter atuado com integridade na elaboração do presente trabalho académico e confirmo que não recorri à prática de plágio nem a qualquer forma de utilização indevida ou falsificação de informações ou resultados em nenhuma das etapas conducente à sua elaboração. Mais declaro que conheço e que respeitei o Código de Conduta Ética da Universidade do Minho. iv Resumo Neste trabalho, s˜ ao estudadas algumas quest˜ oes relativas ` a regularidade da soluc¸˜ ao de problemas de c´ alculo das variac¸˜ oes e de Lagrange. Como resultado desse estudo, apresentamos algumas estimativas explicitas para o controlo ´ otimo de alguns problemas espec´ ıficos. Estas estimativas s˜ ao ainda utilizadas para derivar um limite para a complexidade de um m´ etodo de ponto interior aplicado a um problema de Lagrange convexo. Al´ em disso, ´ e ainda estudado o problema de rastreio regido pela equac¸˜ ao do calor. Obtivemos uma aproximac¸˜ ao por um problema de otimizac¸˜ ao de dimens˜ ao finita e, baseando-nos nessa aproximac¸˜ ao, encontramos um limite para a complexidade do m´ etodo de ponto interior aplicado ao problema de rastreio regido pela equac¸˜ ao do calor. v vi Abstract In this work, some questions regarding the regularity of solution for calculus of variations and Lagrange problems are studied. As a result of this study, we present some explicit estimates for the optimal control of some specific problems. These estimates are used to obtain bound to the complexity of an interior point method applied to a convex Lagrange problem. In addition, we study a tracking problem governed by the heat equation. We obtained an approximation by a finite-dimensional optimization problem and, based on this approximation, we find a bound for the complexity of the interior point method applied to the tracking problem governed by heat equation. vii Teorema 2.1 ([7]).Seja xuma trajet´ oria admiss´ ıvel tal que ˙x´ e essencialmente limitada. Assumimos que x´ e um m´ ınimo (local) de J(isto ´ e, J(x)≤J(y), para todo ytrajet´ oria admiss´ ıvel tal que |x(t)−y(t)| ≤ ε,a≤t≤b, para algum ε > 0). Ent˜ ao, 1. A func¸˜ ao λ(t) = −L˙x(t, x(t),˙x(t)) ´ e absolutamente cont´ ınua e a igualdade d dtL˙x(t, x(t),˙x(t)) = Lx(t, x(t),˙x(t)) verifica-se para quase todo a≤t≤b. 2. A condic¸˜ ao de transversalidade hL˙x(b, x(b),˙x(b)), zbi−hL˙x(a, x(a),˙x(a)), zai ≥ 0 verifica-se para todo (za, zb)pertencente ao cone tangente a Bno ponto (x(a), x(b)). 2.2 Problema de Lagrange Chamamos problema de Lagrange a um problema do tipo minimizar: J(x, u) = Zb a L(t, x(t), u(t))dt, sujeito a: ˙x(t) = g(t, x(t), u(t)) u(t)∈U⊆Rm, (x(a), x(b)) ∈B⊆R2n, (4) onde g´ e uma func¸˜ ao cont´ ınua no conjunto A×UChamamos ` a vari´ avel ucontrolo e ao par (x, u)processo. Dado o problema (4), representamos por H(t, x, ˙x, λ)a func¸˜ ao de Hamilton definida por H(t, x, u, λ0, λ) = λ0L(t, x, ˙x) + hλ, g(t, x(t), u(t))i.(5) 4 Teorema 2.2 ([7]).Seja (x, u)um processo admiss´ ıvel tal que u´ e essencialmente limitado. Assumimos que (x, u)´ e um m´ ınimo (local) de J. Ent˜ ao, 1. Existe uma func¸˜ ao absolutamente cont´ ınua λ(t), e uma constante λ0≥0tais que (λ0, λ) nunca se anula e dλ dt =−∂H ∂x (t, x(t), u(t), λ0, λ(t)) para quase todo a≤t≤b. 2. A condic¸˜ ao de transversalidade hλ(b), zbi−hλ(a), zai= 0 verifica-se para todo (za, zb)pertencente ao cone tangente a Bno ponto (x(a), x(b)). 2.3 Problema de Tempo M´ınimo Seja F:Rn→Rnuma func¸˜ ao mult´ ıvoca com valores compactos e Lipschitziana, isto ´ e, existe Luma constante positiva tal que F(x1)⊆F(x2) + L|x1−x2|Bn, onde Bnrepresenta a bola aberta unit´ aria de dimens˜ ao n. Consideremos o problema de tempo m´ ınimo minimizar: T, sujeito a: ˙x∈F(x), x(0) = x0, x(T)∈S, (6) onde S´ e um conjunto fechado e convexo. Seja ˆx∈AC([0, T],Rn)uma soluc¸˜ ao do problema. Para cada t∈[0, T], consideremos um cone convexo K(t)⊆ T(gr coF, (ˆx(t),˙ ˆx(t))) mensur´ avel. Existem v´ arias condic¸˜ oes necess´ arias de otimalidade para problemas de tempo ´ otimo com inclus˜ oes diferenciais (ver [8, 35]). Para o nosso trabalho, a mais relevante ´ e a proposic¸˜ ao seguinte, que ´ e uma consequˆ encia de [28, Teorema 5]. 5 Proposi¸c˜ao 2.3. Existe uma func¸˜ ao p∈AC([0, T], Rn)tal que 1. ( ˙p(t), p(t)) ∈ −K∗(t),hp(t),˙ ˆx(t)i ≡ h≥0; 2. p(T)∈(T(S, ˆx(T)))∗; 3. |p(T)|>0. No caso dos sistemas de controlo ´ otimo suaves, a aproximac¸˜ ao seguinte ser escolhida como o cone K(t). Seja U⊂Rkef:Rn×U→Rnuma func¸˜ ao diferenci´ avel em xe tal que o conjunto f(x, U)´ e convexo, para todo x∈Rn. Para (ˆx, ˆu)∈Rn×Udenotemos ˆv=f(ˆx, ˆu) eC=∇xf(ˆx, ˆu),K=T(f(ˆx, U),ˆv). Recordemos a seguinte proposic¸˜ ao [29, p. 38]. Proposi¸c˜ao 2.4. A inclus˜ ao {(x, v)∈Rn×Rn|v∈Cx +K}⊂T(grf(·, U),(ˆx, ˆu)) verifica-se. Recordemos tamb´ em a seguinte f´ ormula [29, p. 50]. Proposi¸c˜ao 2.5. Seja C:Rn→Rnum operador linear e K⊂Rnum cone convexo. Ent˜ ao, verifica-se a igualdade {(x, v)∈Rn×Rn|v∈Cx +K}∗={(x∗, v∗)∈Rn×Rn|x∗=−C∗v∗, v∗∈K∗}. 2.4 Equa¸c˜oes Parab´olicas Dado um conjunto aberto X⊆Rn, denotamos por Lp(X, R),1≤p < ∞, o espac¸o das func¸˜ oes mensur´ aveis em Xque satisfazem RX|f|pdx < ∞, por L∞(X, R)o espac¸o das func¸˜ oes essencialmente limitadas e por k·kLp(X,R),1≤p≤ ∞, a norma usual em Lp(X, R). Seja Ω um subconjunto aberto, conexo e limitado de RneT∈R+. Usamos a notac¸˜ ao QTpara o conjunto (0, T)×Ω. Dada uma func¸˜ ao F, o seu gradiente e a matriz Hessiana s˜ ao denotados, respetivamente, por ∇(F)e∇2(F). Definimos ainda os seguintes espac¸os de Hilbert: 6 •W2 2(Ω) ´ e o espac¸o que consiste em todas as func¸˜ oes u∈L2(Ω,R)com derivadas generalizadas uxeuxx, munido da norma kukW2 2(Ω) =kukL2(Ω,R)+kuxkL2(Ω,R)+kuxxkL2(Ω,R); •W1,1 2(QT)´ e o espac¸o que consiste em todas as func¸˜ oes u∈L2(QT,R)com derivadas generalizadas uxeut, munido do produto interno (u, v)W1,1 2(QT)=ZZQT (uv +uxvx+utvt)dxdt; •W1,0 2(QT)´ e o espac¸o que consiste em todas as func¸˜ oes ude L2(QT,R)com derivadas generalizadas ux, munido do produto interno (u, v)W1,0 2(QT)=ZZQT (uv +uxvx)dxdt. Ainda definimos os seguintes espac¸os de Banach: •V2(QT)´ e o espac¸o que consiste em todas as func¸˜ oes u∈W1,0 2(QT)com norma |u|QT= ess sup 0≤t≤Tku(t, ·)kL2(Ω,R)+kuxkL2(QT,R) finita; •V1,0 2(QT)´ e o espac¸o que consiste em todas as func¸˜ oes u∈V2(QT)tais que ku(t+ ∆t, ·)−u(t, ·)kL2(Ω,R)→0quando ∆t→0. Recordemos os seguintes resultados sobre EDP’s. Seja Cuma constante positiva. Consideremos o problema ut=Cuxx −f, u(t, x)=0,(t, x)∈[0, T]×∂Ω, u(0, x) = ψ(x).            (7) Seja I(t1;u, φ) = ZΩ u(t1,·)φ(t1,·)dx −Zt1 0ZΩ uφtdxdt +Zt1 0ZΩ C n X i=1 n X j=1 uxjφxi+fφ!dxdt, (8) 7 Dizemos que uma func¸˜ ao u∈V1,0 2(QT)´ e uma soluc¸˜ ao do problema (7) se a igualdade I(t1;u, φ) = ZΩ ψ(x)φ(0, x)dx se verifica para todo t1∈[0, T],φ∈W1,1 2(QT)com φ(t, x)=0,x6∈ Ω. Recordemos os seguintes resultados (ver, [17, ch. 3]). Teorema 2.6 ([17]).O problema (7) tem uma ´ unica soluc¸˜ ao u∈V1,0 2(QT). Seja k·kq,r a norma definida por kakq,r = ZT 0ZΩ aqdxr/q dt!1/r . Assumimos que a condic¸˜ ao kfkq,r ≤µ1,(9) ´ e satisfeita quando qersatisfazem as condic¸˜ oes 1 r+n 2q= 1 + n 4, q∈2n n+ 2,2, r ∈[1,2] ,para n≥3, q∈(1,2] , r ∈[1,2) ,para n= 2, q∈[1,2] , r ∈1,4 3,para n= 1.                        (10) Teorema 2.7 ([17]).Assuma-se que, para os problemas ut=Cuxx −fm, u(t, x) = 0,(t, x)∈[0, T]×∂Ω, u(0, x) = ψm(x),            (11) as condic¸˜ oes (9)-(10) s˜ ao satisfeitas com as mesmas constantes. Assuma-se tamb´ em que as func¸˜ oes fmeψmconvergem para feψ, respetivamente, nas normas dos espac¸os a que pertencem, de acordo com as condic¸˜ oes (9)-(10). Ent˜ ao, as soluc¸˜ oes umdos problemas (11) convergem fortemente em V1,0 2(QT)para a soluc¸˜ ao udo problema (7). 8 Seja U= ([0, T]×∂Ω) ∪({0}×Ω). Teorema 2.8 ([17]).Seja u∈V1,0 2(QT)a soluc¸˜ ao do problema (7). Se f= 0, ent˜ ao, min{0,ess inf Uu(t, x)} ≤ u(t, x)≤max{0,ess sup U u(t, x)} para quase todo (t, x)em QT. Teorema 2.9 ([17]).Considere-se a func¸˜ ao Γdefinida por Γ(t, x) = 1 (4πCt)n/2exp −|x|2 4Ct. Para todo t > 0, a igualdade ZRn Γ(t, x)dx = 1 verifica-se. 2.5 M´etodo de Minimiza¸c˜ao de Ponto Interior Dado um vetor v∈Rne uma func¸˜ ao F:Rn→Rduas vezes diferenci´ avel, usamos a notac¸˜ ao kvkF x=h[∇2(F)(x)]−1v, vi1/2. Seja P:Rn→Ruma func¸˜ ao convexa. Consideremos o problema P(x)→min, x= (x1, x2, . . . , xn)∈Rn, x2 i≤Ki, i = 1, n.            (12) Seja Fa func¸˜ ao definida por F(x, σ) = −ln(σ−P(x)) −ln(σ−σ)− n X i=1 ln(Ki−x2 i), onde σ= max{x|x2 i≤Ki,i=1,n}P(x)e seja b= (0,1) ∈Rn×R. Consideremos β∈(0,(3 −√5)/2) eγ > 0tal que γ≤√β 1 + √β−β. O M´ etodo de Ponto Interior ´ e apresentado na Tabela 1 (ver [21]). 9 Inicializac¸˜ ao: Tome α0= 0. Escolha uma precis˜ ao ε > 0,x0∈Rneσ0∈Rtal que k∇(F)(x0, σ0)kF (x0,σ0)≤β. Passo k: Fac¸a αk+1 =αk+γ kbkF (xk,σk) , (xk+1, σk+1) = (xk, σk)−[∇2(F)(xk, σk)]−1(αk+1b+∇(F)(xk, σk)). Pare o processo se n+1+(β+√n+ 1)β 1−β≤εαk. Tabela 1: M´ etodo de ponto interior Para encontrar um ponto inicial que satisfac¸a k∇(F)(x0, σ0)kF (x0,σ0)≤βpodemos usar um m´ etodo auxiliar apresentado em [21]. Seja No maior inteiro satisfazendo N ≤ ln (1 + β)(n+ 1) + (β+√n+ 1)β γ(1 −2β)εkbkF (˜x,˜σ) ln 1 + γ β+√n+ 1+ 1, onde (˜x, ˜σ) = argmin (F). Teorema 2.10 ([21]).O M´ etodo de Ponto Interior termina em n˜ ao mais do que Npassos. No momento final, obtemos |P(xN)−P(ˆx)|< ε, onde ˆx´ e a soluc¸˜ ao do problema (12). 10 3 Estimativas expl´ıcitas para a Constante de Lipschitz O estudo da regularidade da soluc¸˜ ao de problemas de otimizac¸˜ ao ´ e de fundamental importˆ ancia. Em particular, a regularidade Lipschitziana permite-nos determinar uma classe de problemas onde o fen´ omeno de Lavrientiev n˜ ao ocorre, permitindo-nos garantir que a soluc¸˜ ao do problema pode ser bem aproximada usando problemas de dimens˜ ao finita. Nesta secc¸˜ ao, estabelecemos estimativas expl´ ıcitas para a constante de Lipschitz de um problema de c´ alculo das variac¸˜ oes (Teorema 3.8.) e para um problema de Lagrange com ponto final livre (Teorema 3.13.) usando apenas os dados do problema. Com base nessas estimativas, derivamos um limite para a complexidade do m´ etodo de ponto interior aplicado a um problema de otimizac¸˜ ao convexo. 3.1 Problema de Lagrange Estudaremos um problema de Lagrange da forma minimizar: J(x, u) = Z1 0 L(t, x(t), u(t))dt, sujeito a: ˙x(t) = g(t, x(t))u(t), x(0) = 0, x(1) ∈S, (13) onde L:R×Rn×Rm→R,g´ e uma matriz de dimens˜ ao n×m,S´ e o conjunto {x∈Rn|Ax ≤b}, onde A´ e uma matriz de dimens˜ ao k×neb∈(R∪{∞})k. A condic¸˜ ao x(1) ∈Spode ainda ser substitu´ ıda por x(1) = b, fazendo as devidas alterac¸˜ oes. Obtemos estimativas expl´ ıcitas para a constante de Lipschitz em casos especiais deste problema: 1. Problema b´ asico de c´ alculo das variac¸˜ oes: g(t, x) = 1; 2. Problema de Lagrange com ponto final livre: S=Rn. Assumimos que as seguintes condic¸˜ oes se verificam: 11 (C1) A func¸˜ ao L(·,·,·)´ e continuamente diferenci´ avel e satisfaz a condic¸˜ ao de super linearidade L(t, x, u)≥θ(|u|)>0,para todo t, x, u, onde limr→∞ r/θ(r)=0. (C2) A func¸˜ ao L(t, x, ·)´ e estritamente convexa, isto ´ e, existe uma constante µ > 0tal que L(t, x, u) + h∇uL(t, x, u), v −ui+µ 2|v−u|2≤L(t, x, v),para todo t, x, u, v. (C3) Existem constantes ξ > 0eδ > 0tais que |∇(t,x)L(t, x, u)| ≤ ξL(t, x, u) + δ, para todo t, x, u. (C4) Existem constantes cg>0ec∇g>0tais que |g(t, x)| ≤ cg,|∇(t,x)g(t, x)| ≤ c∇g,para todo t, x. Assumimos ainda que se verifica a condic¸˜ ao: (C5) Existem constantes ξ > 0eδ > 0tais que |∇(t,x)L(t, x, u)||u| ≤ ξL2(t, x, u) + δ, para todo t, x, u. De facto, a condic¸˜ ao (C5) ´ e uma consequˆ encia das condic¸˜ oes (C1) e (C3). Vejamos que, existe r0>1tal que |u| ≤ θ(|u|)sempre que |u|> r0. Sejam ξ1eδ1as constantes relativas ` a condic¸˜ ao (C3). Sem perda de generalidade, assumimos que ξ1>1eδ1>1. Para |u| ≥ r0, temos |∇(t,x)L(t, x, u)||u| ≤ (ξ1L(t, x, u) + δ1)θ(|u|) ≤(ξ1L(t, x, u) + δ1)L(t, x, u) ≤(ξ1L(t, x, u) + δ1)2 ≤2ξ2 1L2(t, x, u)+2δ2 1. 12 Se |u|< r0eL(t, x, u)≥1, temos |∇(t,x)L(t, x, u)||u| ≤ (ξ1L(t, x, u) + δ1)r0 ≤(ξ1L2(t, x, u) + δ1)r0. Finalmente, se |u|< r0eL(t, x, u)<1, temos |∇(t,x)L(t, x, u)||u| ≤ (ξ1L(t, x, u) + δ1)r0 ≤(ξ1+δ1)r0 ≤(L2(t, x, u) + 1)(ξ1+δ1)r0. Assim, basta tomarmos ξ= max{1,2ξ2 1,(ξ1+δ1)r0}eδ= max{1,2δ2 1,(ξ1+δ1)r0}. Pelas condic¸˜ oes (C1) e (C2), podemos concluir que o problema (13) tem uma soluc¸˜ ao ˆx∈AC([0,1],Rn). Dado (˘x, ˘u)∈AC([0,1],Rn)×L∞([0,1],Rn)um processo admiss´ ıvel do problema (13) e r0>0tal que r/θ(r)≤1, sempre que r > r0, consideramos c=r0+R1 0L(t, ˘x(t),˘u(t))dt. Ent˜ ao, dado M={t∈[0,1]||ˆu(t)| ≤ θ(|ˆu(t)|)}, temos c≥r0+Z1 0 L(t, ˆx(t),ˆu(t))dt > Z[0,1]\M r0dt +ZM L(t, ˆx(t),ˆu(t))dt ≥Z[0,1]\M r0dt +ZM θ(|ˆu(t)|)dt ≥Z1 0|ˆu(t)|dt, (14) uma vez que, para t∈[0,1] \M, temos r0>|ˆu(t)|. Assim, podemos concluir que |ˆx(t)|< cgc, t ∈[0,1]. Consideremos Ω = [0,1] ×cgcBn, onde Bnrepresenta a bola aberta unit´ aria de dimens˜ ao n. 3.2 Equivalˆencia com o problema de tempo ´otimo O estudo deste problema ser´ a feito usando, tal como sugere Gamkrelidze (ver [12, Sec. 8]), a equivalˆ encia entre (13) e um problema de tempo ´ otimo, obtido atrav´ es da introduc¸˜ ao de uma nova vari´ avel τ, definida por τ(κ) = Zκ 0 L(s, x(s), u(s))ds. 13 Proposi¸c˜ao 3.5. Existe uma func¸˜ ao n˜ ao nula (q, p)∈AC([0,ˆ T],R×Rn)tal que dq dτ (τ) = (q(τ) + hˆw(τ), p(τ)i)ˆ Lt(τ) (ˆ L(τ) + β)2,(21) dp dτ (τ) = (q(τ) + hˆw(τ), p(τ)i)∇xˆ L(τ) (ˆ L(τ) + β)2,(22) p(τ) ˆ L(τ) + β−(q(τ) + hˆw(τ), p(τ)i)∇uˆ L(τ) (ˆ L(τ) + β)2= 0,(23) q(τ) + hˆw(τ), p(τ)i ˆ L(τ) + β≡h > 0.(24) Demonstrac¸˜ ao. Da segunda parte da Proposic¸˜ ao 3.1., podemos concluir que (ˆκ, ˆy, ˆw)´ e uma soluc¸˜ ao do problema minimizar: T, sujeito a: d(κ, y) dτ (τ) = (1, w(τ)) L(κ(τ), y(τ), w(τ)) + β, (κ, y)(0) = (0,0) (κ, y)(T)∈(1, S). (25) O problema de tempo ´ otimo minimizar: T, sujeito a: d(κ, y) dτ (τ)∈G(κ, y), (κ, y)(0) = (0,0) (κ, y)(T)∈(1, S). (26) tamb´ em tem uma soluc¸˜ ao (˜κ, ˜y). O Lema de Filippov garante-nos que existe uma func¸˜ ao mensur´ avel (˜ρ, ˜w)tal que d(˜κ, ˜y)(τ) dτ =˜ρ(τ)(1,˜w(τ)) L(˜κ(τ),˜y(τ),˜w(τ)) + β. Aplicando as Proposic¸˜ oes 2.3.-2.5., podemos ver que existem (q, p)∈AC([0,˜ T], R×Rn), uma 20 func¸˜ ao n˜ ao nula, e uma constante h≥0tais que dq dτ (τ) = ˜ρ(τ)(q(τ) + h˜w(τ), p(τ)i)Lt(˜κ(τ),˜y(τ),˜w(τ)) (L(˜κ(τ),˜y(τ),˜w(τ)) + β)2,(27) dp dτ (τ) = ˜ρ(τ)(q(τ) + h˜w(τ), p(τ)i)∇xL(˜κ(τ),˜y(τ),˜w(τ)) (L(˜κ(τ),˜y(τ),˜w(τ)) + β)2,(28) h≡˜ρ(τ)(q(τ) + h˜w(τ), p(τ)i) L(˜κ(τ),˜y(τ),˜w(τ)) + β≥ρ(q(τ) + hw, p(τ)i) L(˜κ(τ),˜y(τ), w) + βρ∈[0,1], w ∈Rn.(29) Da condic¸˜ ao de m´ aximo (29), temos ˜ρ(τ)p(τ) L(˜κ(τ),˜y(τ),˜w(τ)) + β−˜ρ(τ)(q(τ) + h˜w(τ), p(τ)i)∇uL(˜κ(τ),˜y(τ),˜w(τ)) (L(˜κ(τ),˜y(τ),˜w(τ)) + β)2= 0.(30) Se d(˜κ, ˜y)/dτ = (0,0) num conjunto de medida n˜ ao nula, ent˜ ao h= 0. Nos pontos onde ˜ρ(τ)>0, como q(τ) + h˜w(τ), p(τ)i= 0, da condic¸˜ ao (30), obtemos p(τ)=0e, por conseguinte, q(τ)=0, o que ´ e uma contradic¸˜ ao. Logo, ˜ρ= 0 em quase toda a parte, o que ´ e imposs´ ıvel. Assim, d(˜κ, ˜y)/dτ 6= (0,0), em quase todos os pontos τ∈[0,˜ T]. Portanto, as condic¸˜ oes (27)-(29) s˜ ao satisfeitas e ˜ρ(τ)>0em quase todos os pontos τ∈[0,˜ T]. Logo, h > 0, uma vez que a igualdade h= 0 implica, como acima, (q, p)≡0. De (29) obtemos ˜ρ≡1. Assim, podemos identificar as trajet´ orias (ˆκ, ˆy)(·)e(˜κ, ˜y)(·). Ambas s˜ ao soluc¸˜ ao do problema de tempo ´ otimo (26) e satisfazem as condic¸˜ oes de otimalidade (27)-(30) com ˜ρ= 1. Proposi¸c˜ao 3.6. Se q(τ)≤0, ent˜ ao |ˆw(τ)| ≥ (c+α)/T0. Demonstrac¸˜ ao. Multiplicando (23) por ˆw(τ), obtemos (ˆ L(τ) + β)hˆw(τ), p(τ)i= (q(τ) + hˆw(τ), p(τ)i)h∇uˆ L(τ),ˆw(τ)i.(31) Uma vez que q(τ)≤0, por (24), temos hˆw(τ), p(τ)i>0. De (31), temos h∇uˆ L(τ),ˆw(τ)i=hˆw(τ), p(τ)i q(τ) + hˆw(τ), p(τ)i(ˆ L(τ) + β)≥ˆ L(τ) + β e, portanto, β≤ h∇uˆ L(τ),ˆw(τ)i− ˆ L(τ)≤σ(|ˆw(τ)|). 21 Assim, obtemos |ˆw(τ)| ≥ σ−1(β) = σ−1σc+α T0=c+α T0 . Proposi¸c˜ao 3.7. Se q(τ1) = 0 eq(τ)<0,τ∈]τ1, τ2], ent˜ ao |q(τ)|/|p(τ)| ≤ ¯γ,τ∈[τ1, τ2]. Demonstrac¸˜ ao. Uma vez que q(τ)<0,τ∈]τ1, τ2], temos q(τ) + hˆw(τ), p(τ)i |p(τ)|(ˆ L(τ) + β)≤|ˆw(τ)| θ(|ˆw(τ)|) + β≤η. Da desigualdade anterior, de (21) e da condic¸˜ ao (C3), temos  dq(τ) dτ ≤(q(τ) + hˆw(τ), p(τ)i)|ˆ Lt(τ)| (ˆ L(τ) + β)2≤η|p(τ)||ˆ Lt(τ)| ˆ L(τ) + β≤ηξ|p(τ)|, sempre que τ∈[τ1, τ2]. De modo an´ alogo, temos  dp(τ) dτ ≤ξη|p(τ)|. Daqui, obtemos d dτ |q(τ)| |p(τ)|≤|dq(τ)/dτ||p(τ)|+|q(τ)||dp(τ)/dτ| |p(τ)|2≤ξη 1 + |q(τ)| |p(τ)|. Uma vez que q(τ1) = 0, aplicando o Lema de Gronwall, temos |q(τ)| |p(τ)|≤eξη(τ2−τ1)−1.(32) Note-se que τ2−τ1=Zˆκ(τ2) ˆκ(τ1) (L(t, ˆx(t),ˆu(t)) + β)dt ≤c+ (ˆκ(τ2)−ˆκ(τ1))β, eˆκ(τ2)−ˆκ(τ1)≤T0. De facto, uma vez que q(τ)≤0no intervalo [τ1, τ2]et∈[ˆκ(τ1),ˆκ(τ2)], pela Proposic¸˜ ao 3.6. temos |ˆu(t)|=|ˆw(ˆτ(t))| ≥ c+α T0≥c+α. Assim, a desigualdade ˆκ(τ2)−ˆκ(τ1)> T0contradiz (14). Logo, τ2−τ1≤c+T0β. Combinando isto com as condic¸˜ oes (32) e (18), obtemos o resultado. 22 Teorema 3.8. A desigualdade |˙ ˆx(t)| ≤ `= max (%, r2 µ(Λ0+β),Λ1+pΛ2 1+ 8µΛ0 2µ) verifica-se para quase todo t∈[0,1]. Demonstrac¸˜ ao. Consideremos τ∈[0,ˆ T]de tal forma que q(τ)≥0. Da condic¸˜ ao (C2), temos ˆ L(τ)−h∇uˆ L(τ),ˆw(τ)i+µ 2|ˆw(τ)|2≤Λ0. Daqui e da igualdade (31), obtemos µ 2|ˆw(τ)|2≤Λ0−ˆ L(τ) + h∇uˆ L(τ),ˆw(τ)i= Λ0−ˆ L(τ) + hˆw(τ), p(τ)i q(τ) + hˆw(τ), p(τ)i(ˆ L(τ) + β). Se hˆw(τ), p(τ)i>0, ent˜ ao conclu´ ımos µ 2|ˆw(τ)|2≤Λ0−ˆ L(τ) + ˆ L(τ) + β= Λ0+β e, portanto, |ˆw(τ)| ≤ r2 µ(Λ0+β).(33) Se hˆw(τ), p(τ)i ≤ 0, ent˜ ao, pela Proposic¸˜ ao 3.4., temos µ 2|ˆw(τ)|2≤Λ0−ˆ L(τ)≤2Λ0+ Λ1|ˆw(τ)|− µ 2|ˆw(τ)|2 e, portanto, obtemos |ˆw(τ)| ≤ Λ1+pΛ2 1+ 8µΛ0 2µ.(34) Consideremos agora τ∈[0,ˆ T]tal que q(τ)<0. Note-se que a condic¸˜ ao q(τ)<0, para todo τ∈[0,1] ´ e imposs´ ıvel, uma vez que, neste caso, pela Proposic¸˜ ao 3.6., ter´ ıamos |ˆu(t)|=|ˆw(ˆτ(t))| ≥ c+α T0≥c+α, o que contradiz a desigualdade (14). Uma vez que q(τ)<0, pela Proposic¸˜ ao 3.7., q(τ)>−¯γ|p(τ)|. Pelo princ´ ıpio de m´ aximo (23), temos q(τ) + hˆw(τ), p(τ)i ˆ L(τ) + β≥q(τ) + (¯γ+α)hp(τ)/|p(τ)|, p(τ)i L(ˆκ(τ),ˆy(τ),(¯γ+α)p(τ)/|p(τ)|) + β ≥α|p(τ)| L(ˆκ(τ),ˆy(τ),(¯γ+α)p(τ)/|p(τ)|) + β≥α|p(τ)| Λ2+β. (35) 23 Uma vez que % > 0´ e um n´ umero tal que, para todo r > % a condic¸˜ ao (19) se verifica, se tivermos |w|> %, ent˜ ao, pela condic¸˜ ao (C1) e pela Proposic¸˜ ao 3.4., obtemos q(τ) + hw, p(τ)i L(ˆ t(τ),ˆy(τ), w) + β≤|w||p(τ)| max{θ(|w|),µ 2|w|2−Λ1|w|−Λ0}+β<α|p(τ)| Λ2+β. Ora, pela desigualdade (35), podemos ver que w6= ˆw(τ). Portanto, |ˆw(τ)| ≤ %. Combinando isto com as desigualdades (33) e (34), obtemos o resultado. Corol´ario 3.9. Se Ln˜ ao depende da vari´ avel t, ent˜ ao |˙ ˆx(t)| ≤ `= max (r2 µ(Λ0+β),Λ1+pΛ2 1+ 8µΛ0 2µ) para quase todo t∈[0,1]. Demonstrac¸˜ ao. Uma vez que Ln˜ ao depende da vari´ avel t, da condic¸˜ ao (21), temos dq/dτ = 0. Logo, q´ e constante. Como vimos anteriormente, n˜ ao ´ e poss´ ıvel ter q < 0. Logo, q≥0. Assim, a prova deste Corol´ ario coincide com a prova do Teorema 3.8., para q≥0. Exemplo 3.1. Seja ω≥1/2. Consideremos o problema minimizar: Z1 0˙x2(t) + 1 4dt, sujeito a: x(0) = 0, x(1) = ω, (36) cuja trajet´ oria ´ otima ´ eˆx(t) = ωt. Tomando θ(r) = r2+ 1/4, temos r0= 0, uma vez que θ(r)≥r, para todo r > 0. A condic¸˜ ao (C2) ´ e satisfeita com µ= 2 e as condic¸˜ oes (C3) e (C5) s˜ ao satisfeitas para quaisquer valores de ξeδpositivos. Usando ˆxcomo uma trajet´ oria admiss´ ıvel, obtemos c=ω2+ 1/4. Temos ainda Λ0= 1/4,Λ1= 0 eσ(r) = r2−1/4. Pondo T0= 1, temos β= (ω2+ 1/4 + α)2−1/4. Desta forma, a estimativa obtida pelo Corol´ ario 3.9. ´ eω2+ 1/4 + α. Para valores de αsuficientemente pequenos, o erro cometido por esta estimativa ´ e aproximadamente ω+ 1/(4ω)−1, sendo aproximadamente 0, quando ω= 1/2. 24 3.4 Problema de Lagrange com x(1)livre Consideramos agora o problema minimizar: J(x, u) = Z1 0 L(t, x(t), u(t))dt, sujeito a: ˙x(t) = g(t, x(t))u(t), x(0) = 0. (37) Seja (ˆx, ˆu)uma soluc¸˜ ao do problema (37). Consideremos ˆκa func¸˜ ao inversa de τ(κ) = Rκ 0L(s, ˆx(s),ˆu(s))ds eˆyeˆwas func¸˜ oes definidas por ˆy(τ) = ˆx(ˆκ(τ)) e ˆw(τ) = ˆu(ˆκ(τ)), respetivamente. Proposi¸c˜ao 3.10. Existe uma func¸˜ ao n˜ ao nula (q, p)∈AC([0,ˆ T],R×Rn)tal que dq dτ (τ) = −hˆgt(τ) ˆw(τ), p(τ)i ˆ L(τ) + β+(q(τ) + hˆg(τ) ˆw(τ), p(τ)i)ˆ Lt(τ) (ˆ L(τ) + β)2,(38) dp dτ (τ) = −h∇xˆg(τ) ˆw(τ), p(τ)i ˆ L(τ) + β+(q(τ) + hˆg(τ) ˆw(τ), p(τ)i)∇xˆ L(τ) (ˆ L(τ) + β)2,(39) p(ˆ T) = 0,(40) ˆg∗(τ)p(τ) ˆ L(τ) + β−(q(τ) + hˆg(τ) ˆw(τ), p(τ)i)∇uˆ L(τ) (ˆ L(τ) + β)2= 0,(41) q(τ) + hˆg(τ) ˆw(τ), p(τ)i ˆ L(τ) + β≡h > 0.(42) Demonstrac¸˜ ao. Da segunda parte da Proposic¸˜ ao 3.1., podemos concluir que (ˆκ, ˆy, ˆw)´ e uma soluc¸˜ ao do problema minimizar: T, sujeito a: d(κ, y) dτ (τ) = (1, g(κ(τ), y(τ))w(τ)) L(κ(τ), y(τ), w(τ)) + β, (κ, y)(0) = (0,0) κ(T) = 1. (43) 25 O problema de tempo ´ otimo minimizar: T, sujeito a: d(κ, y) dτ (τ)∈G(κ, y), (κ, y)(0) = (0,0) κ(T)=1. (44) tamb´ em tem uma soluc¸˜ ao (˜κ, ˜y). O Lemma de Filippov garante-nos que existe uma func¸˜ ao mensur´ avel (˜ρ, ˜w)tal que d(˜κ, ˜y)(τ) dτ =˜ρ(τ)(1, g(˜κ(τ),˜y(τ)) ˜w(τ)) L(˜κ(τ),˜y(τ),˜w(τ)) + β. Aplicando as Proposic¸˜ oes 2.3.-2.5., podemos ver que existem (q, p)∈AC([0,˜ T], R×Rn), uma func¸˜ ao n˜ ao nula, e uma constante h≥0tais que dq dτ (τ) = −˜ρ(τ)hgt(˜κ(τ),˜y(τ)) ˜w(τ), p(τ)i L(˜κ(τ),˜y(τ),˜w(τ)) + β +˜ρ(τ)(q(τ) + hg(˜κ(τ),˜y(τ)) ˜w(τ), p(τ)i)Lt(˜κ(τ),˜y(τ),˜w(τ)) (L(˜κ(τ),˜y(τ),˜w(τ)) + β)2, (45) dp dτ (τ) = −˜ρ(τ)h∇xg(˜κ(τ),˜y(τ)) ˜w(τ), p(τ)i L(˜κ(τ),˜y(τ),˜w(τ)) + β +˜ρ(τ)(q(τ) + hg(˜κ(τ),˜y(τ)) ˜w(τ), p(τ)i)∇xL(˜κ(τ),˜y(τ),˜w(τ)) (L(˜κ(τ),˜y(τ),˜w(τ)) + β)2, (46) p(˜ T) = 0,(47) h≡˜ρ(τ)(q(τ) + hg(˜κ(τ),˜y(τ)) ˜w(τ), p(τ)i) L(˜κ(τ),˜y(τ),˜w(τ)) + β ≥ρ(q(τ) + hg(˜κ(τ),˜y(τ))w, p(τ)i) L(˜κ(τ),˜y(τ), w) + βρ∈[0,1], w ∈Rm. (48) Da condic¸˜ ao de m´ aximo (48), temos ˜ρ(τ)g∗(˜κ(τ),˜y(τ))p(τ) L(˜κ(τ),˜y(τ),˜w(τ)) + β −˜ρ(τ)(q(τ) + hg(˜κ(τ),˜y(τ)) ˜w(τ), p(τ)i)∇uL(˜κ(τ),˜y(τ),˜w(τ)) (L(˜κ(τ),˜y(τ),˜w(τ)) + β)2= 0. (49) Se d(˜κ, ˜y)/dτ = (0,0) num conjunto de medida n˜ ao nula, ent˜ ao h= 0. Nos pontos onde ˜ρ(τ)>0, como q(τ) + hg(˜κ(τ),˜y(τ)) ˜w(τ), p(τ)i= 0, das condic¸˜ oes (46) e (47), obtemos 26 p(τ)=0e, por conseguinte, q(τ)=0, o que ´ e uma contradic¸˜ ao. Logo, ˜ρ= 0 em quase toda a parte, o que ´ e imposs´ ıvel. Assim, d(˜κ, ˜y)/dτ 6= (0,0) em quase todos os pontos τ∈[0,˜ T]. Portanto, as condic¸˜ oes (45)-(48) s˜ ao satisfeitas e ˜ρ(τ)>0em quase todos os pontos τ∈[0,˜ T]. Logo, h > 0, uma vez que a igualdade h= 0 implica, como acima, (q, p)≡0. De (48) obtemos ˜ρ(τ)=1. Assim, podemos identificar as trajet´ orias (ˆκ, ˆy)(·)e(˜κ, ˜y)(·). Ambas s˜ ao soluc¸˜ ao do problema de tempo ´ otimo (44) e satisfazem as condic¸˜ oes de otimalidade (45)-(49) com ˜ρ= 1. Proposi¸c˜ao 3.11. Se q(τ)≤0, ent˜ ao |ˆw(τ)| ≥ (c+α)/T0. Demonstrac¸˜ ao. Multiplicando (23) por ˆw(τ), obtemos (ˆ L(τ) + β)hˆg(τ) ˆw(τ), p(τ)i= (q(τ) + hˆg(τ) ˆw(τ), p(τ)i)h∇uˆ L(τ),ˆw(τ)i.(50) Uma vez que q(τ)≤0, por (24), temos hˆw(τ), p(τ)i>0. De (31), temos h∇uˆ L(τ),ˆw(τ)i=hˆg(τ) ˆw(τ), p(τ)i q(τ) + hˆg(τ) ˆw(τ), p(τ)i(ˆ L(τ) + β)≥ˆ L(τ) + β e, portanto, β≤ h∇uˆ L(τ),ˆw(τ)i− ˆ L(τ)≤σ(|ˆw(τ)|). Assim, obtemos |ˆw(τ)| ≥ σ−1(β) = σ−1σc+α T0=c+α T0 . 27 Proposi¸c˜ao 3.12. Se q(τ1)=0eq(τ)<0,τ∈]τ1, τ2], ent˜ ao |q(τ)|/|p(τ)| ≤ ¯γ,τ∈[τ1, τ2]. Demonstrac¸˜ ao. Uma vez que q(τ)<0,τ∈]τ1, τ2], temos q(τ) + hˆg(τ) ˆw(τ), p(τ)i |p(τ)|(ˆ L(τ) + β)≤cg|ˆw(τ)| θ(|ˆw(τ)|) + β≤cgη e |hˆgt(τ) ˆw(τ), p(τ)i| |p(τ)|(ˆ L(τ) + β)≤c∇g|ˆw(τ)| θ(|ˆw(τ)|) + β≤c∇gη. Das desigualdades anteriores, de (38) e da condic¸˜ ao (C3), temos  dq(τ) dτ ≤|hˆgt(τ) ˆw(τ), p(τ)i| ˆ L(τ) + β+(q(τ) + hˆg(τ) ˆw(τ), p(τ)i)|ˆ Lt(τ)| (ˆ L(τ) + β)2 ≤c∇gη|p(τ)|+cgη|p(τ)||ˆ Lt(τ)| ˆ L(τ) + β ≤(c∇g+cgξ)η|p(τ)|, sempre que τ∈[τ1, τ2]. De modo an´ alogo, temos  dp(τ) dτ ≤(c∇g+cgξ)η|p(τ)|. Daqui, obtemos d dτ |q(τ)| |p(τ)|≤|dq(τ)/dτ||p(τ)|+|q(τ)||dp(τ)/dτ| |p(τ)|2≤(c∇g+cgξ)η1 + |q(τ)| |p(τ)|. Uma vez que q(τ1) = 0, aplicando o Lema de Gronwall, temos |q(τ)| |p(τ)|≤e(c∇g+cgξ)η(τ2−τ1)−1.(51) Note-se que τ2−τ1=Zˆκ(τ2) ˆκ(τ1) (L(t, ˆx(t),ˆu(t)) + β)dt ≤c+ (ˆκ(τ2)−ˆκ(τ1))β, eˆκ(τ2)−ˆκ(τ1)≤T0. De facto, uma vez que q(τ)≤0no intervalo [τ1, τ2]et∈[ˆκ(τ1),ˆκ(τ2)], pela Proposic¸˜ ao 3.11. temos |ˆu(t)|=|ˆw(ˆτ(t))| ≥ c+α T0≥c+α. Assim, a desigualdade ˆκ(τ2)−ˆκ(τ1)> T0contradiz (14). Logo, τ2−τ1≤c+T0β. Combinando isto com as condic¸˜ oes (51) e (18), obtemos o resultado. 28 Teorema 3.13. Se gn˜ ao depende da vari´ avel x, ent˜ ao a desigualdade |ˆu(t)| ≤ `= max (r2 µ(Λ0+β) (1 + ¯γξ),Λ1+pΛ2 1+ 8µΛ0 2µ) verifica-se para quase todo t∈[0,1]. Demonstrac¸˜ ao. Se q(τ)≥0, ent˜ ao, de forma an´ aloga ` a demonstrac¸˜ ao do Teorema 3.8., temos |ˆw(τ)| ≤ max (r2 µ(Λ0+β),Λ1+pΛ2 1+ 8µΛ0 2µ).(52) Consideremos agora τ∈[0,ˆ T]tal que q(τ)<0. Multiplicando (41) por ˆw(τ), obtemos hˆg(τ) ˆw(τ), p(τ)i(ˆ L(τ) + β)=(q(τ) + hˆg(τ) ˆw(τ), p(τ)i)h∇uˆ L(τ),ˆw(τ)i. Usando a condic¸˜ ao (42), podemos reescrever esta igualdade como hˆg(τ) ˆw(τ), p(τ)i=hh∇uˆ L(τ),ˆw(τ)i. Combinando com (42), temos h=q(τ) + hh∇uˆ L(τ),ˆw(τ)i ˆ L(τ) + β. Da condic¸˜ ao (C2), obtemos q(τ) h=ˆ L(τ) + β−h∇uˆ L(τ),ˆw(τ)i ≤ Λ0−µ 2|ˆw(τ)|2+β. e, portanto, uma vez que, pela Proposic¸˜ ao 3.7., −q(τ)≤¯γ|p(τ)|, temos µ 2|ˆw(τ)|2≤Λ0+β−q(τ) h≤Λ0+β+¯γ|p(τ)| h. Pela igualdade (39) e pela condic¸˜ ao (C3), obtemos d|p(t)|/h dτ ≤1 h (q(τ) + hˆg(τ) ˆw(τ), p(τ)i)|∇xˆ L(τ)| (ˆ L(τ) + β)2=|∇xˆ L(τ)| ˆ L(τ) + β≤ξ e, uma vez que p(ˆ T) = 0, temos |p(t)|/h ≤ˆ Tξ. Para estimar ˆ T, consideremos ¯κ, uma soluc¸˜ ao do problema dκ dτ (τ) = 1 L(κ(τ),0,0) + β, κ(0) = 0 (53) 29 4 Problema de Rastreio Nesta secc¸˜ ao, estudaremos a complexidade do m´ etodo de ponto interior para o problema de rastreio regido pela equac¸˜ ao do calor. 4.1 Enunciado do problema Sejam ˇ θ∈V1,0 2(QT)∩L∞(QT,R)eϕ(θ) = |ˇ θ(t, x)−θ(t, x)|2. Consideremos Qj∈W2 2(Ω), j= 1, m,Kj>0,j= 1, m eθ0∈L2(Ω,R). Assumimos que Qjpode ser prolongado continuamente a Rnfazendo Qj(x) = 0, x /∈Ωe que θ0satisfaz a condic¸˜ ao de compatibilidade θ0(x) = 0, x ∈∂Ω. Fixemos 0< C ∈R. Consideraremos o problema de rastreio minimizar: J(θ) = ZZQT ϕ(θ(t, x))dxdt, (60) sujeito a: θt(t, x) = Cθxx(t, x) + m X j=1 Qj(x)qj(t), θ(t, x)=0,(t, x)∈[0, T]×∂Ω, θ(0, x) = θ0(x), qj(0) = 0,k˙qjkL∞((0,T),R)≤Kj, j = 1, m,                      (61) onde (θ, q1,··· , qm)pertence ao espac¸o V1,0 2(QT)×(AC([0, T],R))m. Seja Λa func¸˜ ao definida por Λ(t, x, q1,··· , qj) = Zt 0ZΩ Γ(t−τ, x −ξ) m X j=1 Qj(ξ)qj(τ)!dξdτ, (62) onde Γ(t, x) = 1 (4πCt)n/2exp −|x|2 4Ct. Ao longo da resoluc¸˜ ao deste problema, iremos considerar tamb´ em o problema auxiliar θ• t(t, x) = Cθ• xx(t, x), θ•(t, x) = −Λ(t, x, q1,··· , qj),(x, t)∈[0, T]×∂Ω, θ•(0, x) = θ0(x), qj(0) = 0,k˙qjkL∞((0,T),R)≤Kj, j = 1, m,                  (63) 36 4.2 Resultados Principais Vamos necessitar dos seguintes resultados no que se segue. Lema 4.1. Sejam (θ, q1,··· , qm)∈V1,0 2(QT)×(AC([0, T],R))mfunc¸˜ oes que satisfazem (63). Ent˜ ao, a desigualdade kθkL∞(QT,R)≤max   kθ0kL∞(Ω,R), T2     m X j=1 Qj˙qj    L∞(QT,R)    verifica-se. Demonstrac¸˜ ao. Usando o Teorema 2.9 e a desigualdade de Holder, temos |Λ(t, x, q1,··· , qj)|=Zt 0ZΩ Γ(t−τ, x −ξ) m X j=1 Qj(ξ)qj(τ)!dξdτ ≤Zt 0ZΩ Γ(t−τ, x −ξ)dξdτ     m X j=1 Qjqj    L∞(QT,R) ≤T     m X j=1 Qjqj    L∞(QT,R) ≤T2     m X j=1 Qj˙qj    L∞(QT,R) . Pelo Teorema 2.8, obtemos kθkL∞(QT,R)≤max{kθ0kL∞(Ω,R),kΛ(·,·, q1,··· , qj)kL∞(QT,R)}, o que completa a prova. Uma vez que, pelo Teorema anterior, as trajet´ orias admiss´ ıveis θdo problema (60), (61) pertencem a um conjunto limitado, Θ, definimos Kϕ= inf{`| |ϕ(θ1)−ϕ(θ2)| ≤ `|θ1−θ2|, θ1, θ2∈Θ}. Lema 4.2. Sejam (θ(l), q(l) 1,··· , q(l) m)∈V1,0 2(QT)×(AC([0, T],R))m,l∈ {1,2}, func¸˜ oes satisfazendo o problema (63). Ent˜ ao, a desigualdade |J(θ(1))−J(θ(2))| ≤ T3VΩKϕ     m X j=1 Qj˙q(1) j−˙q(2) j    L∞(QT,R) 37 verifica-se. Demonstrac¸˜ ao. Temos |J(θ(1))−J(θ(2))|=ZZQTϕ(θ(1)(t, x)) −ϕ(θ(2)(t, x))dxdt ≤ZZQT Kϕθ(1)(t, x)−θ(2)(t, x)dxdt ≤TVΩKϕkθ(1) −θ(2)kL∞(QT,R). Pelo Lema 4.1, obtemos kθ(1) −θ(2)kL∞(QT,R)≤T2     m X j=1 Qj˙q(1) j−˙q(2) j    L∞(QT,R) . Portanto, temos |J(θ(1))−J(θ(2))| ≤ T3VΩKϕ     m X j=1 Qj˙q(1) j−˙q(2) j    L∞(QT,R) . Teorema 4.3. O problema (60)-(61) tem uma soluc¸˜ ao. Demonstrac¸˜ ao. Seja `o´ ınfimo do problema (60)-(61) e (θl, ql 1,··· , ql m)func¸˜ oes que satisfazem (61) e tais que J(θl)→`. Usando a notac¸˜ ao Λl(·,·) = Λ(·,·, ql 1,··· , ql m)temos Λl t(t, x) = CΛl xx(t, x) + m X j=1 Qj(x)ql j(t), Λl(0, x) = 0.        (64) Logo, as func¸˜ oes (θl−Λl, ql 1,··· , ql m)satisfazem (63). Seja ηl= ( ˙ql 1,··· ,˙ql m). Uma vez que {ηl}´ e limitada em L2((0, T),Rm), existe uma subsucess˜ ao {ηlk}fracamente convergente em L2((0, T),Rm). Seja η0o limite fraco de {ηlk}. Pelo Teorema de Mazur, existe uma sucess˜ ao de combinac¸˜ oes convexas de {ηlk},ξp=PI(p) i=pλiηli, tal que ξp→η0em L2((0, T),Rm). Uma vez que o problema (63) ´ e linear, pelo Teorema 2.7, temos PI(p) i=pλi(θli−Λli)→θ0em V1,0 2(QT)⊆L2(QT,R)ePI(p) i=pλiqli→q0em L2((0, T),Rm). 38 Uma vez que (θ0, q0)verificam (63), tamb´ em (θ0+ Λ0, q0), onde Λ0(·,·) = Λ(·,·, q0 1,··· , q0 m), satisfazem (61). Portanto, uma vez que J´ e convexo, pelo Lema 4.2, obtemos J(θ0+ Λ0) = J lim p→∞ I(p) X i=p λi(θli−Λli)+Λ0  =J lim p→∞ I(p) X i=p λiθli+ lim p→∞ I(p) X i=p λi(−Λli+ Λ0)  =J lim p→∞ I(p) X i=p λiθli  = lim p→∞ J  I(p) X i=p λiθli  ≤lim p→∞ I(p) X i=p λiJ(θli) =`. Logo, (θ0+ Λ0, q0)´ e a soluc¸˜ ao de (60)-(61). No que se segue, denotamos por (ˆ θ, ˆq1,··· ,ˆqm)um processo ´ otimo do problema (60)-(61) no espac¸o V1,0 2(QT)×(AC([0, T],R))m. Consideremos HN, o espac¸o das func¸˜ oes lineares por partes η∈L2((0, T),R)cujas respetivas derivadas tomam valores ˙η(t) = ˙η(τk),t∈(τk, τ(k+ 1)],k= 0, N −1,τ=T/N. O problema (60)-(61) tamb´ em tem uma soluc¸˜ ao ´ otima no espac¸o V1,0 2(QT)×(HN)m. Isto segue da compacidade do conjunto de controlos e do Teorema 2.7. De seguida, vamos mostrar que a diferenc¸a entre J(ˆ θ)eJ(ˆ θ), onde (ˆ θ, ˆ q1,··· ,ˆ qm)´ e um processo ´ otimo do problema (60)-(61) no espac¸o V1,0 2(QT)×(HN)m, pode ser feita arbitrariamente pequena quando N´ e suficientemente grande. Consideremos as func¸˜ oes qj(t),j= 1, m definidas por ˜qj(0) = 0, e ˜qj(t) = ˜qj(kτ) + t−kτ τZ(k+1)τ kτ ˙ ˆqj(s)ds, 39 j= 1, m, t ∈(kτ, (k−1)τ], τ =T N, k = 0, N −1. Obviamente, estas func¸˜ oes s˜ ao lineares por partes, continuas e satisfazem a condic¸˜ ao |˙ ˜qj(t)| ≤ Kj,t∈[0, T],j= 1, m. A func¸˜ ao Pm j=1 Qj˜qjaproxima-se da func¸˜ ao Pm j=1 Qjˆqjno sentido seguinte. Lema 4.4. A desigualdade      m X j=1 Qj(˜qj−ˆqj)    L∞(QT,R)≤τ m X j=1 kQjkL∞(Ω,R)Kj(65) verifica-se. Demonstrac¸˜ ao. Por induc¸˜ ao, temos m X j=1 Qj(x)˜qj((k+ 1)τ) = m X j=1 Qj(x)˜qj(kτ) + m X j=1 Qj(x)Z(k+1)τ kτ ˙ ˆqj(s)ds = m X j=1 Qj(x)ˆqj(kτ) + m X j=1 Qj(x)Z(k+1)τ kτ ˙ ˆqj(s)ds = m X j=1 Qj(x)ˆqj((k+ 1)τ) e, portanto, m X j=1 Qj(x)˜qj(kτ) = m X j=1 Qj(x)ˆqj(kτ), k =0, N. (66) Vejamos que, para todo t∈(kτ, (k+ 1)τ], se tem m X j=1 Qj(x)˜qj(t) = m X j=1 Qj(x)˜qj(kτ) + t−kτ τ m X j=1 Qj(x)Z(k+1)τ kτ ˙ ˆqj(s)ds = m X j=1 Qj(x)˜qj((k+ 1)τ) + t−(k+ 1)τ τ m X j=1 Qj(x)Z(k+1)τ kτ ˙ ˆqj(s)ds. 40 Se t∈(kτ, (k+1 2)τ], ent˜ ao obtemos  m X j=1 Qj(x)(˜qj(t)−ˆqj(t)) = t−kτ τ m X j=1 Qj(x)Z(k+1)τ kτ ˙ ˆqj(s)ds − m X j=1 Qj(x)Zt kτ ˙ ˆqj(s)ds ≤t−kτ τ m X j=1 Qj(x)Z(k+1)τ kτ ˙ ˆqj(s)ds + m X j=1 Qj(x)Zt kτ ˙ ˆqj(s)ds ≤1 2 m X j=1 |Qj(x)|Z(k+1)τ kτ  ˙ ˆqj(s)ds + m X j=1 |Qj(x)|Zt kτ  ˙ ˆqj(s)ds ≤τ 2 m X j=1 |Qj(x)|Kj+τ 2 m X j=1 |Qj(x)|Kj =τ m X j=1 |Qj(x)|Kj e, se t∈((k+1 2)τ, (k+ 1)τ], obtemos  m X j=1 Qj(x)(˜qj(t)−ˆqj(t)) = t−(k+ 1)τ τ m X j=1 Qj(x)Z(k+1)τ kτ ˙ ˆqj(s)ds − m X j=1 Qj(x)Z(k+1)τ t ˙ ˆqj(s)ds ≤(k+ 1)τ−t τ m X j=1 Qj(x)Z(k+1)τ kτ ˙ ˆqj(s)ds + m X j=1 Qj(x)Zτ(k+1) t ˙ ˆqj(s)ds ≤τ 2 m X j=1 |Qj(x)|Kj+τ 2 m X j=1 |Qj(x)|Kj =τ m X j=1 |Qj(x)|Kj. Logo, temos (65). Usando o princ´ ıpio de m´ aximo (Teorema 2.8.) vamos encontrar uma estimativa para a diferenc¸a entre a soluc¸˜ ao ´ otima do problema (60)-(61) nos espac¸os V1,0 2(QT)×(AC([0, T],R))m eV1,0 2(QT)×(HN)m. 41 Recordemos que, se (θ, q1,··· , qm)satisfaz (61), ent˜ ao (θ−Λ, q1,··· , qm)satisfaz (63), onde Λ(·,·) = Λ(·,·, q1,··· , qm). Usaremos a notac¸˜ ao ˜ Λ(·,·) = Λ(·,·,˜q1,··· ,˜qm)eˆ Λ(·,·) = Λ(·,·,ˆq1,··· ,ˆqm). Lema 4.5. Sejam ˜qjas func¸˜ oes definidas acima e ˜ θuma func¸˜ ao tal que (˜ θ, ˜q1,··· ,˜qm)satisfaz (63). Ent˜ ao, a desigualdade    ˜ θ+˜ Λ−ˆ θ  L∞(QT,R)≤2T2 m X j=1 kQjkL∞(Ω,R)Kj!/N. verifica-se. Demonstrac¸˜ ao. Seja δθ =˜ θ−ˆ θ+ˆ Λ. A func¸˜ ao δθ verifica as condic¸˜ oes (δθ)t=C(δθ)xx, δθ(t, x) = ˆ Λ(t, x)−˜ Λ(t, x),(t, x)∈[0, T]×∂Ω, δθ(0, x) = 0.            (67) Pelos Teoremas 2.8, 2.9 e pelo Lema 4.4, temos, kδθkL∞(QT,R)≤   ˆ Λ−˜ Λ  L∞(QT,R) ≤T     m X j=1 Qj(˜qj−ˆqj)    L∞(QT,R) ≤T2 N m X j=1 kQjkL∞(Ω,R)Kj. Portanto, obtemos    ˜ θ+˜ Λ−ˆ θ  L∞(QT,R)≤   ˜ θ−ˆ θ+ˆ Λ  L∞(QT,R)+   ˜ Λ−ˆ Λ  L∞(QT,R) ≤2T2 N m X j=1 kQjkL∞(Ω,R)Kj. 42 Teorema 4.6. Seja (ˆ θ, ˆq1,··· ,ˆqm)um processo ´ otimo do problema (60)-(61) no espac¸o V1,0 2(QT)×(AC([0, T],R))me(ˆ θ, ˆ q1,··· ,ˆ qm)um processo ´ otimo no espac¸o V1,0 2(QT)×(HN)m. Ent˜ ao, J(ˆ θ)−J(ˆ θ)≤2T3 NVΩKϕ m X j=1 kQjkL∞(Ω,R)Kj, onde VΩ=RΩdx. Demonstrac¸˜ ao. Sejam ˜qjas func¸˜ oes definidas acima e ˜ θuma func¸˜ ao tal que (˜ θ, ˜q1,··· ,˜qm) satisfaz (63). Assim como na prova do Lema 4.2., obtemos J(˜ θ+˜ Λ) −J(ˆ θ)=ZZQTϕ(˜ θ+˜ Λ) −ϕ(ˆ θ)dxdt ≤TVΩKϕk˜ θ+˜ Λ−ˆ θkL∞(QT,R). Pelo Lema 4.5., temos J(˜ θ+˜ Λ) −J(ˆ θ)≤TVΩKϕk˜ θ+˜ Λ−ˆ θkL∞(QT,R) ≤2T3 N VΩKϕ m X j=1 kQjkL∞(Ω,R)Kj!. Assim, uma vez que J(ˆ θ)≤J(ˆ θ)≤J(˜ θ+˜ Λ), temos J(ˆ θ)−J(˜ θ)≤2T3 N VΩKϕ m X j=1 kQjkL∞(Ω,R)Kj!. Seja F(θ, σ) = −ln(σ−J(θ)) −ln(σ−σ)− m X i=1 N−1 X k=0 ln(Ki−(˙ qi(τk))2),(68) onde σ= max{J(θ)|(θ, q1,··· , qm)∈V1,0 2(QT)×(HN)msatisfaz (61)}. 43 Seja ε > 0, N > 4VΩKϕPm j=1 kQjkL∞(Ω,R)KjT3 ε,(69) e N ≥ ln 2(1 + β)(Nm + 1) + (β+√Nm + 1)β γ(1 −2β)εkbkF (˜x,˜σ) ln 1 + γ β+√Nm + 1+ 1,(70) onde b= (0,1). Teorema 4.7. O M´ etodo de Ponto Interior encontra (q1,··· , qm)∈(HN)mtal que |J(θ−Λ) −J(ˆ θ)| ≤ ε, onde (θ, q1,··· , qm)satisfaz (63) e Λ(·,·) = Λ(·,·, q1,··· , qm), em, no m´ aximo, Niterac¸˜ oes. Demonstrac¸˜ ao. Seja N > 4VΩKϕPm j=1 kQjkL∞(Ω,R)KjT3 ε. Pelo Teorema 4.6, temos |J(ˆ θ)−J(ˆ θ)|< ε/2. Usando o M´ etodo de Ponto Interior, encontramos (q1,··· , qm)tal que |J(θ−Λ) −J(ˆ θ)| ≤ ε/2, onde (θ, q1,··· , qm)satisfaz (63). O n´ umero de iterac¸˜ oes necess´ arias ´ e dado pelo Teorema 2.10. Assim, temos |J(θ−Λ) −J(ˆ θ)|≤|J(θ−Λ) −J(ˆ θ)|+|J(ˆ θ)−J(ˆ θ)|<ε 2+ε 2=ε. 44 5 Conclus˜oes e Trabalho Futuro O m´ etodo utilizado no cap´ ıtulo 3 deste trabalho levou-nos ` a obtenc¸˜ ao de estimativas expl´ ıcitas para a constante de Lipschitz da soluc¸˜ ao de dois problemas de Lagrange particulares. Atrav´ es de um exemplo, pudemos verificar que estas estimativas s˜ ao de ´ otima qualidade, atingindo mesmo o valor real em alguns casos espec´ ıficos. Constatamos ainda que, o m´ etodo num´ erico aplicado garante-nos uma excelente aproximac¸˜ ao (finita) da soluc¸˜ ao real, ap´ os um n´ umero de iterac¸˜ oes que pode ser estimado a priori, utilizando apenas os dados do problema. No cap´ ıtulo 4, obtivemos um majorante para a complexidade do M´ etodo de Ponto Interior aplicado ao problema de rastreio regido pela equac¸˜ ao do calor. Para isso, constru´ ımos uma aproximac¸˜ ao adequada da soluc¸˜ ao real, atrav´ es do uso do princ´ ıpio de m´ aximo (Teorema 2.8.) e da func¸˜ ao Γ. Este problema admite uma resoluc¸˜ ao eficaz com recurso a este m´ etodo. Futuramente, seria interessante procurar classes de problemas onde as estimativas encontradas possam ser melhoradas. Num outro sentido, talvez at´ e mais interessante, est´ a a busca por alargar estas estimativas a classes de problemas mais gerais. O conhecimento de uma estimativa para a constante de Lipschitz da soluc¸˜ ao de um problema de otimizac¸˜ ao pode tamb´ em levar-nos ` a obtenc¸˜ ao de um m´ etodo de otimizac¸˜ ao para problemas de dimens˜ ao infinita, atrav´ es da aproximac¸˜ ao da soluc¸˜ ao ´ otima por func¸˜ oes de classe C1. No que toca ao problema de rastreio, um caminho futuro ser´ a a generalizac¸˜ ao dos resultados encontrados para um problema regido por uma equac¸˜ ao parab´ olica mais geral. 45