right|thumb|375x375px|Illustração de um método de descida (as linhas a azul correspondem a curvas de nível, e as setas a vermelho correspondem as iterações, que descem em direção ao ponto de mínimo) 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 ondeDavid 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]
.
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)
Categoria:Matemática aplicada Categoria:Pesquisa operacional