Otimização/Métodos duais


Lagrangiana

editar

O conceito de lagrangiana está sempre relacionado ao seguinte problema:

 
Definição

A função lagrangiana associada ao problema   é

  definida por
 .

 
Wikipedia
A Wikipédia tem mais sobre este assunto:
Multiplicadores de Lagrange

Em alguns livros é usada a seguinte notação:

  definida por
 

e

  definida por
 

Deste modo, a lagrangiana fica expressa por

 

que é uma representação bem mais compacta.

Condições de otimalidade

editar

Para permitir a compreensão da importância da função lagrangiana em otimização, é preciso ter em mente os principais resultados que garantem a otimalidade de uma solução para o problema  . Nas próximas seções será apresentado um breve resumo das condições de otimalidade, dividindo-as em dois casos:

  • Caso particular: quando   é convexo e fechado.
  • Caso geral: quando   é arbitrário.

Caso particular

editar
Proposição

Seja   função de classe   no conjunto  . Se   é um minimizador local de   no conjunto convexo e fechado  , então:

 

Demonstração
Seja   uma solução de  , e fixe um ponto arbitrário  . Denote por   a restrição da função   sobre o segmento de reta que passa por   e por  , ou seja,
 , com  .

Note que  .

Como   é um minimizador de   em  , tem-se:

 , para todo  

Logo,

 , ou seja,  

Mas pela regra da cadeia,

 , então  .

Como   era arbitrário, o resultado está demonstrado.

Observação

A condição   significa que os vetores   e   formam um ângulo reto ou agudo (menor ou igual a 90 graus), conforme indicado na figura a seguir:

 
Em um ponto de mínimo,   sempre forma ângulo menor ou igual a 90 graus com os vetores do tipo  , onde   é um ponto de mínimo da função no conjunto viável   e   é um ponto qualquer deste conjunto.

No caso específico, com   e  ,   é a derivada direcional de   na direção  . Quando tal número é não negativo, intuitivamente a função cresce naquela direção.


Quando   é um conjunto convexo e fechado, a existência de uma solução para o problema   é garantida pela seguinte proposição:

Proposição

Se  ,   é convexa e

 
então   é um minimizador global de   no conjunto   (isto é,   é solução de  ).

Demonstração
Pela convexidade de  , tem-se que:
 

Logo,

 

Portanto,  , ou seja,   é um minimizador de   em  .

Até aqui, não é exigido que qualquer das funções   ou   sejam diferenciáveis. Isto será utilizado mais adiante, nos algoritmos.

A próxima proposição fornece uma caracterização dos minimizadores, em termos do conceito de projeção.

Lembre-se que a projeção de um ponto   sobre o conjunto  , denotada por  , satisfaz  . Na verdade, vale:

 
 
O vetor   forma ângulo menor que 90 graus com o vetor  , pois   é a projeção de   sobre o conjunto  .
Proposição

Seja   um número real fixado.

  1. Se   é um minimizador local de   em  , então  
  2. Se   é convexa e  , então   é um minimizador global de   em  .

Demonstração
(1)

Como   é um minimizador local de   em  , então

 

Observe que essa desigualdade equivale à

 

ou ainda

 

Tomando   e  , tem-se a equivalência com:

 

que equivale a dizer que  , ou seja:

 

(2)

Reciprocamente, supor que  , conforme a argumentação anterior, equivale a dizer que

 

Usando a hipótese de que   é convexa, segue da proposição anterior que   é um minimizador global de   em  .

Caso geral

editar

Para tratar este caso, é preciso utilizar o conceito de cone tangente. O conjunto contínua o mesmo, ou seja,  , embora não seja mais suposto que ele é convexo. Mesmo assim,   ainda será fechado, pois as funções   e   que o definem são contínuas.

Teorema

  1. Se   é um minimizador local de   em  , então  .
  2. Se   é convexo,   é convexa e  , então   é minimizador global de   em  .

Este teorema pode ser demonstrado de forma análoga a que foi feita anteriormente.

Demonstração
Esta demonstração é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

Seja   definido como:

 .

Pela segunda propriedade do cone tangente, tem-se:

 . Logo,
 

Em outras palavras, se é dado um conjunto   e depois se restringe tal conjunto para  , através do acréscimo de restrições inativas em um ponto  , os cones tangentes aos dois conjuntos (no ponto  ) coincidem.

Definição

Toda condição que implica que   é chamada de condição de qualificação das restrições.

 
Wikipedia

Observação: Também se pode dizer condições de regularidade das restrições (do inglês, Regularity conditions).

Exemplos de condições de qualificação das restrições

editar

(1) Se   e   são funções afim-lineares, então para qualquer  , tem-se  . Prova-se isso trivialmente

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

