Otimização/Métodos de região de confiança

Considere o seguinte problema de programação diferenciável não linear sem restrições:

$(P)\left\{{\begin{matrix}\min f(x)\\x\in \mathbb {R} ^{n}\end{matrix}}\right.$

onde $f:\mathbb {R} ^{n}\mapsto \mathbb {R}$ é de classe $C^{2}(\mathbb {R} ^{n})$.

Observação: Como $f$ não é necessariamente convexa, a matriz $\nabla ^{2}f(x)$ pode não ser definida positiva, apesar de ser simétrica. Neste caso, o método de Newton ou suas variantes (direções conjugadas, quase Newton, etc) não servem.

O primeiro método de região de confiança (em inglês, Trust region method), foi introduzido por Powel em 1970 (qual artigo?) mas oficialmente introduzido por Dennis em 1978 (artigo?). Ele consiste no seguinte:

A cada iteração, se constrói um modelo quadrático e uma região de confiança

este princípio pode ser considerado como uma extensão da busca de Armijo unidimensional.

Breve revisão da busca de Armijo

Para entender a geometria do método de região de confiança, é bom lembrar a geometria da busca de Armijo unidimensional.

Seja $d$ uma direção de descida de uma função $f$ a partir do ponto $x$. Então $\nabla f(x)^{\top }d<0$. Agora, considerando $\theta :\mathbb {R} \mapsto \mathbb {R}$, definida por $\theta (t)=f(x+td)$, tem-se:

$\theta '(t)=\nabla f(x+td)^{\top }d$. Assim, $\theta '(0)=\nabla f(x)^{\top }d<0$. Se $\alpha \in (0,1)$, então $\theta '(0)<\alpha \theta '(0)<0$.

Exercício

Mostrar que sempre existe $t>0$ tal que ${\frac {f(x+td)-f(x)}{t}}={\frac {\theta (t)-\theta (0)}{t-0}}\leq \alpha \theta '(0)$.

Resolução
A resolução deste exercício é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

A busca de Armijo consiste em tomar $t>0$.

Se ${\frac {f(x+td)-f(x)}{t}}>\alpha \theta '(0)>\theta '(0)$

Mas como $\theta '(0)=\lim _{t\to 0}{\frac {f(x+td)-f(x)}{t}}$, então existe algum $t>0$ tal que vale ${\frac {f(x+td)-f(x)}{t}}\leq \alpha \theta '(0)$. A tal ponto, chama-se ponto de Armijo.

Introduzindo as seguinte notação

$m(x+h)=f(x)+\nabla f(x)^{\top }h$	(modelo linear para a função $f$)
$pred=m(x)-m(x+td)=-t\theta '(0)$	(redução predita por este modelo)
$ared=f(x)-f(x+td)$	(redução real no valor da função)

a pergunta é:

Quando um ponto $t$ vai ser ponto de Armijo com essa notação?

Tem-se:

$\alpha \cdot pred=-\alpha t\theta '(0)\leq f(x)-f(x+td)=ared$

Logo, se $\alpha \cdot pred\leq ared$ segue que $t$ é um ponto de Armijo.

Observações: Note que a essência da busca linear de Armijo é construir um modelo linear e um intervalo compacto $[0,t]$, sendo $t>0$ e o ponto inicial da busca e logo procurar o ponto de Armijo em $[0,t]$.

De volta ao método

O método de região de confiança será uma generalização da busca de Armijo, consistindo da construção de um modelo quadrático e uma região $R$, chamada de região de confiança, e nessa região calcular o novo iterando.

Algoritmo da região de confiança

Primeiro passo: Escolha $x_{0}\in \mathbb {R} ^{n}$, $r>0$, $\alpha \in (0,1)$, $\beta \in (0,1)$ e $k=0$.

Passo iterativo $k$: Enquanto $\nabla f(x_{k})\not =0$, construa o modelo quadrático:
 $m_{k}(h)=\nabla f(x_{k})^{\top }h+{\frac {1}{2}}h^{\top }H_{k}h$
Calcule $d$, solução de
 $(P)\left\{{\begin{matrix}\min m_{k}(h)\\\|h\|\leq r\end{matrix}}\right.$
Tome $ared=f(x_{k})-f(x_{k}+d)$ e $pred=-m_{k}(d)$
Se ${\frac {ared}{pred}}>\alpha$, fazer $x_{k+1}=x_{k}+d$
Senão $x_{k+1}=x_{k}$, $r=\beta r$ e $k=k+1$

Comentários: No algoritmo anterior, quando se tem um passo falho, a região de confiança sempre diminui. Seria bom incluir casos bons, onde a região deve crescer.

Algoritmo da região de confiança melhorado

Primeiro passo: Escolha $x_{0}\in \mathbb {R} ^{n}$, $r>0$, $0<\alpha <\gamma <1$, $\beta \in (0,1)$, $\beta _{2}>1$, $\epsilon \in (0,1)$ e $k=0$.

Passo iterativo $k$: Enquanto $\|\nabla f(x_{k})\|>\epsilon$, construa o modelo quadrático:
 $m_{k}(h)=\nabla f(x_{k})^{\top }h+{\frac {1}{2}}h^{\top }H_{k}h$
Continue = 1
Enquanto (Continue = 1)
  Calcule $d$, solução de
   $(P)\left\{{\begin{matrix}\min m_{k}(h)\\\|h\|\leq r\end{matrix}}\right.$
  Tome $ared=f(x_{k})-f(x_{k}+d)$ e $pred=-m_{k}(d)$
  Se ${\frac {ared}{pred}}>\alpha$, fazer $x_{k+1}=x_{k}+d$
    Se $r>\gamma$, $r=\beta _{2}r$; Continue = 0
    k = k+1
  Senão $r=\beta _{1}r$

O subproblema quadrático

Conforme foi explicado, o método das regiões de confiança constrói um modelo quadrático da forma:

$m(h)=g^{\top }h+{\frac {1}{2}}h^{\top }Hh$

onde, no método, $g=\nabla f(x_{k})$ e $H=H_{k}$. Em tal modelo, tem-se

• $g$ um vetor não nulo;
• $h$ uma matriz simétrica (que pode não ser definida positiva)

O problema quadrático é

$(PQ)\left\{{\begin{matrix}\min m(h)\\\|h\|\leq r\end{matrix}}\right.$

com $r>0$.

Este é o problema que será tratado a seguir.

Exercício

Provar que $(PQ)$ sempre tem solução.

Resolução
Esboço: Como $h$ é uma função contínua e o conjunto onde se quer minimizar tal função é uma bola, em dimensão finita, trata-se de minimizar uma função contínua em um compacto. Esse é um problema que tem solução, pelo teorema de Weierstrass.

O exercício anterior garante que o método está bem definido, quer dizer, todas as etapas podem ser realizadas.