Métodos de Direções de Busca-Buscas Aleatorias

Prévia do material em texto

Métodos de Direções de Busca 
 
Os primeiros métodos de otimização (minimização) de funcionais não-lineares 
foram desenvolvidos a partir da ideia básica de fazer o algoritmo evoluir encontrando 
novos pontos situados em direções para as quais o funcional decresça, em relação ao 
ponto corrente. 
A versão mais primitiva dessa família de métodos vem a ser o Algoritmo do 
Gradiente": dado um ponto inicial do espaço de busca, obtém-se um novo ponto situado 
sobre a reta definida por esse ponto e pelo gradiente da função objetivo. 
Essa é a direção para a qual, localmente, a função mais rapidamente decresce (no 
sentido contrario ao do gradiente). Determina-se o novo ponto como sendo aquele em 
que a função objetivo atinge o mínimo sobre essa reta (note-se que este é um problema 
de minimização de uma função de uma única variável). A partir desse novo ponto, 
repete-se o processo, até que seja satisfeito um critério de convergência. 
Ao longo das décadas de 50 e 60 do século XX, tal método básico foi 
aperfeiçoado, para permitir que a direção de busca na qual era feita a busca 
unidimensional sofresse uma “correção”. Tal correção levava em conta mais 
informações a respeito da função objetivo, além do valor de seu gradiente no ponto 
corrente: procurava-se também levar em consideração a curvatura da função. 
Aproximações de segunda ordem, por exemplo, levando em consideração estimativas da 
Hessiana da função objetivo, permitiram significativa aceleração de convergência dos 
métodos. 
Os métodos aqui agrupados sob a denominação de “direção de busca” têm essa 
raiz, e possuem em comum as seguintes características: 
 
 Cada novo ponto é obtido de um processo de otimização unidimensional 
que tem como ponto de partida o ponto anterior. 
 A direção na qual é feita a busca unidimensional é uma função das 
avaliações anteriores da função objetivo. 
 
O objetivo deste capítulo é o estudo dessa classe de métodos, sendo o conteúdo 
selecionado para fundamentar sua compreensão geral. Não houve a intenção de esgotar 
a apresentação de todas as variações já desenvolvidas de métodos classificados nesta 
categoria. 
 
6.1 Estrutura Básica 
 
 
 
 
Nessa estrutura, h(‘, ....,’ ) é uma função que em geral será recursiva, isto é, não 
irá depender explicitamente dos pontos anteriores, mas irá armazenar sua influência em 
variáveis intermediárias. Um algoritmo irá diferir do outro essencialmente pela maneira 
como é calculada a direção de busca dk, ou seja, na escolha dessa função. 
 
Ex1: Algoritmo Gradiente 
 
Ex2: Algoritmo de Newton 
 
 
6.2 Busca em Direções Aleatórias 
 
Considere-se o algoritmo definido por: 
 
A função rand(n,1) é definida tal que sua saída é um vetor de n componentes 
aleatórias com distribuição Gaussiana, média 0 e variância 1. A convergência desse 
algoritmo para o ponto de mínimo de uma função unimodal é estabelecida no teorema a 
seguir. 
 
 
Ver demonstração do Teorema 6.1 nas notas de aulas do professor 
Takahashi. 
 
Percebe-se que para este tipo de algoritmo, ocorre-se a aproximação, mas não a 
convergência para o ponto de mínimo x*. De qualquer forma, este é um algoritmo que 
efetivamente funcionaria para a minimização de funções. A questão a ser observada é 
que uma escolha adequada da direção de busca dk, em substituição _a escolha aleatória, 
pode aumentar em muito a eficiência do algoritmo de minimização. Os diversos 
algoritmos de direções de busca surgem precisamente quando se propõem diferentes 
formas de se fazer tal escolha de uma direção.