# 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
       $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)

## Notas e Referências

* ↑ David 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]