Otimização/Aplicações dos métodos duais

Aplicação à programação linear

editar

Considere um problema típico da programação linear como:

 

onde são dados  ,  ,  ,  ,  ,  ,   e  . Por simplicidade, pode-se ainda adotar a seguinte notação:

 

Nesta seção será mostrado como a "bonita teoria dos métodos duais" se aplica a esse tipo de problema.

Primeiramente, calcula-se a lagrangiana:

 

Note que:

  • As variáveis primais são   e  ;
  • As variáveis duais são  ,   e  ;

Agora é preciso identificar as funções   e   correspondentes a este problema. Conforme anteriormente, tem-se:

 , dada por
 

e

 , dada por
 

Logo, considerando que  , o problema dual consiste no seguinte:

 
Exercício

Verificar que   é uma solução de

 
se, e somente se,   é uma solução de
 

Resolução
Seja   uma solução de  . Então, por definição, tem-se para todo   que
 

mas isto equivale a

 

ou seja,   é uma solução de  .

Exercício

Verificar que:

 

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.

Exemplificando com um problema de programação linear

editar

O seguinte problema é chamado de problema standard (padrão) de programação linear:

 

onde são dados  ,   e  .

Calculando o dual de (PL)

editar

Primeiramente,

 

A função   não precisa ser calculada, pois já se mostrou que

 

Por outro lado, quanto à função   tem-se:

 
 

Logo, o problema dual é:

 

ou ainda

 

Calculando o dual do dual de (PL)

editar

Considere o seguinte problema:

 

que, conforme já foi mostrado em um exercício anteriormente, equivale a

 

A lagrangiana é dado por:

 

Logo,

 

Logo, o dual de   é:

 

ou seja,

 

que equivale a

 

Um exemplo numérico contextualizado

editar

Considere a seguinte situação:

Um empresário que produz cerveja dispões de 240 kg de milho, 5 kg de lúpulo e 596 kg de Malta. Para produzir um barril de cerveja preta requer 2,5 kg de milho, 0,125 kg de lúpulo e 17,5 kg de malta. Enquanto que para produzir um barril de cerveja branca, se precisa de 7,5 kg de milho, 0,125 kg de lúpulo e 10 kg de malta. Por barril de cerveja branca vendido, o empresário recebe 130 reais, enquanto por um barril de cerveja preta, recebe 230 reais. Achar o modelo matemático para otimizar o ganho do empresário.
Resolução
Primeiramente, é preciso identificar quais são as variáveis do problema, e quais são os dados. Pode-se adotar a seguinte notação para as quantidades dos dois tipos de cerveja:
  •  : Indica a quantidade (em litros) de cerveja preta;
  •  : Indica a quantidade (em litros) de cerveja branca;

O ganho do empresário, que é o que se pretende maximizar, pode ser obtido pela fórmula:

 

Por hora, considere que são aceitáveis os valores de   e   serem reais (não apenas inteiros positivos, mas também "números quebrados" como  ,  , etc).

Como o estoque de cada ingrediente é limitado, tem-se restrições que devem ser consideradas. Matematicamente tais restrições podem ser expressas assim:

 

Pode-se simplificar a escrita das restrições e também da função objetivo utilizando a seguinte notação:

 

Nesses termos, o problema de otimização a ser resolvido é:

 

ou apenas,

 

onde   é o conjunto definido pelo conjunto de restrições:

 

Tal problema tem solução pois a função objetivo   é linear (contínua) e o conjunto de restrições forma um conjunto compacto.

Para este problema, a lagrangiana é dado por

 

Donde

 

Então, o problema dual é dado por

 

que é equivalente a

 

ou, escrevendo novamente em termos dos valores numéricos,

 


Na década de 30, 40 e 50 havia diversos livros que tratavam cada problema de programação linear individualmente, deduzindo vez após vez os seus duais, e disso extraindo certas "regras" que eram então sugeridas ao leitor na forma "se o problema for desse tipo, use tal regra, se for daquele tipo, use esta outra, e se for deste outro tipo, use esta regra". Um dos primeiros autores que começou a trabalhar os problemas sob um novo ponto de vista, mais generalizado, foi Werner Oettio (grafia?) . Seguindo-se por George Dantzig (conhecido como inventor do método simplex), Eugen Blumb (grafia?) e Jean-Pierre Crouzeix.

  Este módulo tem a seguinte tarefa pendente: Identificar e corrigir a grafia correta dos nomes dos pesquisadores mostrados acima; Encontrar fontes para comprovar a informação deste parágrafo.

