Otimização/Método da lagrangiana aumentada: diferenças entre revisões

[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
m +parte da demonstração
+demonstração. +teoremas [finalizando aula de 13/11]
Linha 140:
 
Mas a Hessiana de <math>l_{\rho_0}</math> é dada por <math>\nabla_x l_{\rho_0} = \nabla_x^2 l(\bar{x},\bar{v}) + \left(J_H(x)\right)^\top \left(J_H(x)\right)</math>. Logo, a hipótese equivale a dizer que <math>\nabla_x^2 l_{\rho_0} (\bar{x}, \bar{v})</math> é definida positiva.
 
Considere agora a função <math>\delta: \mathbb{R}^n \times \mathbb{R}^n \mapsto \mathbb{R}</math> definida por
:<math>\delta(d,x) = d^\top \nabla_x^2 l_\rho (x,\bar{u}) d</math>
Logo, para qualquer <math>d \not = 0</math>, tomando <math>x = \bar{x}</math>, tem-se
:<math>\delta(d,x) = \delta(d,\bar{x}) = d^\top \nabla_x^2 l_\rho (\bar{x},\bar{u}) d > 0</math>
 
Pela continuidade da função <math>\delta</math>, existe uma vizinhança <math>X_0</math> de <math>\bar{x}</math> tal que <math>\delta(d,x) > 0</math> para todo ponto <math>x \in X_0</math>, e qualquer que seja <math>d\not = 0</math>. Além disso, tal vizinhança pode ser tomada aberta, convexa e suficientemente pequena para que <math>\delta(d,x) \ge \epsilon > 0</math>.
 
Assim, tomando o ínfimo, pode-se definir <math>\delta_0</math> como
:<math>\delta_0 = \inf_{\begin{smallmatrix}x \in X_0\\\|d\| = 1\end{smallmatrix}} \delta(d,x)</math>
 
Então
:<math>\delta\left(\frac{d}{\|d\|}, x\right) = \left(\frac{d}{\|d\|}\right)^\top \nabla_x^2 l_{\rho_0} (x,\bar{u}) \left(\frac{d}{\|d\|}\right) \ge \delta_0</math>
quaisquer que sejam <math>d\not=0</math> e <math>x \in X_0</math>.
 
Portanto,
:<math>d^\top \left[\nabla_x^2 l_{\rho_0} (x,\bar{u})\right] d \ge \delta_0 \|d\|^2</math>
 
ou seja, os auto-valores de <math>\nabla_x^2 l_{\rho_0} (x,\bar{u}) </math> são todos positivos.
 
Para concluir que <math>l_{\rho_0}(\cdot, \bar{u})</math> é fortemente convexa, basta recordar-se de dois fatos:
# Uma função <math>f</math> de classe <math>\mathcal{C}^2</math> é convexa se, e somente se, <math>\nabla^2 f</math> é semidefinida positiva;
# Uma função <math>f</math> é fortemente convexa se, e somente se, existe uma constante <math>\alpha > 0</math> tal que <math>f(x) - \frac{\alpha}{2}\|x\|^2</math> é convexa, ou seja, <math>d^\top \nabla^2 f(x) d - \alpha \|x\|^2 \ge 0</math>.
 
Com isso, <math>l_{\rho_0}(\cdot, \bar{u})</math> é fortemente convexa pois
:<math>d^\top \left[\nabla_x^2 l_{\rho_0} (x,\bar{u})\right] d - \delta_0 \|d\|^2 \ge 0</math>
 
Isso significa que há um único mínimo local para tal função, e que consequentemente ele é um mínimo global. Das hipóteses 1 e 2 colocadas no início da discussão sobre a lagrangiana aumentada, segue que <math>l_{\rho_0}</math> é fortemente convexa em <math>X_0</math>.
}}
 
Com essas condições, mostrou-se que em um ponto que seja solução, a lagrangiana aumentada é fortemente convexa.
 
Antes de apresentar o algoritmo, será fixada mais uma notação:
:<math>(P_{\rho, u})\left\{\begin{matrix}
\min l_{\rho} (x,u)\\
x \in \mathbb{R}^n
\end{matrix}\right.</math>
 
== Algoritmo da lagrangiana aumentada ==
Dados <math>\rho > 0</math> e <math>\epsilon \in (0,\rho)</math>.
 
Início: Tome <math>u_0 \in \mathbb{R}^q</math> e <math>k=0</math>.
Iteração: Calcule <math>x_k</math>, solução de <math>(P_{\rho, u_k})</math>.
Se <math>H(x_k) = 0</math>, pare: <math>\bar{x} = x_k</math>.
Senão, faça
<math>u_{k+1} = u_k + \epsilon H(x_k)</math>
<math>k = k+1</math>
 
 
 
Este é um dos algoritmos mais usados e mais eficientes para problemas de programação não linear. A garantia de convergência segue dos próximos teoremas.
 
{{Teorema
|Sejam <math>\rho_0</math>, <math>\delta_0</math> e <math>X_0</math> como na proposição anterior. Se <math>U</math> é uma vizinhança de <math>\bar{u}</math>, existe algum <math>\rho_U > \rho_0</math> tal que:
# <math>X(\rho, u) \subset X_0, \forall u \in U</math>
# <math>X(\rho, \bar{u}) = \{ \bar{x} \}</math> e <math>\beta_\rho (\bar{u}) = f(\bar{x})</math>
}}
Observações:
* <math>X(\rho, u)</math> denota as soluções do problema;
* A igualdade <math>\beta_\rho (\bar{u}) = f(\bar{x})</math> significa que não há salto de dualidade.
* Já foi mostrado que a função é fortemente convexa em uma vizinhança. Logo, os minimizadores devem estar em tal vizinhança.
* A prova é um pouco técnica, e usa as condições de KKT, mostrando que o cone linearizado é igual ao cone tangente.
{{Demonstração}}
 
O segundo teorema é:
{{Teorema
|Se <math>\rho</math> é suficientemente grande e <math>\delta</math> suficientemente pequeno, então:
# <math>x_k \to \bar{x}</math>
# <math>l_\rho (x_k,u_k) \to f(\bar{x})</math>
# <math>\{u_k\}</math> é limitada
}}
Observações:
* A propriedade 2 praticamente segue do fato de não haver salto de dualidade.
{{Demonstração}}
 
Com esses resultados, tem-se a garantia de que o algoritmo realmente converge para uma solução, desde que os parâmetros sejam tomados adequadamente. A questão que ainda permanece é como identificar os valores adequados de <math>\rho</math> e de <math>\delta</math> para que tal convergência ocorra.
 
{{AutoCat}}