0866

Título
MÉTODO DE CAUCHY: COMO A ESCOLHA DO TAMANHO DO PASSO INTERFERE NO DESEMPENHO

Aluno: Rodrigo Zeni Stocco - PET - Curso de Matemática (Bacharelado e Licenciatura) (T) - Orientador: Mael Sachine - Departamento de Matemática - Área de conhecimento: 10104003 - Palavras-chave: otimização; método de cauchy; método do gradiente conjugado - Coorientador: Ademir Alves Ribeiro.

Neste trabalho realizamos um estudo do algoritmo de Cauchy, também conhecido como método do gradiente ou da máxima descida, que é um dos mais antigos e mais conhecidos métodos para minimizar uma função de várias variáveis, sendo globalmente convergente sob certas hipóteses. O algoritmo consiste em fazer uma busca linear na direção oposta ao vetor gradiente no ponto corrente, pois sabemos que dentre todas as direções ao longo das quais a função objetivo decresce, a direção oposta ao gradiente é a de decrescimento mais acentuado. Estudamos ainda três maneiras distintas para a escolha do comprimento do passo: a primeira delas é a busca exata, que consiste em minimizar uma função real a partir de um ponto e uma direção determinados. Para as funções onde não é fácil encontrar o minimizador global de forma direta, utilizamos o método da seção áurea que particiona sucessivamente o intervalo que contém o minimizador até encontrar uma aproximação para a solução dentro de uma precisão pré-determinada. A segunda maneira estudada para tentar reduzir o valor da função ao longo de uma direção foi a busca de Armijo, que procura uma redução suficiente proporcional ao tamanho do passo. Finalmente estudamos a busca de Barzilai-Borwein, que escolhe o tamanho do passo na iteração k como sendo o exato da iteração k-1. Com o objetivo de comparar o desempenho dessas três variantes do método de Cauchy, implementamos em MATLAB o algoritmo para funções quadráticas convexas, cujas matrizes Hessianas foram geradas a partir de seus autovalores. Geramos um gráfico de perfil de desempenho representando a performance dos três métodos em relação ao tempo. Apresentamos figuras mostrando as trajetórias das sequências geradas por cada variante do método, tendo como objetivo não apenas ilustrar os passos de Cauchy, como também evidenciar propriedades deste algoritmo, particularmente a taxa de convergência.