Otimização/Método da lagrangiana aumentada


O problema a ser resolvido é:

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

dada por
.

e também

, dada por

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:

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 uma matriz simétrica e . As seguintes afirmações são equivalentes:

  1. Se , com , então ;
  2. Existe tal que a matriz é definida positiva;
  3. Existe tal que a matriz é definida positiva para todo .

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:

Assim, (2) também implica (3).

Agora, será mostrado que de (2) se conclui (1). De fato, se , para algum , então:

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

Neste caso, dividindo por , e denotando , segue que para cada , existe algum e algum , com , tais que

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

Neste caso,

só é possível se , ou seja, se . Logo,

contradizendo a hipótese (1).


Exercício

Prove a seguinte variante do lema anterior:

Seja uma matriz simétrica e semi-definida positiva, e . As seguintes afirmações são equivalentes:
  1. Se , com , então ;
  2. Existe tal que a matriz é definida positiva;
  3. Para todo , a matriz é definida positiva.

A partir de agora, o problema será:

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

tem-se a lagrangiana expressa da seguinte maneira:

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

  1. Se é solução, então existe tal que ;
  2. Para todo , o jacobiano de satizfaz:

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 , se define a lagrangiana aumentada para o problema como:

dada por

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

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
para satisfaz
onde é solução de

Demonstração

E a segunda desigualdade

.


Exercício

Verifique que é compacto, qualquer que seja e .

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 é solução de , então existe algum , algum e alguma vizinhança de tais que é fortemente convexa com parâmetro .

Demonstração
Conforme o lema de Finsler-Debreu, a hipótese (2), segundo a qual para todo , o jacobiano de satizfaz:

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

Logo, para qualquer , tomando , tem-se

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

Então

quaisquer que sejam e .

Portanto,

ou seja, os auto-valores de são todos positivos.

Para concluir que é fortemente convexa, basta recordar-se de dois fatos:

  1. Uma função de classe é convexa se, e somente se, é semidefinida positiva;
  2. Uma função é fortemente convexa se, e somente se, existe uma constante tal que é convexa, ou seja, .

Com isso, é fortemente convexa pois

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:

Algoritmo da lagrangiana aumentadaEditar

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.

Teorema

Sejam  ,   e   como na proposição anterior. Se   é uma vizinhança de  , existe algum   tal que:

  1.  
  2.   e  

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 é:

Teorema

Se   é suficientemente grande e   suficientemente pequeno, então:

  1.  
  2.  
  3.   é 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   e de   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   e a função objetivo tem todos os seus subníveis compactos.
  2. Se   é solução do problema, então existe   tal que o gradiente da Lagrangiana não aumentada com respeito a variável primal se anula em  .
  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   das restrições.