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

Origem: Wikilivros, livros abertos por um mundo aberto.

Aplicação à programação linear[editar | editar código-fonte]

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

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

onde são dados , e .

Calculando o dual de (PL)[editar | editar código-fonte]

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

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

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

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

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

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

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

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

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. , ou seja,
  2. , ou seja,
  3. , 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:

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