Pesquisa linear
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Gradient_descent.svg/350px-Gradient_descent.svg.png)
A pesquisa linear é um método numérico usado em otimização, também entendido como método de descida em problemas de minimização. Para encontrar um mínimo (local) de uma função usa-se um esquema iterativo, onde em cada passo se toma uma direção de descida, e dessa forma se garante que o valor seguinte é sempre inferior ao anterior, procurando atingir o mínimo.
Em problemas de maximização, basta trocar o sinal da função, já que um mínimo de F será um máximo de -F, e vice-versa.
Descrição
O objetivo é encontrar o ponto de mínimo de uma função de várias variáveis
ou seja um ponto z tal que
sendo ponto de mínimo local se a condição se verificar para (uma vizinhança de z).
Começando com um vetor inicial visando alcançar um ponto de mínimo de , consideramos a sucessão definida por onde[1]
- .
Esta é a forma geral de um método de descida para a função , desde que a escolha da direção implique
para um certo passo
Neste caso, a direção chama-se direção de descida.
Condição de descida
Para funções diferenciáveis, usamos a expansão em série de Taylor de primeira ordem
e substituindo por (1) obtemos (desprezando o termo infinitesimal):
- .
Portanto, para termos uma direção de descida que verifique (2), através da expressão (4) basta considerar a condição de descida:
já que é assumido ser positivo.
Método do gradiente
No caso do método do gradiente a condição de descida verifica-se tomando
porque
notando ainda que só se for um ponto crítico, o que acontece quando atingimos o ponto de mínimo.
Pesquisa exata e inexata
Um dos problemas habituais nos métodos de pesquisa linear é determinar o passo a ser considerado na iteração:
- ,
quando a direção de descida está determinada (por exemplo, pelo método do gradiente).
Há duas abordagens possíveis:
- Pesquisa exata - onde será o valor otimal numa otimização unidimensional.
- Pesquisa inexata - onde será apenas um valor aproximado.
Isto tem que ser feito a cada passo, pelo que a pesquisa exata pode ser incomportável em tempo computacional, sendo preferível usar uma pesquisa inexata.
Pesquisa exata
No caso da pesquisa exata, procura-se o ponto de mínimo de uma nova função
notando que estão fixos e apenas está a variar.
Se for possível encontrar esse ponto de mínimo, então obtemos:
- arg min
por exemplo, calculando os zeros da derivada da função g.
Pesquisa inexata
Sendo moroso ou impraticável minimizar g considera-se um valor aproximado, dado por exemplo pelo critério de Wolfe, que é um dos critérios mais usados na pesquisa inexata.
Algoritmo
Um algoritmo em pseudo-código pode definir-se assim:
- Define-se o vector inicial
- Ciclo em
- calcula-se a direção de descida
- define-se a função
- determina-se = arg min
- (por pesquisa exata ou inexata)
- define-se
- Até que
- (onde , pequeno, define o critério de paragem)
Notas e Referências
- ↑ David G. Luenberger, Yinyu Ye: Linear and Nonlinear Programming. International Series in Operations Research & Management Science. Volume 116. Springer (2008) [Basic Descent Methods, pág 215]