Ajudar a decidir entre interpolação cúbica e quadrática na pesquisa de linha

Estou realizando uma pesquisa de linha como parte de um algoritmo quase-Newton BFGS. Em uma etapa da pesquisa de linha, uso uma interpolação cúbica para me aproximar do minimizador local.

Seja a função de interesse. Eu quero encontrar um tal que .x ∗ f ′ ( x ∗ ) ≈ $f : R \rightarrow R, f \in C^1$$x^*$$f'(x^*) \approx 0$

Deixe- , , e ser conhecido. Suponha também . Eu ajusto um polinômio cúbico modo que , , e .f ′ ( x k ) f ( x k + 1 ) f ′ ( x k + 1 ) 0 ≤ x k < x ∗ < x k + 1 Q ( x ) = a x 3 + b x 2 + c x + d Q ( 0 ) = $f(x_k)$$f'(x_k)$$f(x_{k+1})$$f'(x_{k+1})$$0\le x_k<x^*<x_{k+1}$$Q(x)=ax^3+bx^2+cx+d$Q ′ ( 0 ) = f ′ ( x k ) Q ( x k + 1 - x k ) = f ( x k + 1 ) Q ′ ( x k + 1 - x k ) = f ′ ( x k + 1$Q(0)=f(x_k)$$Q'(0)=f'(x_k)$$Q(x_{k+1}-x_{k})=f(x_{k+1})$$Q'(x_{k+1}-x_{k})=f'(x_{k+1})$

a equação quadrática: para o meu procurado usando a solução de forma fechada.x $(1): Q'(x^*-x_k) = 0$$x^*$

O exemplo acima funciona bem na maioria dos casos, exceto quando como a solução de formulário fechado para divide por que fica muito próxima ou exatamente a .( 1 ) a $f(x)=\mathcal{O}(x^2)$$(1)$$a$$0$

Minha solução é olhar para e se ele é "muito pequeno" simplesmente tomar a solução de forma fechada para o minimizador do polinômio quadrático para o qual eu já tenho os coeficientes do ajuste anterior para .Q 2 ( x ) = b x 2 + c x + d b , c , d Q ( x $a$$Q_2(x)=bx^2+cx+d$$b,c,d$$Q(x)$

Minha pergunta é: como elaborar um bom teste para quando fazer a interpolação quadrática sobre o cúbico? A abordagem ingênua para testar é ruim devido a razões numéricas, então estou olhando para , onde é a precisão da máquina, mas eu sou incapaz de decidir um bom que é invariante escala de .| a | < ϵ τ ϵ τ $a \equiv 0$$|a| < \epsilon\tau$$\epsilon$$\tau$$f$

Pergunta do bônus: existem problemas numéricos com o uso dos coeficientes do ajuste cúbico com falha ou devo executar um novo ajuste quadrático com a maneira apropriada de calcular os coeficientes?$b,c,d$

Editar para esclarecimentos: Na minha pergunta, é na verdade o que é comumente conhecido como na literatura. Eu apenas simplifiquei a formulação da pergunta. O problema de otimização que estou resolvendo não é linear em 6 dimensões. E eu estou bem ciente de que as condições de Wolfe são suficientes para a pesquisa de linha BFGS, portanto, afirmando que eu estava interessado em ; Estou procurando por algo que satisfaça as condições fortes de Wolfe e usar o minimizador da aproximação cúbica é um bom passo ao longo do caminho.ϕ ( α ) = f ( ˉ x k + α ¯ p k ) f ′ ( x ∗ ) ≈ $f$$\phi(\alpha)=f(\bar{x}_k+\alpha \bar{p_k})$$f'(x^*) \approx 0$

A questão não era sobre BFGS, mas como determinar quando o coeficiente cúbico é pequeno o suficiente para que uma aproximação quadrática seja mais apropriada.

Editar 2: Atualizar notação, as equações permanecem inalteradas.

Hmm ... a interpolação cúbica não é inédita na pesquisa de linhas, mas geralmente é um exagero.

Se estou lendo seu problema corretamente, é apenas um escalar? Nesse caso, o BFGS provavelmente não é a maneira mais eficiente de resolver seu problema. Algoritmos de otimização escalar, como o método de Brenth, provavelmente resolverão seu problema mais rapidamente.$x$

Existem vários algoritmos de pesquisa de linha para BFGS. Para meus próprios aplicativos, usando o BFGS com memória limitada (L-BFGS), esta pesquisa de linhas funciona muito bem. Lembre-se de que você só precisa satisfazer as condições de Wolfe e provavelmente não está ganhando muito encontrando o minimizador exato.

De qualquer forma, para realmente responder à sua pergunta: eu consideraria simplesmente mudar para o polinômio quadrático se resolver o cúbico produzir valores "ruins", como NaN ou Inf (como é feito aqui ).

Não sei bem o que você quer dizer com ? Esses coeficientes para o ajuste cúbico não serão os mesmos que para o ajuste quadrático, portanto você não poderá reutilizá-los.$b,c,d$

Por fim, convém usar , em vez de , pois sua função (provavelmente) será apenas aproximadamente cúbica ou quadrática localmente, e e devem ser mais próximos um do outro (e a solução) do que .f ( x 0 ) x k x k - 1 x $f(x_{k-1})$$f(x_0)$$x_k$$x_{k-1}$$x_0$

Espero que isto ajude.

Há um artigo de Moré, implementado pela Nocedal, sobre isso:

Jorge J. Moré e David J. Thuente. 1994. Algoritmos de busca de linha com redução suficiente garantida. ACM Trans. Matemática. Softw. 20, 3 (setembro de 1994), 286-307. DOI http://dx.doi.org/10.1145/192115.192132 ( pré-impressão ).