# Otimização/Método da lagrangiana aumentada

O problema a ser resolvido é:
    $\left\{{\begin{matrix}\min f(x)\\h_{j}(x)=0;j=1,\ldots ,q\end{matrix}}\right.$
Sabe-se que se for aplicado o método da lagrangiana, será considerada a função:
    $l:\mathbb {R} ^{n}\times \mathbb {R} ^{q}\mapsto \mathbb {R}$ dada por
    $l(x,v)=f(x)+\sum _{j=1}^{q}v_{j}h_{j}(x)$.
e também
    $\beta :\mathbb {R} ^{q}\mapsto \mathbb {R} \cup \{-\infty \}$, dada por
    $\beta (v)=\inf _{x\in \mathbb {R} ^{n}}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}\left(h_{j}(x)\right)^{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:

## Lema (Finsler-Debreu)

Seja $A_{n\times n}$ uma matriz simétrica e $B_{p\times n}$. As seguintes afirmações são equivalentes:
* Se $Bx=0$, com $x\not =0$, então $\langle Ax,x\rangle >0$;
* Existe $r>0$ tal que a matriz $A+rB^{\top }B$ é definida positiva;
* Existe $s>0$ tal que a matriz $A+rB^{\top }B$ é definida positiva para todo $r>s$.

## Exercício

Prove a seguinte variante do lema anterior:
    Seja $A_{n\times n}$ uma matriz simétrica e semi-definida positiva, e $B_{p\times n}$. As seguintes afirmações são equivalentes:
   * Se $Bx=0$, com $x\not =0$, então $\langle Ax,x\rangle >0$;
   * Existe $r>0$ tal que a matriz $A+rB^{\top }B$ é definida positiva;
   * Para todo $r>0$, a matriz $A+rB^{\top }B$ é definida positiva.
A partir de agora, o problema será:
    $\left\{{\begin{matrix}\min f(x)\\h_{j}(x)=0;j=1,\ldots ,q\end{matrix}}\right.$
onde se supõe que $f,\,h_{i}:\mathbb {R} ^{n}\mapsto \mathbb {R}$ são funções de classe ${\mathcal {C}}^{2}\left(\mathbb {R} ^{n}\right)$ e que para todo $\lambda \in \mathbb {R}$, o conjunto $\{x\in \mathbb {R} ^{n};f(x)\leq \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:\mathbb {R} ^{n}\times \mathbb {R} ^{q}\mapsto \mathbb {R}$ 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:\mathbb {R} ^{n}\mapsto \mathbb {R} ^{q}$ definida por
    $H(x)={\begin{bmatrix}h_{1}(x)\\\vdots \\h_{q}(x)\end{bmatrix}}$
tem-se a lagrangiana expressa da seguinte maneira:
    $l(x,v)=f(x)+H(x)^{\top }v$
Para o método da lagrangiana aumentada serão assumidas as seguintes hipóteses:
* Se ${\bar {x}}$ é solução, então existe ${\bar {u}}\in \mathbb {R} ^{q}$ tal que $\nabla _{x}l({\bar {x}},{\bar {u}})=0$;
* Para todo $d\not =0$, o jacobiano de $H$ satizfaz:
    $J_{H}(x)d=0\Rightarrow d^{\top }H_{x}^{2}l({\bar {x}},{\bar {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.

## Definição

Dado $\rho >0$, se define a lagrangiana aumentada para o problema $(P)$ como:
    $l_{\rho }:\mathbb {R} ^{n}\times \mathbb {R} ^{q}\mapsto \mathbb {R}$ dada por
    $l_{\rho }(x,v)=f(x)+H(x)^{\top }v+{\frac {\rho }{2}}H(x)^{\top }H(x)=l(x,v)+{\frac {\rho }{2}}H(x)^{\top }H(x)$
Observe que é justamente a aparição do termo ${\frac {\rho }{2}}H(x)^{\top }H(x)$ sendo somado à lagrangiana que justifica o nome lagrangiana aumentada.
Esse conceito possui algumas interpretações:

## Exercício

Verifique que a lagrangiana aumentada $l_{\rho }$ é justamente a lagrangiana do problema $(P)$ penalizado, ou seja, de
    $\left\{{\begin{matrix}\min f(x)+{\frac {\rho }{2}}H(x)^{\top }H(x)\\H(x)=0\end{matrix}}\right.$

## Exercício

Verifique que a função dual $\beta _{\rho }$ (o ínfimo da lagrangiana aumentada em relação à primeira componente), dada por
    $\beta _{\rho }:\mathbb {R} ^{q}\mapsto \mathbb {R} \cup \{-\infty \}$, com
    $\beta _{\rho }(v)=\inf _{x\in \mathbb {R} ^{n}}l_{\rho }(x,v)$
para $0<\rho <\delta$ satisfaz
    $\beta _{\rho }(v)\leq \beta _{\delta }(v)\leq f({\bar {x}})$
${\bar {x}}$
$(P)$

## Exercício

Verifique que $\{x\in \mathbb {R} ^{n};l_{\rho }(x,v)\leq \lambda \}$ é compacto, qualquer que seja $\lambda \in \mathbb {R}$ e $v\in \mathbb {R} ^{q}$.

## Proposição

Se ${\bar {x}}$ é solução de $(P)$, então existe algum $\rho _{0}>0$, algum $\delta _{0}>0$ e alguma vizinhança $X_{0}$ de ${\bar {x}}$ tais que $l_{\rho _{0}}(\cdot ,{\bar {v}})$ é fortemente convexa com parâmetro $\delta _{0}$.
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})\left\{{\begin{matrix}\min l_{\rho }(x,u)\\x\in \mathbb {R} ^{n}\end{matrix}}\right.$

## Algoritmo da lagrangiana aumentada

Dados $\rho >0$ e $\epsilon \in (0,\rho )$.
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 $\rho _{0}$, $\delta _{0}$ e $X_{0}$ como na proposição anterior. Se $U$ é uma vizinhança de ${\bar {u}}$, existe algum $\rho _{U}>\rho _{0}$ tal que:
* $X(\rho ,u)\subset X_{0},\forall u\in U$
* $X(\rho ,{\bar {u}})=\{{\bar {x}}\}$ e $\beta _{\rho }({\bar {u}})=f({\bar {x}})$
Observações:
* $X(\rho ,u)$ denota as soluções do problema;
* A igualdade $\beta _{\rho }({\bar {u}})=f({\bar {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 é:

### Teorema

Se $\rho$ é suficientemente grande e $\delta$ suficientemente pequeno, então:
* $x_{k}\to {\bar {x}}$
* $l_{\rho }(x_{k},u_{k})\to f({\bar {x}})$
* $\{u_{k}\}$ é limitada
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.

### Exercício

Argumente porque as hipóteses 1, 2 e 3 garantem que a iteração do algoritmo da Lagrangiana aumentada para problemas de minimização com restrições de igualdade tem uma única solução, sendo:
* Todas as funções são de classe ${\mathcal {C}}^{2}$ e a função objetivo tem todos os seus subníveis compactos.
* Se ${\bar {x}}$ é solução do problema, então existe ${\bar {u}}$ tal que o gradiente da Lagrangiana não aumentada com respeito a variável primal se anula em $({\bar {x}},{\bar {u}})$.
* A hessiana da Lagrangiana não aumentada com respeito a variável primal é definida positiva sob a variedade ortogonal de todos os gradientes no ponto ${\bar {x}}$ das restrições.