Loading AI tools
Da Wikipédia, a enciclopédia livre
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.
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.
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.
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.
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:
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.
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:
por exemplo, calculando os zeros da derivada da função g.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.