O problema a ser resolvido é:
![{\displaystyle \left\{{\begin{matrix}\min f(x)\\h_{j}(x)=0;j=1,\ldots ,q\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9553c0fa9e5067d1c65b921dd8f75146cfaea28d)
Sabe-se que se for aplicado o método da lagrangiana, será considerada a função:
dada por
.
e também
, dada por
![{\displaystyle \beta (v)=\inf _{x\in \mathbb {R} ^{n}}l(x,v)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2bb5f7578ed5aea6279a5a789f0c036f49cb609)
A grande dificuldade seria saber quando o valor de
é finito. Uma idéia seria modificar um pouco a lagrangiana (aumentando-a, com um termo extra), da seguinte maneira:
![{\displaystyle 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5796e627655ebc5d919af67f3552c2961b032444)
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:
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 , tal que a matriz é definida positiva. Logo, para concluir a outra implicação, basta notar que para qualquer vale:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84070ffffc608ef45f4ad23dc200cb42bcc73307)
Assim, (2) também implica (3).
Agora, será mostrado que de (2) se conclui (1). De fato, se , para algum , então:
![{\displaystyle \langle Ax,x\rangle =\langle Ax,x\rangle +r\|Bx\|^{2}=\langle (A+rB^{\top }B)x,x\rangle >0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4ff60b47b99ccbb0915501c02b335459ce9734d)
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 tal que , tem-se , e que fosse falsa a afirmação (3), existiria para cada algum e algum de modo que
![{\displaystyle \langle Ax,x\rangle +r\|Bx\|^{2}\leq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/839ed908466282d8e96fa41144362d972535efa5)
Neste caso, dividindo por , e denotando , segue que para cada , existe algum e algum , com , tais que
![{\displaystyle \langle Au_{k},u_{k}\rangle +r_{k}\|Bu_{k}\|^{2}\leq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/541363dbc26e50a65048c8406125584e5855341e)
Como todos os estão na esfera unitária, que é compacta, a sequência tem algum ponto de acumulação, por exemplo . Passando o limite em , e considerando apenas a subsequência de que converge para , tem-se
(pois )
e
![{\displaystyle \|Bu_{k}\|^{2}\to \|B{\bar {u}}\|^{2}\not =0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37ddf4258126b880d8004ed5b349bc24dbd587c0)
Neste caso,
![{\displaystyle \lim _{k\to +\infty }\langle Au_{k},u_{k}\rangle +r_{k}\|Bu_{k}\|^{2}\leq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6322e9a0d7437592e0883039d948badf8aeea8f6)
só é possível se , ou seja, se . Logo,
![{\displaystyle \langle A{\bar {u}},{\bar {u}}\rangle \leq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b6bc1b5f81a59124a70cb27931879e0fd3464d3)
contradizendo a hipótese (1).
|
A partir de agora, o problema será:
![{\displaystyle \left\{{\begin{matrix}\min f(x)\\h_{j}(x)=0;j=1,\ldots ,q\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9553c0fa9e5067d1c65b921dd8f75146cfaea28d)
onde se supõe que
são funções de classe
e que para todo
, o conjunto
é 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
é:
dada por
.
e ainda, em uma notação mais sintética, considerando a função
dada por:
definida por
![{\displaystyle H(x)={\begin{bmatrix}h_{1}(x)\\\vdots \\h_{q}(x)\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb39d21db1cbcd145086f982011cb0a4b156a8d7)
tem-se a lagrangiana expressa da seguinte maneira:
![{\displaystyle l(x,v)=f(x)+H(x)^{\top }v}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6489155d5e524584a12ceceee81ddd8f0cdd34b9)
Para o método da lagrangiana aumentada serão assumidas as seguintes hipóteses:
- Se
é solução, então existe
tal que
;
- Para todo
, o jacobiano de
satizfaz:
![{\displaystyle J_{H}(x)d=0\Rightarrow d^{\top }H_{x}^{2}l({\bar {x}},{\bar {u}})d>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2eb7ac769acb798abd587cd4d06c6d368a1a032b)
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
sendo somado à lagrangiana que justifica o nome lagrangiana aumentada.
Esse conceito possui algumas interpretações:
- Exercício
Verifique que a lagrangiana aumentada
é justamente a lagrangiana do problema
penalizado, ou seja, de
![{\displaystyle \left\{{\begin{matrix}\min f(x)+{\frac {\rho }{2}}H(x)^{\top }H(x)\\H(x)=0\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5005bcc3318762987d7f717510458bfb67f8845)
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
(o ínfimo da lagrangiana aumentada em relação à primeira componente), dada por
, com
![{\displaystyle \beta _{\rho }(v)=\inf _{x\in \mathbb {R} ^{n}}l_{\rho }(x,v)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cb34b3be4c9321e9e07ee927d89e2849d6eedde)
para
![{\displaystyle 0<\rho <\delta }](https://wikimedia.org/api/rest_v1/media/math/render/svg/e354d7ca12b9d5cc0ca99f4126932bbb2d2ef7b0)
satisfaz
![{\displaystyle \beta _{\rho }(v)\leq \beta _{\delta }(v)\leq f({\bar {x}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abc60d5a349a4f50b97afa4cbbd541aa677834f8)
onde
![{\displaystyle {\bar {x}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/466e03e1c9533b4dab1b9949dad393883f385d80)
é solução de
Demonstração
|
E a segunda desigualdade
.
|
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.
|
Demonstração
|
Conforme o lema de Finsler-Debreu, a hipótese (2), segundo a qual para todo , o jacobiano de satizfaz:
![{\displaystyle J_{H}(x)d=0\Rightarrow d^{\top }H_{x}^{2}l({\bar {x}},{\bar {u}})d>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2eb7ac769acb798abd587cd4d06c6d368a1a032b)
equivale a dizer que existe algum tal que é definida positiva.
Mas a Hessiana de é dada por . Logo, a hipótese equivale a dizer que é definida positiva.
Considere agora a função definida por
![{\displaystyle \delta (d,x)=d^{\top }\nabla _{x}^{2}l_{\rho }(x,{\bar {u}})d}](https://wikimedia.org/api/rest_v1/media/math/render/svg/78bc50a59bf241d7b5ec4b624a8023204346c0c5)
Logo, para qualquer , tomando , tem-se
![{\displaystyle \delta (d,x)=\delta (d,{\bar {x}})=d^{\top }\nabla _{x}^{2}l_{\rho }({\bar {x}},{\bar {u}})d>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cb3d6970ae99ff251ed4287399c3d977e752f90)
Pela continuidade da função , existe uma vizinhança de tal que para todo ponto , e qualquer que seja . Além disso, tal vizinhança pode ser tomada aberta, convexa e suficientemente pequena para que .
Assim, tomando o ínfimo, pode-se definir como
![{\displaystyle \delta _{0}=\inf _{\begin{smallmatrix}x\in X_{0}\\\|d\|=1\end{smallmatrix}}\delta (d,x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d75f248205ac2d6885bfa1fb2ba1f20302d70693)
Então
![{\displaystyle \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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bdb9126a2192e0bed39cefbb60cfddb80c4693c2)
quaisquer que sejam e .
Portanto,
![{\displaystyle d^{\top }\left[\nabla _{x}^{2}l_{\rho _{0}}(x,{\bar {u}})\right]d\geq \delta _{0}\|d\|^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e0dc529c58b0c0a92681dd54e4af48d6cd9b292)
ou seja, os auto-valores de são todos positivos.
Para concluir que é fortemente convexa, basta recordar-se de dois fatos:
- Uma função
de classe é convexa se, e somente se, é semidefinida positiva;
- Uma função
é fortemente convexa se, e somente se, existe uma constante tal que é convexa, ou seja, .
Com isso, é fortemente convexa pois
![{\displaystyle d^{\top }\left[\nabla _{x}^{2}l_{\rho _{0}}(x,{\bar {u}})\right]d-\delta _{0}\|d\|^{2}\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d818ee502253f71d5f3485d5df365de3a29f34ae)
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 é fortemente convexa em .
|
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:
![{\displaystyle (P_{\rho ,u})\left\{{\begin{matrix}\min l_{\rho }(x,u)\\x\in \mathbb {R} ^{n}\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b5dbc8c864c94ff59257d027e041787631d48ed1)
Dados
e
.
Início: Tome
e
.
Iteração: Calcule
, solução de
.
Se
, pare:
.
Senão, faça
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.
Observações:
denota as soluções do problema;
- A igualdade
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 é:
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
e de
para que tal convergência ocorra.