Pesquisa linear

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.

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)

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:\,\mathbb {R} ^{n}\,\to \,\mathbb {R}$

ou seja um ponto z tal que

$F(\mathbf {z} )<F(\mathbf {x} ),\forall \mathbf {x} \neq \mathbf {z}$

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

Começando com um vetor inicial $\mathbf {x} _{0}$  visando alcançar um ponto de mínimo de $F$, consideramos a sucessão definida por $\mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\dots$ onde

$\mathbf {x} _{n+1}=\mathbf {x} _{n}+\omega _{n}\mathbf {d} _{n}\quad \quad (1)$.

Esta é a forma geral de um método de descida para a função $F$, desde que a escolha da direção $\mathbf {d} _{n}$ implique

$F(\mathbf {x} _{n+1})<F(\mathbf {x} _{n})\quad \quad (2)$

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

Neste caso, a direção $\mathbf {d} _{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(\mathbf {x} _{n+1})=F(\mathbf {x} _{n})+(\mathbf {x} _{n+1}-\mathbf {x} _{n})\cdot \nabla F(\mathbf {x} _{n})+o(||\mathbf {x} _{n+1}-\mathbf {x} _{n}||)\quad \quad (3)$

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

$F(\mathbf {x} _{n+1})-F(\mathbf {x} _{n})\approx \omega _{n}\mathbf {d} _{n}\cdot \nabla F(\mathbf {x} _{n})\quad \quad (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:

$\mathbf {d} _{n}\cdot \nabla F(\mathbf {x} _{n})<0\quad \quad (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

$\mathbf {d} _{n}=-\nabla F(\mathbf {x} _{n})$

porque

$(-\nabla F(\mathbf {x} _{n}))\cdot \nabla F(\mathbf {x} _{n})=-||\nabla F(\mathbf {x} _{n})||^{2}<0\quad \quad (6)$

notando ainda que $\nabla F(\mathbf {x} _{n})=\mathbf {0}$ só se $\mathbf {x} _{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:

$\mathbf {x} _{n+1}=\mathbf {x} _{n}+\omega _{n}\mathbf {d} _{n}$,

quando a direção de descida $\mathbf {d} _{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(\mathbf {x} _{n}+\omega \mathbf {d} _{n})$

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