Pesquisa Line - Line search
Na otimização , a pesquisa linha de estratégia é uma das duas básicas iterativos abordagens para encontrar um mínimo local de uma função objetivo . A outra abordagem é a região de confiança .
A abordagem de busca primeira linha encontra um sentido descendente ao longo do qual a função objetivo será reduzida e, em seguida, calcula um tamanho de passo que determina o quão longe deve se mover ao longo dessa direção. A direcção de descida pode ser calculado através de vários métodos, tais como o gradiente descendente , o método de Newton e método de Quasi-Newton . O tamanho do passo pode ser determinada forma exata ou inexata.
exemplo de uso
Aqui é um método de gradiente de exemplo que usa uma pesquisa de linha no passo 4.
- Definir iteração balcão , e fazer uma estimativa inicial para o mínimo
- Repetir:
- Calcular um sentido descendente
- Escolha a 'vagamente' minimizar mais
- Atualização e
- Até <tolerância
Na etapa de pesquisa de linha (4) o algoritmo pode quer exatamente minimizar h , resolvendo , ou vagamente , pedindo uma diminuição suficiente h . Um exemplo do primeiro caso é método de gradiente conjugado . Este último é chamado de busca linear inexata e pode ser realizado em um número de maneiras, tais como a busca linear retrocesso ou usando as condições de Wolfe .
Como outros métodos de otimização, pesquisa linha pode ser combinado com o recozimento simulado para permitir que ele saltar sobre alguns mínimos locais .
algoritmos
métodos de busca direta
Neste método, o mínimo deve ser primeiro entre colchetes, então o algoritmo deve identificar pontos x 1 e x 2 de tal forma que as mentiras mínimos procurado entre eles. O intervalo é então dividido por computação em dois pontos internos, X 3 e X 4 , e rejeitar qualquer dos dois pontos exteriores não é adjacente ao de X 3 e X 4 , que tem o menor valor de função. Nas etapas seguintes, apenas um ponto interno extra deve ser calculado. Dos vários métodos de dividir o intervalo, pesquisa seção áurea é particularmente simples e eficaz, como as proporções de intervalo são preservados, independentemente de como os recursos de busca:
- Onde
Veja também
- pesquisa linha de retrocesso
- método da secante
- O método de Newton na otimização
- busca padrão (otimização)
- método Nelder-Mead
- Pesquisa seção áurea
Referências
- ^ Box, MJ; Davies, D .; Swann, WH (1969). Técnicas de otimização não-linear . Oliver & Boyd.