Aplicação à programação quadrática

editar

Agora, o problema a considerar passa a ser

 

onde   é um poliedro (interseção finita de semi-espaços),  ,   e   é uma matriz simétrica positiva definida.

Note que este problema tem solução, uma vez que o problema irrestrito correspondente tem solução (já que   é uma matriz simétrica positiva definida, a função é limitada inferiormente, e como   é fechado, a função objetivo assume seu valor mínimo em  , por Wolfe).

Mesmo para  , os problemas de programação linear já são difíceis de resolver "à mão". É preciso utilizar alguma técnica mais sofisticada.

Para dar continuidade ao exemplo, considere que o poliedro   é dado por

 

com   e  .

Agora será aplicado o esquema de dualidade. A lagrangiana é

 
 

além disso,

 
 

e a última igualdade vale pois a função é fortemente convexa.

 

Considerando  , se deduz que

 .

Logo,

 

Observe que, sendo os autovalores de   positivos, o mesmo vale obrigatoriamente para  . Assim, como a expressão de   envolve  , tal função é fortemente côncava (conforme já era esperado para tal função).

Baseado nestas deduções, o problema dual é

 

ou seja,

 

Usualmente este tipo de problema   é resolvido por meio do método do gradiente projetado.

Revisão do método do gradiente projetado

editar

O método baseia-se na seguinte proposição:

Proposição

Seja   uma função convexa em  , um conjunto convexo e fechado. Se o ponto   é tal que  , então  .

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

Um algoritmo para o método do gradiente projetado

editar

Este algoritmo é bastante simples.

Primeiro passo:
  Escolha   e fixe  .  
Passo iterativo  : Enquanto  
   

Agora, é interessante observar como se faz para projetar um ponto em  .

Exercício

Dado  , mostre que

 

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.

Exemplificando a projeção

editar

Seja  . Então a projeção de   sobre   é :

 

Devido a essa simplicidade ao se fazer a projeção de um ponto, o método do gradiente projetado é muito eficiente para resolver o problema  .

Exemplo concreto

editar

Seja  .

  Este módulo tem a seguinte tarefa pendente: Incluir uma ilustração deste conjunto.

Como calcular a projeção do ponto   sobre o conjunto  ,  ?

Resolução
Seja   a projeção de   sobre  . Então:
 

Então:

 

Nota: O leitor deve observar que a inclusão de   é válida, e foi feita apenas para simplificar as contas.

Logo o modelo matemático para resolver este problema é

 

A lagrangiana é dada por

 

Logo,

 

Fazendo   tem-se:

 

Donde

 

Logo,

 

Logo, o problema dual é

 

ou seja,

 

Agora, para a resolução deste problema dual, pode-se usar o método do gradiente projetado.

Para isso, note que o gradiente de   é:

 
Passo 0

Seja   e escolha  .

Passo 1

 

Passo 2

 

Logo, a solução dual é

 

Agora, substituindo tal solução na lagrangiana, obtem-se o problema:

 

que é um problema quadrático sem restrições. Neste caso, basta igualar o gradiente a zero para determinar uma solução:  

Donde   e  . De acordo com a teoria desenvolvida, a solução   do problema é também solução do problema original, pois o produto é igual a zero (ver condições da proposição).

Exercícios resolvidos

editar
Exercício

Encontrar a solução do seguinte problema de programação linear:

 
sendo
 
 
 

Resolução
Primeiramente observe que  , então não é possível obter uma interpretação geométrica do problema. Será usado o esquema de dualidade lagrangiana:
Identificar a lagrangiana  
 
 
Identificar a função  
 
 
Identificar o problema dual  
 

que equivale a

 

ou simplesmente

 

