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.

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

${\displaystyle F:\,\mathbb {R} ^{n}\,\to \,\mathbb {R} }$

ou seja um ponto z tal que

${\displaystyle 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 ${\displaystyle \mathbf {x} \in V_{\mathbf {z} }}$ (uma vizinhança de z).

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

${\displaystyle \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 ${\displaystyle F}$, desde que a escolha da direção ${\displaystyle \mathbf {d} _{n}}$ implique

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

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

Neste caso, a direção ${\displaystyle \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

${\displaystyle 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):

${\displaystyle 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:

${\displaystyle \mathbf {d} _{n}\cdot \nabla F(\mathbf {x} _{n})<0\quad \quad (5)}$

já que ${\displaystyle \omega _{n}}$ é assumido ser positivo.

Método do gradiente

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

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

porque

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

notando ainda que ${\displaystyle \nabla F(\mathbf {x} _{n})=\mathbf {0} }$ só se ${\displaystyle \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 ${\displaystyle \omega _{n}}$ a ser considerado na iteração:

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

quando a direção de descida ${\displaystyle \mathbf {d} _{n}}$ está determinada (por exemplo, pelo método do gradiente).

Há duas abordagens possíveis:

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

${\displaystyle g(\omega )=f(\mathbf {x} _{n}+\omega \mathbf {d} _{n})}$

notando que ${\displaystyle \mathbf {x} _{n},\mathbf {d} _{n}}$ estão fixos e apenas ${\displaystyle \omega >0}$ está a variar.

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

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

Notas e Referências