Região de confiança

Na otimização matemática, uma região de confiança é o subconjunto da região da função objetivo que é aproximada usando uma função de modelo (geralmente uma função quadrática). Se um modelo adequado da função objetivo for encontrado dentro da região de confiança, então a região é expandida; inversamente, se a aproximação for ruim, então a região é contraída.

O ajuste é avaliado comparando a proporção da melhoria esperada da aproximação do modelo com a melhoria real observada na função objetivo. Limitação simples da razão é usada como critério para expansão e contração - uma função de modelo é "confiável" apenas na região em que fornece uma aproximação razoável.

Os métodos de região de confiança são, em certo sentido, duais aos métodos de busca de linha : os métodos de região de confiança primeiro escolhem um tamanho de passo (o tamanho da região de confiança) e depois uma direção de passo, enquanto os métodos de busca de linha primeiro escolhem uma direção de passo e então um tamanho de passo.

A ideia geral por trás dos métodos de região de confiança é conhecida por muitos nomes; o uso mais antigo do termo parece ser de Sorensen (1982). Um livro popular de Fletcher (1980) chama esses algoritmos de métodos de etapas restritas. Além disso, em um trabalho inicial sobre o método, Goldfeld, Quandt e Trotter (1966) referem-se a ele como escalada quadrática.

Exemplo

Conceitualmente, no algoritmo de Levenberg-Marquardt, a função objetivo é aproximada iterativamente por uma superfície quadrática e, em seguida, usando um solucionador linear, a estimativa é atualizada. Isso por si só pode não convergir bem se o palpite inicial estiver muito longe do ideal. Por esse motivo, o algoritmo restringe cada etapa, impedindo-a de avançar "muito longe". Ele operacionaliza "longe demais" da seguinte maneira. Em vez de resolver $A\,\Delta x=b$ para $\Delta x$, ele resolve ${\big (}A+\lambda \operatorname {diag} (A){\big )}\,\Delta x=b$, onde $\operatorname {diag} (A)$ é a matriz diagonal com a mesma diagonal que A, e λ é um parâmetro que controla o tamanho da região de confiança. Geometricamente, isso adiciona um parabolóide centrado em $\Delta x=0$ para a forma quadrática, resultando em um passo menor.

O truque é alterar o tamanho da região de confiança (λ). A cada iteração, o ajuste quadrático amortecido prevê uma certa redução na função de custo, $\Delta f_{\text{pred}}$, que esperaríamos ser uma redução menor do que a redução real. Dado $\Delta x$, podemos avaliar

$\Delta f_{\text{actual}}=f(x)-f(x+\Delta x).$

Olhando para a proporção $\Delta f_{\text{pred}}/\Delta f_{\text{actual}}$, podemos ajustar o tamanho da região confiável. Em geral, esperamos $\Delta f_{\text{pred}}$ ser um pouco menor do que $\Delta f_{\text{actual}}$, e assim a razão estaria entre, digamos, 0,25 e 0,5. Se a proporção for superior a 0,5, estamos amortecendo demais a etapa, portanto, expanda a região de confiança (diminua λ) e itere. Se a razão for menor que 0,25, então a verdadeira função está divergindo "muito" da aproximação da região de confiança, então diminua a região de confiança (aumente λ) e tente novamente.

Referências

V*Dennis, J. E., Jr.; Schnabel, Robert B. (1983). «Globally Convergent Modifications of Newton's Method». Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice-Hall. pp. 111–154. ISBN 0-13-627216-9 

• Andrew R. Conn, Nicholas I. M. Gould, Philippe L. Toint "Trust-Region Methods (MPS-SIAM Series on Optimization)".
• Byrd, R. H, R. B. Schnabel, and G. A. Schultz. "A trust region algorithm for nonlinearly constrained optimization", SIAM J. Numer. Anal., 24 (1987), pp. 1152–1170.
• Yuan, Y. "A review of trust region algorithms for optimization" in ICIAM 99: Proceedings of the Fourth International Congress on Industrial & Applied Mathematics, Edinburgh, 2000 Oxford University Press, USA.
• Yuan, Y. "Recent Advances in Trust Region Algorithms", Math. Program., 2015

Ligações externas

• Site Kranf: algoritmos de região confiável
• Métodos de região confiável