Um estudo sobre o M´etodo do Gradiente

Resumo

Determinar pontos cr´ıticos de func¸oes tem importantes aplicações, como por exemplo, determinar autovalores de matrizes simetricas, problemas relacionados a sistemas de agroindústria entre outros. Normalmente, existe dificuldade de determinar esses pontos cr´ıticos de maneira algebrica, para isso, se faz necessário a utilização de algoritmos para realizar esta ˜ tarefa. Para este fim, alguns metodos de Otimizaão Contínua sao aplicados, por exemplo,  o Método de Newtom, BFGS, e o Método do Gradiente. Neste trabalho, nós fizemos uma ánalise teórica do Método do Gradiente equipado com as normas Euclidiana, da soma e do máximo. A fim de evidenciar, do ponto de vista numérico, qual das três normas têm um melhor desempenho nós minímizamos a função de Rosenbrock, dado por: ˜ f : Rn → R tal que 

f(x) = 

nX−1 i 

[a(xi+1 − x2i)2 + b(xi − 1)2] com a, b ∈ R. 

No que segue, apresentamos formalmente o Metodo do Gradiente: ´ 

Algoritmo 1: Metodo do gradiente (MG) ´ 

1 Tome um ponto inicial x0 ∈ Rn, η ∈ (0, 1), ϵ > 0 e fac¸a k := 0. 

2 dk := −∇f(xk). 

3 Se ||dk|| > ϵ fac¸a 

αk := max  2−j: f(xk + 2−jdk) ≤ f(xk) − η2−j(norm(dk))2, j ∈ N . (1) 4 xk+1 := xk + αkdk. 

5 k ← k + 1 e retome para o passo 2. 

O que segue assegura convergencia de uma sequência gerada pelo Algoritmo 1. ˆ Teorema 0.1. Seja f : Rn → R de classe C1. Entao, toda sequência gerada pelo Algoritmo 1 é globalmente convergente. ´ 

Observamos que no passo 3, norm(·) denota a norma Euclidiana, do maximo, ou da soma. Implementamos o Algoritmo 1 para n = 10, 50, 100, 150, 200, 250, 300, 350, 400, 500, a = 1, 10, 15, 30 e 5 pontos iniciais para cada n e cada a. Isto totaliza 200 problemas. Nossos experimentos numericos mostram que os tr ´ es m ˆ etodos resolveram em torno de 75% dos problemas. O Algoritmo 1 apresenta desempenho similar nas três normas. Contudo, na norma euclidiana o desempenho oscila, na norma da soma e na norma do máximo, o desempenho ´é estável.

Agência de fomento: VOLUNTÁRIO