(2) Condições de Slater: Se as funções   são convexas e as   são afim lineares e, além disso, existe   tal que   para todo  ,  , então para qualquer  , tem-se  .

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

(3) Condições de Mangasarian-Fromowitz: Se   é linearmente independente e existe   tal que   para tpdp   e  .

Prova
Esta prova é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.
Teorema  (Karush–Kuhn–Tucker)

Suponha que  ,   e   são funções de classe   em uma vizinhança do ponto   e que  . Se   é um minimizador local de   em  , então existem   e   tais que:

  1.  
  2.  
  3.  

 
Wikipedia
A Wikipédia tem mais sobre este assunto:
Condições de Karush-Kuhn-Tucker

Note que aqui aparece a lagrangiana, pois a primeira condição é equivalente a:

 

O essencial para a existência de   é que  .

Teorema

Suponha-se que  ,   e   são funções de classe   em uma vizinhança de  , que   e   são convexas e que   são afim-lineares. são funções de classe  . Se existem   e   tais que:

  1.  
  2.  
  3.  
  4.  
  5.  

A partir deste teorema são construídos alguns algoritmos.


  Este módulo tem a seguinte tarefa pendente: Confrontar as informações presentes nestes últimos teoremas com algum livro. Parece estar precisando de pequenas correções.

Considere o seguinte problema:

 

Sabe-se que   dada por

 .

Agora, tem-se as KKT:

Teorema

Supondo que   e   são de classe   em uma vizinhança de   e que  , se   é um minimizador local de   em  , então   tal que   de modo que:

  1.  
  2.  
  3.  
  4.  
  5.  

Uma inequação sobre ínfimos e supremos

editar
Teorema

Sejam   e   dois subconjuntos arbitrários e considere uma aplicação  . Então

 


Demonstração
Sabe-se que
 ,

quaisquer que sejam  . Então, calculando o ínfimo em ambos os membros (com relação aos valores de  ), e considerando que   pode ser ilimitado inferiormente, tem-se para qualquer  :

 

Assim, calculando o supremo (com relação aos valores de  ), segue das desigualdades anteriores:

 
Exercício

Verifique que:

 

Demonstração
Esta demonstração é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

Defina-se a função:

 , dada por
 

e também

 , dada por
 

Conforme o exercício anterior, tem-se então

 

Observando a relação entre essas funções, é natural considerar dois problemas de otimização:

 

e

 
Comentários
  1. As funções   e   são conhecidas na literatura como funções em dualidade (ou mais frequentemente, funções duais);
  2. O problema   é conhecido como problema primal, enquanto   é chamado de problema dual;
  3. Fazendo   e  , segue-se do exercício anterior que  ;
  4. A diferença   é chamada de brecha de dualidade, ou salto de dualidade (do inglês, skip duality);


Exercício

Verifique que:  

Resolução
Se   tem-se que   e  .

Substituindo na lagrangeana tem-se que   e tomando  , se vê que o supremo dos valores   é atingido, tendo   como valor.

Por outro lado, se   existe um índice   tal que   e/ou  . No primeiro caso, seja   e

 , onde  .

Com esta escolha, a lagrangiana será

 .

Tomando o limite quando   tem-se que  .

Para o outro caso a prova é análoga.

Exercício

Verifique que   consiste de maximizar uma função côncava em um poliedro. Lembre-se:

  1. Uma função   é côncava quando   for convexa.
  2. Um poliedro é qualquer intersecção finita de semiespaços fechados.

Resolução
Primeiro será mostrado que : , dada por   é uma função côncava. Para isso, basta mostrar que para cada   vale
 .

Chamando   e   tem-se:

 

Quanto ao conjunto ser um poliedro, isso segue do fato de   e   serem interseções finitas de semiespaços fechados.


Exemplo numérico: problema primal e seu dual

editar

Considere o problema

 
Resolução
 

O problema é ilustrado na imagem a direita.

Primeiramente, é preciso identificar quais são as funções   e   envolvidas:

  • A função objetivo é aquela que se pretende minimizar, ou seja,  ;
  • Como aparecem apenas restrições de desigualdade, não há qualquer função  ;
  • Reescrevendo as desigualdades como   e  , conclúi-se que as funções   são:
  e  .

Neste caso, a lagrangiana é:

 , dado por
 

Em seguida, é preciso calcular   e  :

 , é dada por
 

E, conforme um dos exercícios anteriores (ou através de uma breve análise dos supremos envolvidos na expressão anterior), tem-se:

 

Analogamente, tem-se:

 , dada por
 

Observe que em relação a  , tem-se uma função fortemente convexa, que portanto possui um único minimizador. Além disso,   é diferenciável, donde o seu único minimizador   é dado pela equação:

 

