State of the Art
2.2 Simulation-based design
[x, y]⊂ X . Suponha que D+f (·; y−x) seja finita e semicontínua superior sobre ]x, y[.Suponha
também que f◦
+(y−x)(x; y− x) e f◦−(y−x)(x; y− x) são finitas. Se f é duas vezes
C-diferenciável sobre ]x, y[, o gradiente generalizado de Clarke ∂f(x) é não vazio e f◦(x; y− x) = max x∗∈∂f (x)x ∗, y− x , então existe t 0 ∈ (0, 1) tal que f (y)∈ f(x) + ∂f(x), y − x + 1 2∂ 2f (x + t 0(y− x))(y − x), y − x,
sendo que o fecho acima é desnecessário caso f ∈ C1,1 sobre ]x, y[.
Os resultados apresentado neste capítulo, são muito interessantes tanto do ponto de vista da análise não suave quanto da otimização.
Ainda hoje existem pesquisadores trabalhando para obter novos conceitos de derivadas di- recionais de segunda ordem generalizadas e condições para otimalidade, como o que foi feito em [3]. Entretanto, tendo em mãos as condições de otimalidade que foram sendo construidas durante esses anos, é muito natural indagar-se qual Teorema fornecendo essas condições atinge uma classe maior de problemas de otimização, utilizando os conceitos da análise não suave. É muito complicado responder essa pergunta, até mesmo porque, uma abordagem dificilmente se sobressairá sobre as outras em todos os aspectos, uma sempre leva algum tipo de vantagem em relação a outra, por exemplo o cálculo das subdiferenciais de um problema pode ser mais fácil com determinada abordagem do que o cálculo com a outra e vice-versa. O melhor seria conseguir de alguma maneira tentar unificar esses Teoremas de modo que um sane a deficiência do outro.
Em 2009 K. Pastor publicou o trabalho [9] que traz exatamente essa ideia. O autor compara as condições suficiente de segunda ordem para otimalidade de problemas sem restrições, que aparecem em [1] e [2] e depois apresenta um resultado que unifica essas condições. Vamos tentar expor de maneira clara o que foi feito em [9] e para isso, faremos uma apresentação de alguns conceitos e resultados que nos permita demonstrar a condição suficiente dada em [1] e depois faremos o mesmo com [2]. Finalizaremos este capítulo ex- pondo o Teorema que é considerado uma unificação dessas duas condições suficientes.
5.2
Alguns resultados e conceitos dados em [1].
Definição 5.2.1. (Jacobiana Aproximada) A aplicação F :Rn→ Rm admite uma jaco-
5.2 Alguns resultados e conceitos dados em [1]. 155 para cada v ∈ Rm (5.1) D+(vF )(x, u) = lim inf t↓0 (vF )(x + tu)− (vF )(x) t ≤M ∈∂sup∗F (x)Mv, u ,
para qualquer u ∈ Rn. Equivalentemente à
(5.2) D+(vF )(x, u) = lim sup
t↓0
(vF )(x + tu)− (vF )(x)
t ≥M ∈∂inf∗F (x)Mv, u ,
para qualquer u ∈ Rn.
Observação: A notação vF significa m
i=1
vifi, sendo fi as funções coordenadas da função
F. Se m = 1 então, a desigualdade (5.1) (ou 5.2) é equivalente à (5.3) D+F (x, u)≤ sup x∗∈∂∗F (x)x ∗, u D+F (x, u) ≥ inf x∗∈∂∗F (x)x ∗, u
Note também que quando m = 1, a condição (5.3) é equivalente à D+(αF )(x, u)≤ sup
x∗∂∗F (x)αx
∗, u , (5.4)
para cada α ∈ R e para qualquer u ∈ Rn. Similarmente, a condição (5.3) é equivalente à
D+(αF )(x, u)≥ inf
x∗∂∗F (x)αx
∗, u
, (5.5) para cada α ∈ R e para qualquer u ∈ Rn.
Proposição 5.2.1. Suponha que F : Rn → Rm seja Lipschitz em uma vizinhança de
x ∈ Rn. Então, a jacobiana generalizada de Clarke ¯∂F (x) é uma jacobiana aproximada
de F em x.
Demonstração. Para cada v ∈ Rm temos que
(5.6) ∂(vF )(x)¯ ⊂ ¯∂F (x)v, consequentemente, para cada u ∈ Rn
(vF )◦(x, u) = max
ξ∈ ¯∂(vF )(x)ξ, u ≤ maxM ∈ ¯∂F (x)M · v, u
5.2 Alguns resultados e conceitos dados em [1]. 156
para cada u ∈ Rn vale
D+(vF )(x, u)≤ (vF )◦(x, u) = max
M ∈ ¯∂F (¯x)Mv, u ,
segue que ¯∂F (x) é uma jacobiana aproximada de F em x.
Proposição 5.2.2. (Teorema 3.1 em [1]) Seja a, b ∈ Rn e F : Rn → Rm uma função
contínua. Suponha que para cada x ∈ [a, b], ∂∗F (x) seja uma jacobiana aproximada de F
em x. Então,
F (b)− F (a) ∈ co (∂∗F ([a, b])(b− a))
Demonstração. Note que o lado direito acima é a envoltória convexa de todo os pontos do tipo M(b − a), sendo M ∈ ∂∗F (ξ), para algum ξ ∈ [a, b]. Fixe v ∈ Rm de modo arbitrário
e tome a função g : [0, 1] → R da seguinte forma
g(t) =v, F (a + t(b − a)) − F (a) + t(F (a) − F (b)) .
Uma vez que g é contínua em [0, 1] que é compacto, segue que g atinge seu valor máximo ou mínimo em algum t0 ∈ (0, 1). Suponha que t0 seja o minimizador de g. Então, para
cada α ∈ R, temos que D+g(t0, α)≥ 0 pois g(t0+ kα)− g(t0)≥ 0, para qualquer k ∈ R,
logo, em particular, para qualquer k > 0 temos que g(t0+kα)−g(t0)
k ≥ 0, para qualquer
α∈ R. Então, para cada α ∈ R segue que D+g(t0, α) = lim inf
k↓0
g(t0+ kα)− g(t0)
k ≥ 0.
Uma vez que
g(t0+ kα)− g(t0) =
=v, F (a + (t0+ kα)(b− a)) − F (a) + (t0+ kα)(F (a)− F (b)) +
− v, F (a + t0(b− a))F (a) − t0(F (a)− F (b)) =
=v, F (a + (t0+ kα)(b− a)) + kα(F (a) − F (b)) , então lim inf k↓0 g(t0+kα)−g(t0) k = = lim inf k↓0
v, F(a + (t0 + kα)(b− a)) + kα(F (a) − F (b))
k
=
5.2 Alguns resultados e conceitos dados em [1]. 157 = lim inf k↓0 v, F(a + (t0+ kα)(b− a))) k + αv, F (a) − F (b) = = lim inf k↓0 v, F(a + (t0+ kα)(b− a)) k + αv, F (a) − F (b) = = D+(vF ) (a + t0(b− a); α(b − a)) + α v, F (a) − F (b) ,
ou seja,
D+g(t0, α) = D+(vF ) (a + t0(b− a); α(b − a)) + α v, F (a) − F (b) ≥ 0,
logo, para cada α ∈ R temos
D+(vF ) (a + t0(b− a); α(b − a)) ≥ α v, F (b) − F (a) .
Tome α = 1. Desse modo,
D+(vF ) (a + t0(b− a), (b − a)) ≥ v, F (b) − F (a) ,
agora tomando α = −1 temos que
D+(vF ) (a + t0(b− a), a − b) ≥ −1 v, F (b) − F (a)
o que implica
−D+(vF ) (a + t0(b− a), a − b) ≤ v, F (b) − F (a) ,
logo, de α = 1 e α = −1 temos
−D+(vF ) (a + t0(b− a), a − b) ≤ v, F (b) − F (a) ≤ D+(vF ) (a + t0(b− a), b − a)
De (5.1) temos que
v, F (b) − F (a) ≤ sup
M ∈∂∗F (a+t0(b−a))Mv, b − a .
Por outro lado,
−D+(vF ) (a + t0(b− a), a − b) ≥ − sup
M ∈∂∗F (a+t0(b−a))Mv; −(b − a) =
= inf
M ∈∂∗F (a+t0(b−a))Mv, b − a
portanto, de (5.1) temos que inf
M ∈∂∗F (a+t0(b−a))Mv, b − a ≤ v, F (b) − F (a) ≤ sup
5.2 Alguns resultados e conceitos dados em [1]. 158
então
v, F (b) − F (a) =M v, b˜ − a∈ ¯co (∂∗F (a + t0(b− a))v) (b − a)
e portanto,
v, F (b) − F (a) ∈ co (∂∗F ([a, b])· v) (b − a) (5.7) Uma vez que (5.7) é válida para cada v ∈ Rn dado, afirmamos que
F (b)− F (a) ∈ co (∂∗F ([a, b])(b− a)) ,
pois caso contrário, já que ¯co (∂∗F ([a, b])(b− a)) é um subconjunto fechado e convexo do
Rm, temos pelo Teorema da Separação que existe p∈ Rm tal que
p, F (b) − F (a) − ǫ > sup
u∈ ¯co(∂∗F ([a,b])(b−a))p, u
isto implica que
p, F (b) − F (a) > sup {α : α ∈ ¯co ((∂∗F ([a, b])· p)(b − a))}
o que contradiz (5.7). Similarmente, se t0 for um maximizador de g, então, D+g(t, α)≤ 0
para cada α ∈ Rn dado. Utilizando a mesma linha dos argumentos acima, chegamos a
mesma conclusão, desse modo, completamos esta demonstração.
Definição 5.2.2. Dizemos que a multifunção G :Rn⇒L(Rn,Rm) é localmente limitada
em x ∈ Rn se existe uma vizinhança U de x e um α > 0 tal que A < α para cada
A ∈ G(U).
Definição 5.2.3. a multifunção G : Rn ⇒ L(Rn,Rm) é dita ser semicontínua superior
em x se, para cada conjunto aberto V contendo G(x) existe uma vizinhança U de x tal que G(U) ⊂ V.
Observação 5.2.1. Claramente se a multifunção G é semicontínua superior em x e se G(x) é um conjunto limitado, então, G(x) é localmente limitado em x.
Proposição 5.2.3. (Teorema 3.5 em [1]) Seja F : Rn → Rm contínua. Então, F tem
uma aplicação jacobiana aproximada ∂∗F em uma vizinhança de x com ∂∗F limitado
sobre essa vizinhança, se e somente se, F é Lipschitz em alguma vizinhança de x.
Demonstração. Suponha que ∂∗F (y) é uma jacobiana aproximada de F em cada y que
esteja na vizinhança U de x na qual ∂∗F é limitada. Sem perda de generalidade, podemos
supor que U é convexa. Uma vez que ∂∗F é limitada sobre U, existe α > 0 tal que
5.2 Alguns resultados e conceitos dados em [1]. 159
Fixe de modo arbitrário x, y ∈ U. Como U é convexo, então, [x, y] ∈ U e da Proposição 5.2.2 temos que
F (y)− F (x) ∈ co (∂∗F ([x, y])· (y − x)) ⊂ co (∂∗F (U )· (y − x)) , portanto
F (y) − F (x) ≤ y − x · max { A : A ∈ ∂∗F (U )} ,
consequentemente F (y) − F (x) ≤ α y − x , e uma vez que x, y foram escolhidos em U de modo arbitrário, seque que F é Lipschitz em U.
Reciprocamente, se F é Lipschitz em uma vizinhança U de x então, F : U ⊂ Rn → Rm
é Lipschitz. Da Proposição 5.2.1 a jacobiana generalizada de Clarke é uma jacobiana aproximada de F em x, a qual é localmente limitada em x.
Observação 5.2.2. Dizemos que f :Rn → R é uma função C1 quando f é continuamente
Gâteaux diferenciável.
Definição 5.2.4. Seja f :Rn → R uma função C1. Dizemos que f admite uma hessiana
aproximada ∂2
∗f (x) em x se o conjunto ∂∗f (x) é uma jacobiana aproximada de∇f em x.
Vale lembrar que a jacobiana ∇f da função f : Rn → R é uma função
∇f : Rn → Rn. Vamos denotar a jacobina aproximada da função ∇f : Rn → Rn por
∂2
∗f (x) = ∂∗∇f(x). Se M ∈ ∂∗2f (x) dizemos que M é uma matriz hessiana aproximada de
f em x. Claramente, se f é duas vezes diferenciável então,∇2f (x) é uma matriz hessiana
simétrica aproximada de f em x.
Proposição 5.2.4. Sejam f :Rn→ R uma função C1 sobre o Rn e x, y ∈ Rn. Suponha
que para cada z ∈ [x, y], ∂2
∗f (z) é uma Hessiana aproximada de f em z. Então,
∇f(y) − ∇f(x) ∈ co∂∗2f ([x, y])· (y − x). Demonstração. Uma vez que f : Rn → R é uma função C1 sendo ∂2
∗f (z) uma Hessiana
aproximada de f em z para cada z ∈ [x, y] segue que ∇f : Rn → Rn é uma função
contínua tal que para cada z ∈ [x, y], ∂2
∗f (z) é uma jacobiana aproximada de ∇f em z.
Portanto, da Proposição 5.2.2 segue que
∇f(y) − ∇f(x) ∈ co∂∗2f ([x, y])· (y − x)
5.2 Alguns resultados e conceitos dados em [1]. 160
Proposição 5.2.5. (Proposição 5.2 em [1]) Seja f :Rn→ R uma função C1 sobre o Rn.
Então, f possui uma aplicação Hessiana aproximada ∂2
∗f em uma vizinhança de x com
∂2
∗f limitado nessa vizinhança, e somente se, f é C1,1 em alguma vizinhança de x.
Demonstração. Considere que f seja uma função C1. Vamos supor que f possui uma
aplicação Hessiana aproximada em uma vizinhança de x com ∂2
∗f limitada sobre essa
vizinhança. Então, ∇f : Rn → Rn é uma aplicação contínua sendo que ∂2
∗f é uma
jacobiana aproximada de ∇f em uma vizinhança de x, com ∂2
∗f limitada sobre essa
vizinhança. Portanto, da Proposição 5.2.3 segue que ∇f é localmente Lipschitz, assim garantimos que f é C1,1 em x.
Reciprocamente, considerando que f : Rn → R é uma função C1, vamos supor que f é C1,1
em x, logo, f é contínua com ∇f : Rn→ Rn contínua e Lipschitz em alguma vizinhança
de x. Então, da Proposição 5.2.3 temos que ∇f possui uma jacobiana aproximada ∂2 ∗f
em uma vizinhança de x, sendo ∂2
∗f limitada sobre essa vizinhança, consequentemente f
possui uma Hessiana aproximada ∂2
∗f em uma vizinhança de x, com ∂∗2f limitada sobre
essa vizinhança.
Proposição 5.2.6. (Teorema 6.1 em [1]) Sejam f : Rn → R uma função C1 sobre
Rn ∈ x, y ∈ Rn. Suponha que para cada z ∈ [x, y], ∂2
∗f (z) é uma Hessiana aproximada de
f em z. Então, existe ξ ∈]x, y[ tal que f (y)∈ f (x) +∇f(x), y − x +1 2co ∂∗2f (ξ)· (x − y), (y − x)
Demonstração. Seja h : [0, 1] → R dada por
h(t) = f (y + t(x− y)) + t ∇f(y + t(x − y)), y − x + 1 2at
2− f(y),
Sendo a = −2 (f(x) − f(y) + ∇f(x), y − x) . Aqui, por conveniência de notação vamos denotar a derivada direcional de (vF ) em w na direção u por ∇f(w), vw .
Como h(0) = 0 e
h(1) = f (x) +∇f(x), y − x − (f(x) − f(y) + ∇f(x), y − x) − f(y) = = f (x) +∇f(x), y − x − f(x) + f(y) − ∇f(x), y − x − f(y) = 0
Além disso, já que f é C1, então, h é contínua sobre [0, 1]. Logo, h atinge seu valor
extremo em algum ponto γ ∈ (0, 1). Suponha γ seja um maximizador de h. Então, para qualquer v ∈ R e λ > 0 suficientemente pequeno, h(γ +λv)−h(γ) ≤ 0, consequentemente, D+h(γ, v) = lim sup
λ↓0
h(γ+λv)−h(γ)
5.2 Alguns resultados e conceitos dados em [1]. 161
Observe que
h(γ+λv) = f (y + (γ + (λv)(x− y))+(γ+tv) ∇f(y + (γ + (λv)(x − y), y − x+1
2a(γ+λv)
2
e h(γ) = f(y + γ(x − y)) + γ ∇f(y + γ(x − y)), y − x + 1 2aγ
2
logo,
h(γ + λv)− h(γ) = f(y + (γ + λv)(x − y)) − f(y + γ(x − y))+ +(γ + λv)∇f(y + (γ + λv)(x − y), y − x) − γ ∇f(y + γ(x − y)), y − x +
+a(γ + λv)
2− aγ2
2 .
Uma vez que f é C1 e a função g(γ) = a · γ, para qualquer γ ∈]0, 1[ são deriváveis, temos
que 0≥ D+h(γ, v) = lim sup λ↓0 h(γ + λv)− h(γ) λ = lim λ↓0 f (y + (γ + λv)(x− y)) − f (y + γ(x − y)) λ + 1 2limλ↓0 a(γ + λv)2− aγ2 λ + + lim sup λ↓0
(γ + λv)∇f(y + (γ + λv)(x − y)), y − x − γ ∇f(y + γ(x − y), y − x
λ =
= lim
λ↓0
f (y + γ(x− y) + λv(x − y)) − f(y + γ(x − y))
λ + 1 2limλ↓0 a· 2 · λ · γv + a · λ2· v2 λ + + lim sup λ↓0 {
γ∇f(y + (γ + λv)(x − y)), y − x − γ ∇f(y + γ(x − y), y − x)
λ +
+λv∇f(y + (γ + λv)(x − y)), y − x
λ } =
=∇f(y + γ(x − y)), v(x − y) + a · γ · v + v ∇f(y + γ(x − y), y − x) + +γ lim sup
λ↓0
∇f(y + (γ + λv)(x − y)), y − x − ∇f(y + γ(x − y), y − x
λ =
= a· γ · v + γ lim sup
λ↓0
∇f(y + γ(x − y) + λv(x − y)), y − x − ∇f(y + γ(x − y)), y − x
λ .
Tome ξ = y + γ(x − y). Logo, ξ ∈]x, y[ e para v = −1 temos 0≥ −aγ + γ lim sup
λ↓0
∇f(y + γ(x − y) + λ(y − x)), y − x − ∇f(y + γ(x − y)), y − x)
λ ,
logo 0≥ −a + inf
M ∈∂2 ∗f (ξ) M(y − x), y − x , ou seja, a≥ inf M ∈∂2 ∗f (ξ) M(y − x), y − x .
5.2 Alguns resultados e conceitos dados em [1]. 162
Por outro lado, se v = 1 temos que 0≥ aγ + γ lim sup
λ↓0
∇f(y + γ(x − y) + λ(x − y)), y − x − ∇f(y + γ(x − y)), y − x
λ ,
ou seja,
0≥ a + lim sup
λ↓0
∇f(y + γ(x − y) + λ(x − y)), y − x − ∇f(y + γ(x − y)), y − x λ
logo
−a ≥ lim sup
λ↓0
∇f(y + γ(x − y) + λ(x − y)), y − x − ∇f(y + γ(x − y)), y − x
λ ≥ ≥ inf M ∈∂2 ∗f (ξ) M(y − x), x − y , consequentemente a≤ − inf M ∈∂2 ∗f (ξ) [− M(y − x), y − x] = sup M ∈∂2 ∗f (ξ) M(y − x), y − x . Portanto, temos que
inf M ∈∂2 ∗f (ξ) M(y − x), y − x ≤ a ≤ sup M ∈∂2 ∗f (ξ) M(y − x), y − x , desse modo, a∈ co ∂∗2f (ξ)(y− x), y − x . Como a
2 = f (x)− f(y) − ∇f(x), y − x , segue que
f (y)− f(x) − ∇f(x), y − x ∈ 1 2co ∂∗2f (ξ)(y− x), y − x , então f (y)∈ f (x) +∇f(x), y − x + 1 2co ∂∗2f (ξ)(y− x), y − x .
O caso em que γ é um mínimo está feito em [1], assim concluímos a demonstração.
Teorema 5.2.1. (Teorema 7.6 em [1]) Seja f : Rn → R uma função C1 sobre Rn e
¯
x ∈ Rn. Suponha que para cada x em uma vizinhança de ¯x, ∂2
∗f (x) seja uma Hessiana
aproximada de f em x com ∂2
∗f limitada nessa vizinhança. Se ∇f(¯x) = 0 e para cada
0 < α < 1 e cada h∈ Rn\{0} tem-se que
(∗) ∀M ∈ ¯co∂∗2f (¯x + αh),Mh, h > 0, então, ¯x é um minimizador local estrito de f.
5.2 Alguns resultados e conceitos dados em [1]. 163
uma sequência {xn} ⊂ Rn com xn = ¯x para todo n ∈ N e xn→ ¯x quando n → ∞ tal que
f (xn)≤ f(¯x) para cada n ∈ N.
Para cada n ∈ N, tome xn= ¯x + hn, sendo hn = 0 para cada n ∈ N. Da Proposição 5.2.6
existe 0 < αn < 1 tal que
f (xn)∈ f (¯x) +∇f(¯x), xn− ¯x + 1 2co ∂∗2f (¯x + αn· hn)(hn), hn
mas por hipótese ∇f(¯x) = 0. Logo, f (xn)∈ f (¯x) + 1 2co¯ ∂∗2f (¯x + αn· hn)(hn), hn . Portanto, existe Mn∈ ∂∗2f (¯x + αn· hn) tal que
f (xn) = f (¯x) +
1
2Mn· hn, hn , ou seja,
Mn· hn, hn ≤ 0,
contradizendo (∗). Portanto, ¯x é um minimizador local estrito de f.
Note que: Uma vez que foi dado o Conceito de Jacobiana aproximada de uma função f :Rn → R em um ponto x ∈ Rn via derivadas direcionais de Dini, inferior de primeira
ordem como vimos em (2.1), segue de maneira natural, sendo a derivada direcional de Dini inferior de segunda ordem de f em x na direção (u, v) ∈ Rn× Rn dada por
D+f (x, u, v) = lim inf t↓0 f′(x + tu; v)− f′(x, v) t , sendo f′(x, h) = lim t↓0 f (x+th)−f (x)
t a derivada direcional de f em x na direção h, que ∂ 2 ∗f (x)
é uma Hessiana aproximada de f em ¯x se ∂2
∗f (x) ⊂ L (Rn,L(Rn× R)) é um conjunto
fechado e
D+f (x, u, v)≤ sup M ∈∂2
∗f (x)
Mv, v para qualquer (u, v) ∈ Rn× Rn.