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:

1. Se $Bx=0$, com $x\not =0$, então $\langle Ax,x\rangle >0$;
2. Existe $r>0$ tal que a matriz $A+rB^{\top }B$ é definida positiva;
3. Existe $s>0$ tal que a matriz $A+rB^{\top }B$ é definida positiva para todo $r>s$.

Demonstração

Primeiramente, será mostrado que a afirmação (2) é equivalente à afirmação (3). Obviamente, (3) implica em (2). Por outro lado, supondo que se tem (2), existe algum $s>0$, tal que a matriz $A+sB^{\top }B$ é definida positiva. Logo, para concluir a outra implicação, basta notar que para qualquer $x\not =0$ vale: ${\begin{aligned}\langle (A+rB^{\top }B)x,x\rangle &=\langle Ax,x\rangle +r\langle B^{\top }Bx,x\rangle \\&=\langle Ax,x\rangle +r\langle Bx,Bx\rangle \\&=\langle Ax,x\rangle +r\|Bx\|^{2}\\&>\langle Ax,x\rangle +s\|Bx\|^{2},\,\forall r>s\\&=\langle (A+sB^{\top }B)x,x\rangle \\&>0\end{aligned}}$ Assim, (2) também implica (3). Agora, será mostrado que de (2) se conclui (1). De fato, se $Bx=0$, para algum $x\not =0$, então: $\langle Ax,x\rangle =\langle Ax,x\rangle +r\|Bx\|^{2}=\langle (A+rB^{\top }B)x,x\rangle >0$ Finalmente, será garantido que se vale (1) então vale (3) (ver também página 25, de Izmailov & Solodov (2007)). Isso será mostrado por contradição, ou seja, supondo que vale (1) e que mesmo assim, não seja válido (3). Se disso seguir uma contradição, a implicação desejada é verdadeira. Supondo que para todo $x\not =0$ tal que $Bx=0$, tem-se $\langle Ax,x\rangle >0$, e que fosse falsa a afirmação (3), existiria para cada $s>0$ algum $r>s$ e algum $x\not =0$ de modo que $\langle Ax,x\rangle +r\|Bx\|^{2}\leq 0$ Neste caso, dividindo por $\|x\|^{2}$, e denotando $u={\frac {x}{\|x\|}}$, segue que para cada $k\in \mathbb {N}$, existe algum $r_{k}>k$ e algum $u_{k}\in \mathbb {R} ^{n}$, com $\|u_{k}\|=1$, tais que $\langle Au_{k},u_{k}\rangle +r_{k}\|Bu_{k}\|^{2}\leq 0$ Como todos os $u_{k}$ estão na esfera unitária, que é compacta, a sequência $\{u_{k}\}$ tem algum ponto de acumulação, por exemplo ${\bar {u}}$. Passando o limite em $k$, e considerando apenas a subsequência de $\{u_{k}\}$ que converge para ${\bar {u}}$, tem-se $r_{k}\to +\infty$ (pois $r_{k}>k$) $\langle Au_{k},u_{k}\rangle \to \langle A{\bar {u}},{\bar {u}}\rangle$ e $\|Bu_{k}\|^{2}\to \|B{\bar {u}}\|^{2}\not =0$ Neste caso, $\lim _{k\to +\infty }\langle Au_{k},u_{k}\rangle +r_{k}\|Bu_{k}\|^{2}\leq 0$ só é possível se $\|B{\bar {u}}\|^{2}=0$, ou seja, se $B{\bar {u}}=0$. Logo, $\langle A{\bar {u}},{\bar {u}}\rangle \leq 0$ contradizendo a hipótese (1).

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:

1. Se $Bx=0$, com $x\not =0$, então $\langle Ax,x\rangle >0$;
2. Existe $r>0$ tal que a matriz $A+rB^{\top }B$ é definida positiva;
3. 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:

1. Se ${\bar {x}}$ é solução, então existe ${\bar {u}}\in \mathbb {R} ^{q}$ tal que $\nabla _{x}l({\bar {x}},{\bar {u}})=0$;
2. 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.$

Demonstração
Basta notar que dentro do conjunto viável as funções objetivos são iguais.

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}})$

onde ${\bar {x}}$ é solução de $(P)$

Demonstração

${\begin{aligned}\beta _{\rho }(v)&=\inf _{x\in \mathbb {R} ^{n}}l_{\rho }(x,v)\\&=\inf _{x\in \mathbb {R} ^{n}}[f(x)+H(x)^{\top }v+{\frac {\rho }{2}}H(x)^{\top }H(x)]\\&\leq \inf _{x\in \mathbb {R} ^{n}}[f(x)+H(x)^{\top }v+{\frac {\delta }{2}}H(x)^{\top }H(x)]\\&=\inf _{x\in \mathbb {R} ^{n}}l_{\delta }(x,v)\\&=\beta _{\delta }(v)\end{aligned}}$ E a segunda desigualdade $\beta _{\delta }(v)=\inf _{x\in \mathbb {R} ^{n}}l_{\delta }(x,v)\leq l_{\delta }({\bar {x}},v)=f({\bar {x}})$.

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}$.

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.

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}$.

