Otimização/Métodos duais

Origem: Wikilivros, livros abertos por um mundo aberto.


Lagrangiana[editar | editar código-fonte]

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

Definição

A função lagrangiana associada ao problema é

definida por
.

Wikipedia
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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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
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 | editar código-fonte]

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

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

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:

Uma inequação sobre ínfimos e supremos[editar | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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
Wikipedia
A Wikipédia tem mais sobre este assunto:
Ponto de sela

Exemplos[editar | editar código-fonte]

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 | editar código-fonte]

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:

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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
Wikipedia
A Wikipédia tem mais sobre este assunto:
Análise funcional