ou seja,

 

donde

 

Portanto,

 

Assim, os problemas em dualidade são:

 

e

 

Pelo primeiro item do exercício, tem-se que a minimização do problema   é equivalente à minimização do problema original.

Por outro lado, através da lagrangiana, obtem-se além do problema primal  , um problema dual  , cuja estrutura é muito melhor que a do original (pois pelo outro exercício, consiste da maximização de uma função côncava   em um poliedro), e que servirá para encontrar o mínimo do problema primal (e consequentemente, do original).

Ponto de sela

editar

Este é um conceito muito importante relacionado à lagrangiana.

Definição

Dado o problema   e a lagrangiana   associada a esse problema, se diz que   é um ponto de sela de   se   e:

 .

Teorema

O ponto   é um ponto de sela de   se, e somente se:

  1.   é solução de  ;
  2.   é solução de  ;
  3.  .

Demonstração
Se   é um ponto de sela de  , então   e se tem:
 .

Em particular, como

 .

segue da segunda desigualdade que

 

e calculando o ínfimo sobre todos os   tem-se:

 

Por outro lado, da inequação sobre ínfimos e supremos, tem-se  , então  .

Logo, todos os membros das desigualdades acima coincidem, ou seja,

 

Mas da definição de   tem-se:

 .

Portanto,   é solução do problema   enquanto   significa que   é solução de  


Reciprocamente, supondo que   é solução do problema  , tem-se:

 

e admitindo que   é solução do problema  , segue:

 

Além disso, usando como hipótese que  , segue da definição que:

 , quaisquer que sejam  .

Em particular, tomando  ,   e  , resulta:

 , ou seja,

 

Logo, pela definição de   tem-se:

 , quaisquer que sejam  .

Portanto,   é um ponto de sela da lagrangiana  .


 
Wikipedia
A Wikipédia tem mais sobre este assunto:
Ponto de sela

Exemplos

editar

Considere novamente o problema de otimização dado por:

 

Verificar se a lagrangiana associada à   tem ponto de sela.


Resolução
 

O problema é ilustrado na imagem a direita, e conforme foi deduzido anteriormente, tem-se:

  •  
  •  
  •  
  •  

Além disso, como foi mostrado anteriormente, vale

 

e também

 

ou seja,

 

Agora, consideram-se os seguintes problemas em dualidade:

 

e

 

Donde   é solução do problema primal, e  .

Intuitivamente, nos pontos em que   assumir seu valor máximo, deve-se ter  , pois conforme   aumenta,   decresce.

Mas pela desigualdade a respeito de supremos e ínfimos, tem-se  , quaisquer que sejam  ,  .

Como  , e ao tomar   e   tem-se  , segue-se que   é uma solução do problema dual  .

Finalmente, como  , e  , segue que  . Portanto, pelo teorema anterior, o ponto   é ponto de sela da lagrangiana  .


Análise do problema

editar

Considerando  ,  ,   e  , se   é uma solução do problema dual, considere o seguinte problema:

 

que no caso do exemplo reduz-se a

 

A solução deste problema é obtida resolvendo  , sendo portanto  . Note que esta é a solução do problema primal   (e consequentemente do problema original  ).

Será apenas uma coincidência? Ou ainda, em que situações a solução deste último problema será também solução do problema original?

A resposta será dada pelo próximo teorema. Acompanhe.

Teorema  (dualidade lagrangiana convexa)

Suponha-se que   são de classe   e convexas, e que as funções   são afim lineares e  . Nestas condições:

  1. Se o problema   tem solução, então   e os problemas   e   têm solução.
  2. Se   tem solução, e   é solução de  , então as soluções de   são as soluções de  , onde
 
que também são as soluções de  .

Antes da demonstração, vale a pena imaginar a seguinte aplicação da segunda parte do teorema: Se por alguma razão não se sabe resolver o problema original  , pode-se optar por resolver   (um problema concavo em um poliedro), e depois resolver   (que é um problema convexo sem restrições). Em outras palavras, é possível trocar um problema difícil por dois problemas mais fáceis,   e  .

Agora a demonstração do teorema:

Demonstração
(1) Como   tem solução, seja   uma solução de  . Pelo teorema de KKT (que se aplica pois as funções são de classe   e se tem a qualificação das restrições), segue a existência de   e  , tais que:
  1.  
  2.  
  3.  
  4.  
  5.  

Como   são funções convexas e   afim lineares, então a função lagrangiana   é convexa em   (pela forma de  ). Isto significa que:

 .

Usando (1), conclúi-se uma das duas desigualdades que definem um ponto de sela em  :

 .

Considerando que   é solução de  , tal ponto satisfaz as restrições   e  . Então, usando  , segue que:

 