Agora, se tem um problema em  , e portanto, pode-se ter uma interpretação geométrica para o mesmo:

  Este módulo tem a seguinte tarefa pendente: Incluir ilustração do conjunto dos pontos que verificam as restrições do problema dual, bem como algumas curvas de nível da função objetivo (as mais relevantes).

As inequações que definem o conjunto viável são:

 

Tal conjunto é um pentágono (irregular, mas convexo), logo o valor máximo de   é assumido quando   for um dos cinco vértices. Através de simples verificação, comprova-se que o ponto de máximo é  . Conforme a teoria, este ponto é uma solução do problema dual  .

Como   é um problema diferenciável e convexo (as condições de KKT são necessárias e suficientes), o dual terá solução e as duas juntas compõe um ponto de sela de  .

Considere as condições de KKT:

  1.  
  2.  
  3.  , ou seja,  
  4.  , ou seja,  
  5.  , ou seja,  

Note que, a partir de 2 e 3, conclui-se que 4 só é possível quando  .

Para se obter  , basta lembrar que em   se tem:

  (comprovando 1)

Logo,  

comprovando a propriedade (2).

Como valem as propriedades (3) e (5), tem-se:

 

Donde  . Resta usar a informação da propriedade (4) para obter   e  . O sistema   pode ser escrito como:

 

Logo,   e  .

Se  ,   e   satisfazem todas as propriedades, então   é solução do problema  , pois todas as condições de KKT são necessárias e suficientes.

Ao resolver o problema  , poderia ter sido escolhido   em vez de  . Será que isso influenciaria o resultado final?

Acompanhe como ficaria a resolução desta maneira:

Resolução
;Identificar a lagrangiana  
 
 
Identificar a função  
 
 
Identificar o problema dual  
 

que equivale a

 

ou simplesmente

 

Novamente, chega-se até um problema em  , que pode ser interpretado de forma geométrica.

  Este módulo tem a seguinte tarefa pendente: Incluir ilustração do conjunto dos pontos que verificam as restrições deste problema dual, bem como algumas curvas de nível da função objetivo (as mais relevantes).

As inequações que definem o conjunto viável são:

 

Este conjunto também é um pentágono, de modo que o valor mínimo de   é assumido quando   for um dos cinco vértices. Através de simples verificação, comprova-se que o ponto de mínimo, ou seja uma solução do problema dual  , é  .

Nas condições de KKT, a única mudança é na propriedade (1), que se torna:

 

Resta ainda saber quem é   e quem é  :

 

como antes.

Como ao obter   e   chegou-se ao mesmo resultado de antes, o ponto   continuará sendo o mesmo.

Exercício

Formule como um problema de minimização com restrições o problema de projetar ortogonalmente o ponto   sobre o conjunto  . Depois, calcule explicitamente a função lagrangiana e o problema dual.

Resolução
Matematicamente resolver esse problema é resolver

 

Definimos a lagrangeana como  

 

 

Como a função é quadrática , podemos calcular o gradiente e igualar a zero:

   

Donde,   e  

Substituindo na função   temos:

 

 

 

O problema dual fica então:

 

Que é equivalente a:

 


Exercício

No exercício anterior, se   é a variável dual relacionada a variável primal   e   é a variável dual relacionada a variável primal  , então verifique se   é solução dual e se a lagrangiana tem pontos de sela. Em caso afirmativo, calcule um ponto de sela, caso contrário, argumente porque a lagrangiana não tem pontos de sela.

Resolução
Olhando o problema

 

observamos que é um problema com restrições.

Podemos usar as equações de KKT para resolve-lo.

Definimos a lagrangeana como

 

Agora usando o teorema de KKT devemos ter:

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  

Calculando o gradiente temos

   

E portanto   e  .

Olhando nas equações acima obtemos   ,  ,   e  .

Portanto   é a solução dual.

Voltando na lagrangiana do problema original e substituindo os multiplicadores de Lagrange obtemos um problema sem restrições:

 

Calculando o gradiente temos:

   

Portanto   é a solução primal.

Logo   é um candidato a ponto de sela.

Para verificar que ele é ponto de sela, basta ver se não há salto de dualidade. Mas isso não ocorre já que o valor ótimo do primal é   e o valor ótimo do dual também é  .