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).^[1] Um livro popular de Fletcher (1980) chama esses algoritmos de métodos de etapas restritas.^[2] Além disso, em um trabalho inicial sobre o método, Goldfeld, Quandt e Trotter (1966) referem-se a ele como escalada quadrática.^[3]

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 ${\displaystyle A\,\Delta x=b}$ para ${\displaystyle \Delta x}$, ele resolve ${\displaystyle {\big (}A+\lambda \operatorname {diag} (A){\big )}\,\Delta x=b}$, onde ${\displaystyle \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 ${\displaystyle \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, ${\displaystyle \Delta f_{\text{pred}}}$, que esperaríamos ser uma redução menor do que a redução real. Dado ${\displaystyle \Delta x}$, podemos avaliar

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

Olhando para a proporção ${\displaystyle \Delta f_{\text{pred}}/\Delta f_{\text{actual}}}$, podemos ajustar o tamanho da região confiável. Em geral, esperamos ${\displaystyle \Delta f_{\text{pred}}}$ ser um pouco menor do que ${\displaystyle \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.