Demonstração

Conforme o lema de Finsler-Debreu, a hipótese (2), segundo a qual 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$ equivale a dizer que existe algum $\rho _{0}>0$ tal que $\nabla _{x}l({\bar {x}},{\bar {v}})+\rho _{0}\left(J_{H}(x)\right)^{\top }\left(J_{H}(x)\right)$ é definida positiva. Mas a Hessiana de $l_{\rho _{0}}$ é dada por $\nabla _{x}^{2}l_{\rho _{0}}({\bar {x}},{\bar {v}})=\nabla _{x}^{2}l({\bar {x}},{\bar {v}})+\left(J_{H}(x)\right)^{\top }\left(J_{H}(x)\right)$. Logo, a hipótese equivale a dizer que $\nabla _{x}^{2}l_{\rho _{0}}({\bar {x}},{\bar {v}})$ é definida positiva. Considere agora a função $\delta :\mathbb {R} ^{n}\times \mathbb {R} ^{n}\mapsto \mathbb {R}$ definida por $\delta (d,x)=d^{\top }\nabla _{x}^{2}l_{\rho }(x,{\bar {u}})d$ Logo, para qualquer $d\not =0$, tomando $x={\bar {x}}$, tem-se $\delta (d,x)=\delta (d,{\bar {x}})=d^{\top }\nabla _{x}^{2}l_{\rho }({\bar {x}},{\bar {u}})d>0$ Pela continuidade da função $\delta$, existe uma vizinhança $X_{0}$ de ${\bar {x}}$ tal que $\delta (d,x)>0$ para todo ponto $x\in X_{0}$, e qualquer que seja $d\not =0$. Além disso, tal vizinhança pode ser tomada aberta, convexa e suficientemente pequena para que $\delta (d,x)\geq \epsilon >0$. Assim, tomando o ínfimo, pode-se definir $\delta _{0}$ como $\delta _{0}=\inf _{\begin{smallmatrix}x\in X_{0}\\\|d\|=1\end{smallmatrix}}\delta (d,x)$ Então $\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)\geq \delta _{0}$ quaisquer que sejam $d\not =0$ e $x\in X_{0}$. Portanto, $d^{\top }\left[\nabla _{x}^{2}l_{\rho _{0}}(x,{\bar {u}})\right]d\geq \delta _{0}\|d\|^{2}$ ou seja, os auto-valores de $\nabla _{x}^{2}l_{\rho _{0}}(x,{\bar {u}})$ são todos positivos. Para concluir que $l_{\rho _{0}}(\cdot ,{\bar {u}})$ é fortemente convexa, basta recordar-se de dois fatos: Uma função $f$ de classe ${\mathcal {C}}^{2}$ é convexa se, e somente se, $\nabla ^{2}f$ é semidefinida positiva; Uma função $f$ é fortemente convexa se, e somente se, existe uma constante $\alpha >0$ tal que $f(x)-{\frac {\alpha }{2}}\|x\|^{2}$ é convexa, ou seja, $d^{\top }\nabla ^{2}f(x)d-\alpha \|x\|^{2}\geq 0$. Com isso, $l_{\rho _{0}}(\cdot ,{\bar {u}})$ é fortemente convexa pois $d^{\top }\left[\nabla _{x}^{2}l_{\rho _{0}}(x,{\bar {u}})\right]d-\delta _{0}\|d\|^{2}\geq 0$ 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 $l_{\rho _{0}}$ é fortemente convexa em $X_{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 )$.

Início: Tome $u_{0}\in \mathbb {R} ^{q}$ e $k=0$.

Iteração: Calcule $x_{k}$, solução de $(P_{\rho ,u_{k}})$.
     Se $H(x_{k})=0$, pare: ${\bar {x}}=x_{k}$.
     Senão, faça
           $u_{k+1}=u_{k}+\epsilon 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.

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:

1. $X(\rho ,u)\subset X_{0},\forall u\in U$
2. $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.

Prova
Esta prova é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

O segundo teorema é:

Teorema

Se $\rho$ é suficientemente grande e $\delta$ suficientemente pequeno, então:

1. $x_{k}\to {\bar {x}}$
2. $l_{\rho }(x_{k},u_{k})\to f({\bar {x}})$
3. $\{u_{k}\}$ é limitada

Observações:

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

Justificativa
Fica a cargo do leitor justificar este fato. Sinta-se livre para melhorar a qualidade deste texto, incluindo a justificativa neste módulo.

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:

1. Todas as funções são de classe ${\mathcal {C}}^{2}$ e a função objetivo tem todos os seus subníveis compactos.
2. 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}})$.
3. 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.