3. METODE, DATA, KILDER OG GJENNOMFØRBARHET
3.1 Valg av metode
Para a descri¸c˜ao dos principais aspectos dos m´etodos de descida ser´a considerado o se- guinte problema irrestrito em n vari´aveis
minimizar f (x) onde f : Rn→ R (4.26)
x ∈ Rn
Como o pr´oprio nome diz, os m´etodos de descida consistem em, dada uma aproxima¸c˜ao xk da solu¸c˜ao do problema 4.26, encontrar uma dire¸c˜ao dk tal que f seja descrescente
(pelo menos para pequenos passos) e a partir de xkcaminharna regi˜ao de descrescimento,
o tamanho do passo αk> 0. Os valores dk e αk devem satisfazer a seguinte desigualdade
f (xk+ αkdk) < f (xk). (4.27)
Assim, o iterando seguinte ´e obtido atrav´es da seguinte f´ormula
xk+1 = xk+ αkdk (4.28)
Brand˜ao (2010) realiza, em sua disserta¸c˜ao de mestrado, um estudo te´orico anal´ıtico e experimental de um m´etodo de descida. Lobato (2008) descreve sobre um m´etodo de descida e apresenta uma descri¸c˜ao anal´ıtica e gr´afica das condi¸c˜oes de otimalidade, denominada condi¸c˜oes de Karush-Kuhn-Tucker(KKT), para um problema com restri¸c˜oes de igualdade.
Para descrever sobre m´etodos de descida ´e necess´ario primeiramente saber o que signi- fica dire¸c˜ao de descida para, depois, saber como calcular o tamanho do passo na dire¸c˜ao des descida. A seguir ´e apresentada a defini¸c˜ao de dire¸c˜ao de descida (IZMAILOV;SOLODOV,
2007; LOBATO, 2008; BRAND ˜AO,2010).
Definic¸˜ao 4.7. Diz-se qued ∈ Rn ´e uma direc¸˜ao de descida da func¸˜aof : Rn → R no ponto
x ∈ Rn, se existe umǫ > 0 tal que
f (x + td) < f (x) ∀t ∈ (0, ǫ] (4.29)
Denota-se porDf(x) o conjunto de todas as direc¸˜oes de descida da func¸˜ao f no ponto x.
Lema 4.8. Sejaf : Rn→ R uma func¸˜ao diferenci´avel no ponto x ∈ Rn. Ent˜ao:
ii) Se d ∈ Rnsatisfazh∇f(x), di < 0, tem-se que d ∈ D f(x).
Ondeh , i denota o produto interno (escalar) em Rn. Demonstrac¸˜ao. Ver em Izmailov e Solodov (2005).
Lembrando da defini¸c˜ao de ˆangulo entre vetores da geometria anal´ıtica, tem-se que a desigualdade h∇f(x), di < 0 ´e equivalente a dizer que a dire¸c˜ao d forma um ˆangulo maior de 90o com a dire¸c˜ao do gradiente ∇f(x). A Figura 4.4 que se segue, ilustra o conjunto
de descida em um ponto, a partir das curvas de n´ıvel de uma fun¸c˜ao gen´erica.
�1
�2
∇�
Região de Descida
Figura 4.4: Conjunto de DescidaDf(x).
Observac¸˜ao - Segue que d = −∇f(x) ´e uma dire¸c˜ao de descida de f no ponto x, mais ainda, ´e poss´ıvel mostrar que d = −∇f(x) ´e a dire¸c˜ao de m´axima descida da fun¸c˜ao f no
ponto x (IZMAILOV;SOLODOV, 2005; BRAND ˜AO, 2010).
Neste momento j´a est´a bem caracterizada a regi˜ao de busca por dire¸c˜oes de descida. Resta agora saber como calcular o tamanho do passo na dire¸c˜ao de descida. Na defini¸c˜ao de descida ´e garantido apenas que, para pequenos passos na dire¸c˜ao de descida, a fun¸c˜ao diminuiria seu valor. O comprimento do passo ´e calculado a partir da observa¸c˜ao do comportamento da fun¸c˜ao f ao longo da semi-reta a partir de x na dire¸c˜ao de d. Por
este motivo, os procedimentos para o c´alculo do tamanho do passo s˜ao chamados de busca
linear. A seguir est˜ao listadas as principais estrat´egias descritas na literatura para a busca linear para o m´etodo da m´axima descida ou m´etodo do gradiente (IZMAILOV;SOLODOV, 2007; BRAND ˜AO, 2010).
• Regra da Minimiza¸c˜ao Exata Unidimensional
Como deseja-se diminuir o valor da fun¸c˜ao objetivo caminhando em sentido a uma dire¸c˜ao de descida, nada ´e mais natural que definir, na k-´esima itera¸c˜ao, o tamanho do passo como sendo o argumento que satisfaz o seguinte problema de minimiza¸c˜ao unidimensional:
tk= arg min
| {z }
t>0
{ϕ(t) = f(xk− t∇f(xk))} (4.30)
onde ϕ : (0, ∞) → R ´e uma fun¸c˜ao real de uma vari´avel.
Primeiramente observe que, sendo −∇f(xk)) uma dire¸c˜ao de descida, o problema 4.30,
possui solu¸c˜ao. Observe ainda que, caso a fun¸c˜ao f seja diferenci´avel, para toda dire¸c˜ao de descida dk, segue que
0 = ϕ′(t
k) = h∇f(xk+ tkdk), dki = h∇f(xk+1), dki (4.31)
Se ∇f(xk+1) 6= 0, do ponto do vista da geometria do problema, o ponto xk+1 ´e a
intesec¸c˜ao da semi-reta, que inicia-se em xk e com dire¸c˜ao dk com a curva de n´ıvel que
passa pelo ponto xk+1. Em particular, o m´etodo do gradiente move-se sempre em passos
fato, tem-se que
hxk+1− xk, xk+2− xk+1i = h−tk∇f(xk), −tk+1∇f(xk+1)i (4.32)
= tk+1tkh∇f(xk), ∇f(xk+1)i.
Note que, pela Equa¸c˜ao 4.31, tem-se que h∇f(xk), ∇f(xk+1)i = 0, assim pode-se ver
que dois passos consecutivos no m´etodo do gradiente s˜ao perpendiculares. A Figura 4.5 ilustra alguns passos consecutivos para o m´etodo do gradiente com a escolha do tamanho do passo atrav´es da minimiza¸c˜ao exata.
�∗ �� ��+1 ��+2 � �
Figura 4.5: Geometria do m´etodo do Gradiente com passo obtido pela minimizac¸˜ao exata.
Neste momento ´e conveniente ressaltar que para resolver, de forma aproximada, o problema 4.30 (minimiza¸c˜ao unidimensional) pode-se utilizar qualquer um dos m´etodos descritos na se¸c˜ao anterior deste cap´ıtulo.
A seguir ´e apresentado um teorema que garante a convergˆencia do m´etodo do Gradi- ente, com a escolha do tamanho do passo pela minimiza¸c˜ao exata.
determinadox0o conjunto de n´ıvel
Lf(f (x0)) = {x ∈ Rn; f (x) 6 f (x0)} (4.33)
seja fechado. Se{xk} ´e a sequˆencia gerada pelo M´etodo do Gradiente, com ponto inicial x0, e
com o tamanho do passo determinado pela minimizac¸˜ao exata, ent˜ao tem-se que:
i) a sequˆencia {xk} ´e limitada;
ii) todo ponto de acumulac¸˜ao de {xk} ´e ponto cr´ıtico da func¸˜ao f.
Demonstrac¸˜ao. Ver em Izmailov e Solodov (2007).
Para finalizar o assunto da minimiza¸c˜ao exata unidimensional, note que este processo pode ser demasiadamante caro do ponto de vista computacional. Sendo assim faz-se necess´ario utilizar alguma estrat´egia para encontrar tkque minimize a fun¸c˜ao f na dire¸c˜ao
de descida −∇f(xk). Os m´etodos da bissec¸c˜ao, se¸c˜ao ´aurea, interpola¸c˜ao polinomial s˜ao
bastante utilizados no intuito de encontrar uma solu¸c˜ao aproximada para o problema de minimiza¸c˜ao unidimensional.
• Regra Regulariza¸c˜ao Proximal
Na Regulariza¸c˜ao Proximal a escolha do tamanho do passo, na k-´esima itera¸c˜ao, ´e o argumento que satisfaz o seguinte problema de minimiza¸c˜ao unidimensional:
tk= arg min
| {z }
t>0
{ϕ(t) = f(xk− t∇f(xk)) + αk||∇f(xk)||2t2} (4.34)
onde ϕ : (0, ∞) → R ´e uma fun¸c˜ao real de uma vari´avel e αk> 0.
Outra estrat´egia para escolha do passo no m´etodo do Gradiente ´e calcular o compri- mento deste passo que resulta em um decr´escimo suficiente da fun¸c˜ao f em rela¸c˜ao ao valor f (xk). Esta id´eia surge com a inten¸c˜ao do c´alculo do tamanho do passo ser mais
econˆomico do que na minimiza¸c˜ao exata unidimensional.
A Regra para escolha do tamanho do passo no M´etodo do Gradiente denominada Regra de Armijo pode ser definida pelas condi¸c˜oes abaixo. Suponha que a fun¸c˜ao f possua derivada primeira cont´ınua e escolha parˆametros ¯t > 0 e σ, θ ∈ (0, 1). Tome tk= ¯t, ent˜ao:
a) Verificar se a desigualdade
f (xk− tk∇f(xk)) 6 f (xk) + σtk||∇f(xk)||2 (4.35)
´e satisfeita ou n˜ao;
b) Se a Equa¸c˜ao 4.35 n˜ao se satisfaz, ent˜ao tome tk = θ¯t e retorne ao passo a). Caso
contr´ario, aceita-se tk = ¯t como valor do comprimento de passo.
Izmailov e Solodov (2007) mostram que a Regra de Armijo est´a bem definida e at´e estabelecem uma cota inferior para o valor do comprimento de passo dado pela Regra de Armijo.
• Regra do Gradiente Lipschitz
A seguir ser´a apresentado um conceito para auxiliar na defini¸c˜ao da regra do Gradiente Lipschitz.
tanteL satisfazendo
||f(x) − f(y)|| 6 L||x − y||, ∀x, y ∈ Rn. (4.36)
O ´ınfimo das constantesL para os quais a desigualdade acima ´e v´alida ´e chamado de Constante
de Lipschitz.
Na Regra do Gradiente Lipschitz, como o pr´oprio nome diz, sup˜oe-se que o gradiente da fun¸c˜ao f satisfaz a defini¸c˜ao 4.10 com constante de Lispschitz L. A regra do Gradiente Lipschitz, para a escolha do tamanho do passo no m´etodo do Gradiente, ´e dada pela determina¸c˜ao de constantes δ1, δ2 e tk tais que
1 2δ1 + δ2 < 1 e 0 < δ1 < tk< 2 L(1 − δ2) . (4.37)
A seguir ´e apresentado um teorema sobre a convergˆencia do M´etodo do Gradiente, com o tamanho do passo determinado pela regra do Gradiente Lipshitz.
Teorema 4.11. Suponha que uma func¸˜aof : Rn→ R possua derivada cont´ınua e que o gradi-
ente seja Lipschitz com constanteL. Se {xk} ´e a sequˆencia gerada pelo M´etodo do gradiente,
com a escolha do tamanho do passo determinado pela Regra do Gradiente Lipschitz, ent˜ao
i) existe β > 0 tal que f (xk+1) < f (xk) − β||xk+1− xk||2;
ii) {f(xk)} ´e mon´otona n˜ao crescente e convergente;
iii) ∞ X k=0 ||xk+1− xk||2 < ∞; iv) lim k→∞||xk+1− xk|| = 0;
Demonstrac¸˜ao. Ver em Izmailov e Solodov (2007).
Os autores Izmailov e Solodov (2007) apresentam, sob hip´oteses variadas, algumas demonstra¸c˜oes de convergˆencia do M´etodo do Gradiente com v´arios tipos de escolha do tamanho do passo. Brand˜ao (2010) tamb´em realiza um estudo sobre a convergˆencia do m´etodo do Gradiente e traz alguns exemplos aplica¸c˜oes pr´aticas do m´etodo.