MÉTODOS QUASE-NEWTON PARA OTIMIZAÇÃO IRRESTRITA

Aluno de Iniciação Científica: Wagner Augusto Almeida de Moraes (Outro)
Curso: Matemática (Bacharelado e Licenciatura)
Orientador: Ademir Alves Ribeiro
Departamento: Matemática
Setor: Ciências Exatas
Palavras-chave: Otimização , Quase-Newton , Algoritmo
Área de Conhecimento: 10104003 - MATEMÁTICA APLICADA

Otimização está presente no nosso dia a dia em vários campos da ciência, como informática, logística, medicina, processos sísmicos e transporte. Podemos dizer que otimização consiste em encontrar mínimos ou máximos de uma função real sobre um subconjunto Ω do Rn. Este trabalho trata de otimização irrestrita, onde Ω é o próprio Rn. Primeiramente, definimos minimizadores locais e globais de funções e estudamos condições que garantem que determinada função contínua possua um minimizador global. Vimos também condições necessárias e suficientes para que um ponto seja minimizador local. Uma destas condições diz que para que o ponto x* seja minimizador local é necessário que o gradiente da função neste ponto seja nulo. Esta é a principal maneira de encontrar prováveis minimizadores, porém dificilmente conseguimos encontrar estes pontos de maneira direta. Normalmente a solução é obtida por meio de processos iterativos. Vimos o conceito de algoritmo de descida e notamos que a escolha do tamanho do passo e da direção não deve ser tomada de forma arbitrária. Assim, analisamos métodos para essas escolhas, como a escolha do tamanho do passo por Busca Exata ou por Armijo. Provamos que com esses tamanhos de passo e com uma direção de descida que envolva uma matriz H definida positiva e o gradiente da função, os algoritmos convergem globalmente. Os métodos de otimização diferem entre si pela maneira com que se escolhe essa matriz H definida positiva. Há métodos clássicos, como o método de Cauchy, em que H é a matriz identidade, e o método de Newton, na qual H é a inversa da Hessiana da função. Após estudar e analisar propriedades destes métodos vimos que cada um possui suas vantagens e desvantagens. É aí que aparecem os métodos Quase-Newton, que visam melhorar a performance em relação a Cauchy e ser computacionalmente mais barato quando comparados com o de Newton. A ideia é construir aproximações para a Hessiana da função ao longo das iterações. Existem dois métodos para atualizar a matriz Hessiana ao longo das iterações. O primeiro foi desenvolvido por Davidon, Fletcher e Powell, conhecido como método DFP, e o segundo, conhecido como método BFGS, desenvolvido por Broyden, Fletcher, Goldfarb e Shanno. Ambos possuem propriedades muito interessantes, como minimizar uma função quadrática em um número finito de passos. Após a abordagem teórica, implementamos os algoritmos no MATLAB 7 e para comparar a eficiência dos métodos, foi feito uso de um procedimento chamado Gráfico de Perfil de Desempenho.

 

0037