Otimização/Método da lagrangiana aumentada

O problema a ser resolvido é:

$\{\begin{array}{c}\min f(x)\\ h_j(x)=0;j=1,\dots ,q\end{array}$

Sabe-se que se for aplicado o método da lagrangiana, será considerada a função:

$l:{ℝ}^n\times {ℝ}^q\mapsto ℝ$ dada por

$l(x,v)=f(x)+\sum _{j=1}^q{v}_j{h}_j(x)$.

e também

$\beta :{ℝ}^q\mapsto ℝ\cup \{-\mathrm{\infty }\}$, dada por

$\beta (v)=\underset{x\in {ℝ}^n}{\inf }l(x,v)$

A grande dificuldade seria saber quando o valor de $\beta$ é finito. Uma idéia seria modificar um pouco a lagrangiana (aumentando-a, com um termo extra), da seguinte maneira:

$l(x,v)=f(x)+\sum _{j=1}^q{v}_j{h}_j(x)+r\sum _{j=1}^q{(h_j(x))}^2$

Com isso, seria necessário garantir que a idéia de fato resolve o problema. Por este motivo, é preciso desenvolver alguns resultados teóricos. Para fazer a análise deste método, um primeiro resultado importante é o seguinte:

A partir de agora, o problema será:

$\{\begin{array}{c}\min f(x)\\ h_j(x)=0;j=1,\dots ,q\end{array}$

onde se supõe que $f,h_i:{ℝ}^n\mapsto ℝ$ são funções de classe ${𝒞}^2\left({ℝ}^n\right)$ e que para todo $\lambda \in ℝ$, o conjunto $\{x\in {ℝ}^n;f(x)\le \lambda \}$ é compacto (em inglês costuma-se usar a expressão inf-compact para descrever tais funções).

Sabe-se que a lagrangiana associada ao problema $(P)$ é:

$l:{ℝ}^n\times {ℝ}^q\mapsto ℝ$ dada por

$l(x,v)=f(x)+\sum _{j=1}^q{v}_j{h}_j(x)$.

e ainda, em uma notação mais sintética, considerando a função $H$ dada por:

$H:{ℝ}^n\mapsto {ℝ}^q$ definida por

$H(x)=\left[\begin{array}{c}{h}_1(x)\\ ⋮\\ h_q(x)\end{array}\right]$

tem-se a lagrangiana expressa da seguinte maneira:

$l(x,v)=f(x)+H(x{)}^{\mathrm{\top }}v$

Para o método da lagrangiana aumentada serão assumidas as seguintes hipóteses:

1. Se $\overline{x}$ é solução, então existe $\overline{u}\in {ℝ}^q$ tal que ${\mathrm{\nabla }}_{x}l(\overline{x},\overline{u})=0$;
2. Para todo $d=0$, o jacobiano de $H$ satizfaz:

$J_H(x)d=0\Rightarrow d^{\mathrm{\top }}{H}_x^{2}l(\overline{x},\overline{u})d>0$

Note que a segunda hipótese tem exatamente a mesma forma de uma das condições que aparece no lema de Finsler-Debreu.

Observe que é justamente a aparição do termo $\frac{\rho }{2}H(x{)}^{\mathrm{\top }}H(x)$ sendo somado à lagrangiana que justifica o nome lagrangiana aumentada.

Esse conceito possui algumas interpretações: Predefinição:Exercício Predefinição:Demonstração

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:

$(P_{\rho ,u})\{\begin{array}{c}\min l_{\rho }(x,u)\\ x\in {ℝ}^n\end{array}$

Algoritmo da lagrangiana aumentada

Dados $\rho >0$ e $ϵ\in (0,\rho )$.

Início: Tome $u_0\in {ℝ}^q$ e $k=0$.

Iteração: Calcule $x_k$, solução de $(P_{\rho ,u_k})$.
     Se $H(x_k)=0$, pare: $\overline{x}=x_k$.
     Senão, faça
           $u_{k+1}=u_k+ϵH(x_k)$
           $k=k+1$

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.

Predefinição:Teorema Observações:

• $X(\rho ,u)$ denota as soluções do problema;
• A igualdade ${\beta }_{\rho }(\overline{u})=f(\overline{x})$ 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.

O segundo teorema é: Predefinição:Teorema Observações:

• A propriedade 2 praticamente segue do fato de não haver salto de dualidade.

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 $\rho$ e de $\delta$ para que tal convergência ocorra.