pois   e  .

Mas, por KKT,  . Além disso,  .

Logo:

 

Assim,

 

quaisquer que sejam  ,   e  . Mas isso implica, por definição, que   é um ponto de sela de  .

Logo,  ,   é solução do problema primal   e   é solução do problema dual  

(2)Seja   solução de   (que existe, pelo item 1). Sabe-se pelo item anterior que o problema primal   tem solução e que  .

Seja   solução de  . Então,   é ponto de sela de  , logo valem as desigualdades:

 .

Uma vez que   está fixo e a segunda desigualdade vale para qualquer  , conclui-se que   é solução do problema

 

As soluções deste problema são soluções de   e, consequentemente, do problema original.

Exercício

Verificar se existe salto de dualidade nos problemas em dualidade para o seguinte problema de minimização:

 

Exercício

Juntamente com o problema   do exercício anterior, considere o seguinte problema:

 
Os problemas são equivalentes? (no sentido de que têm as mesmas funções objetivo e o mesmo conjunto de restrições) O que acontece com relação às condições de KKT? Apesar de   não ser convexa, é válido o resultado do teorema? Para que serve KKT? É possível resolver o problema dual e usar a resposta para resolver o primal?

Exercício

Experimente escolher   e uma transformação linear, e um poliedro (intersecção finita de semi-espaços). É difícil de resolver o problema primal. Tente resolver o dual, usando os métodos conhecidos.

A seguir será apresentada uma proposição que responde a uma pergunta deixada anteriormente:

Proposição

Considere o problema   a lagrangiana   e os problemas em dualidade   e   e   soluções de  . Se   é solução do problema

 
  (o conjunto dos pontos que satisfazem as restrições) e  , então   é também uma solução do problema  .

Tal proposição fornece um roteiro para quem precisa resolver o problema   relativamente difícil:

  1. Primeiramente, resolve-se  ;
  2. Depois, constrói-se o problema   e encontra-se uma solução   para o mesmo;
  3. Finalmente, se   satisfaz as últimas condições da proposição, ele é também uma solução de  .
Demonstração
Se   é uma solução de  ,  . Então, pela definição de  , tem-se:
 

Como   é solução de  , então:

 

ou seja,

 

Portanto,

 

Por outro lado, como  , tem-se   e  .

Por hipótese,  , então

 

Logo,

 .

Então para   tem-se que   e  . Consequentemente,

 

quaisquer que sejam  , ou seja,

 ,

quaisquer que sejam  .

Portanto,   é ponto de sela de  , e assim,   é solução primal (solução de  ), e em consequência, solução de  .


Resumo do esquema de dualidade

editar

Neste ponto, pode-se sintetizar a estratégia geral para a resolução de problemas de otimização utilizando esquemas de dualidade.

Considere o problema

 

onde   são funções de classe  , e seja a lagrangiana   definido por

 .

Convenciona-se que:

  •   é a variável primal;
  •   é a variável dual;

Nesse sentido, "o   é o dual de  " (não confundir com o significado que essa expressão teria na análise funcional. Ver nota sobre a terminologia), ou seja:

  •   é onde "mora" a variável primal  ;
  •   é onde "mora" a variável dual  ;

Definem-se então as funções   e   da seguinte maneira:

 , dada por
 

e

 , dada por
 

A partir destas duas funções, formulam-se os seguintes problemas duais:

 

e

 

É possível verificar que   equivale ao problema original   e que   consiste da maximização de uma função côncava em um poliedro (convexo).

Logo, o dual de   é  .

Conclusões

editar

Dado qualquer problema  , seu dual   é um problema côncavo (isto é, a função objetivo é côncava), tal que os pontos satisfazendo o conjunto de restrições formam um poliedro convexo.

Apesar da controvérsia filosófica existente acerca do nome destes conceitos (coisa que poderia muito bem vir a ser alterada no futuro), a moral da história é que "transforma-se um problema geralmente difícil (sem estrutura) em um problema mais fácil (cheio de estrutura)".

Uma nota sobre a terminologia

editar

Na subárea da matemática denominada Análise Funcional, quando se tem um espaço topológico  , costuma-se chamar de dual topológico ao conjunto  .

Aparentemente, os conceitos de dual da otimização e da análise funcional não tem relação um com o outro.

Um dos primeiros a falar de dualidade (espaços duais) foi o francês Fenchel, mas foi fortemente criticado por Urruty e Lemaréchal, pois os dois conceitos de dualidade não estão relacionados. Também o francês Brezis concordou que há um problema a ser resolvido com a nomenclatura, e um dos conceitos deveria deixar de ser chamado assim.

 
Wikipedia
A Wikipédia tem mais sobre este assunto:
Análise funcional