Pesquisa linear

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

$F:{ℝ}^n\to ℝ$

ou seja um ponto z tal que

$F(𝐳)<F(𝐱),\mathrm{\forall }𝐱\ne 𝐳$

sendo ponto de mínimo local se a condição se verificar para $𝐱\in V_{𝐳}$ (uma vizinhança de z).

Começando com um vetor inicial ${𝐱}_0$  visando alcançar um ponto de mínimo de $F$, consideramos a sucessão definida por ${𝐱}_0,{𝐱}_1,{𝐱}_2,\dots$ onde

${𝐱}_{n+1}={𝐱}_n+{\omega }_n{𝐝}_n(1)$.

Esta é a forma geral de um método de descida para a função $F$, desde que a escolha da direção ${𝐝}_n$ implique

$F({𝐱}_{n+1})<F({𝐱}_n)(2)$

para um certo passo ${\omega }_n>0.$

Neste caso, a direção ${𝐝}_n$ 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

$F({𝐱}_{n+1})=F({𝐱}_n)+({𝐱}_{n+1}-{𝐱}_n)\cdot \mathrm{\nabla }F({𝐱}_n)+o(||{𝐱}_{n+1}-{𝐱}_n||)(3)$

e substituindo por (1) obtemos (desprezando o termo infinitesimal):

$F({𝐱}_{n+1})-F({𝐱}_n)\approx {\omega }_n{𝐝}_n\cdot \mathrm{\nabla }F({𝐱}_n)(4)$.

Portanto, para termos uma direção de descida que verifique (2), através da expressão (4) basta considerar a condição de descida:

${𝐝}_n\cdot \mathrm{\nabla }F({𝐱}_n)<0(5)$

já que ${\omega }_n$ é assumido ser positivo.

Método do gradiente

No caso do método do gradiente a condição de descida verifica-se tomando

${𝐝}_n=-\mathrm{\nabla }F({𝐱}_n)$

porque

$(-\mathrm{\nabla }F({𝐱}_n))\cdot \mathrm{\nabla }F({𝐱}_n)=-||\mathrm{\nabla }F({𝐱}_n)|{|}^2<0(6)$

notando ainda que $\mathrm{\nabla }F({𝐱}_n)=\mathrm{𝟎}$ só se ${𝐱}_n$ 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 ${\omega }_n$ a ser considerado na iteração:

${𝐱}_{n+1}={𝐱}_n+{\omega }_n{𝐝}_n$,

quando a direção de descida ${𝐝}_n$ está determinada (por exemplo, pelo método do gradiente).

Há duas abordagens possíveis:

• Pesquisa exata - onde ${\omega }_n$ será o valor otimal numa otimização unidimensional.
• Pesquisa inexata - onde ${\omega }_n$ 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

$g(\omega )=f({𝐱}_n+\omega {𝐝}_n)$

notando que ${𝐱}_n,{𝐝}_n$ estão fixos e apenas $\omega >0$ está a variar.

Se for possível encontrar esse ponto de mínimo, então obtemos:

${\omega }_n=$arg min${}_{\omega >0}g(\omega )$

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 ${𝐱}_0$
• Ciclo em $n$
  • calcula-se a direção de descida ${𝐝}_n$
  • define-se a função $g(\omega )=f({𝐱}_n+\omega {𝐝}_n)$
  • determina-se ${\omega }_n$ = arg min${}_{\omega >0}g(\omega )$
    • (por pesquisa exata ou inexata)
  • define-se ${𝐱}_{n+1}={𝐱}_n+{\omega }_n{𝐝}_n$
• Até que $||\mathrm{\nabla }f({𝐱}_{n+1})||<ϵ$
  • (onde $ϵ$, pequeno, define o critério de paragem)