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

Aplicação à programação linear

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

$\{\begin{array}{c}min{a}^{\mathrm{\top }}x+b^{\mathrm{\top }}y\\ Mx+Ny\ge c\\ Px+Qy=d\\ x\ge 0;y\in {ℝ}^n\end{array}$

onde são dados $a\in {ℝ}^n$, $b\in {ℝ}^m$, $M_{p\times n}$, $N_{p\times m}$, $P_{q\times n}$, $Q_{q\times m}$, $d\in {ℝ}^p$ e $c\in {ℝ}^q$. Por simplicidade, pode-se ainda adotar a seguinte notação:

$C=\{\left[\begin{array}{c}x\\ y\end{array}\right];Mx+Ny\ge c,Px+Qy=d,x\ge 0\text{ e }y\in {ℝ}^n\}$

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:

$\begin{array}{cc}l(x,y,u,v,w)& =[a^{\mathrm{\top }}x+b^{\mathrm{\top }}y]+u^{\mathrm{\top }}[c-Mx-Ny]+v^{\mathrm{\top }}[d-Px-Qy]+w^{\mathrm{\top }}[-x]\\ & =[a-M^{\mathrm{\top }}u-P^{\mathrm{\top }}v-w{]}^{\mathrm{\top }}x+[b-N^{\mathrm{\top }}u-Q^{\mathrm{\top }}v{]}^{\mathrm{\top }}y+[c^{\mathrm{\top }}u+d^{\mathrm{\top }}v]\end{array}$

Note que:

• As variáveis primais são $x$ e $y$;
• As variáveis duais são $u$, $v$ e $w$;

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

$\alpha :{ℝ}^n\mapsto ℝ\cup \{+\mathrm{\infty }\}$, dada por

$\alpha (x)=\underset{\begin{array}{c}u\ge 0\\ v\in {ℝ}^q\\ w\ge 0\end{array}}{sup}l(x,y,u,v,w)=\{\begin{array}{ccc}{a}^{\mathrm{\top }}x+b^{\mathrm{\top }}y& ,& \text{ se }\left[\begin{array}{c}x\\ y\end{array}\right]\in C\\ +\mathrm{\infty }& ,& \text{ em outros casos}\end{array}$

e

$\beta :{ℝ}^p\times {ℝ}^q\mapsto ℝ\cup \{-\mathrm{\infty }\}$, dada por

$\begin{array}{cc}\beta (u,v)& =\underset{\begin{array}{c}x\in {ℝ}^n\\ y\in {ℝ}^m\end{array}}{inf}l(x,y,u,v,w)\\ & =\underset{\begin{array}{c}x\in {ℝ}^n\\ y\in {ℝ}^m\end{array}}{inf}[a-M^{\mathrm{\top }}u-P^{\mathrm{\top }}v-w{]}^{\mathrm{\top }}x+[b-N^{\mathrm{\top }}u-Q^{\mathrm{\top }}v{]}^{\mathrm{\top }}y+[c^{\mathrm{\top }}u+d^{\mathrm{\top }}v]\\ & =[c^{\mathrm{\top }}u+d^{\mathrm{\top }}v]+\underset{x\in {ℝ}^n}{inf}[a-M^{\mathrm{\top }}u-P^{\mathrm{\top }}v-w{]}^{\mathrm{\top }}x+\underset{y\in {ℝ}^m}{inf}[b-N^{\mathrm{\top }}u-Q^{\mathrm{\top }}v{]}^{\mathrm{\top }}y\\ & =\{\begin{array}{ccc}{c}^{\mathrm{\top }}u+d^{\mathrm{\top }}v& ,& \text{ se }\{\begin{array}{ccc}a-M^{\mathrm{\top }}u-P^{\mathrm{\top }}v-w& =& 0\\ b-N^{\mathrm{\top }}u-Q^{\mathrm{\top }}v& =& 0\\ u\ge 0;w\ge 0& & \end{array}\\ -\mathrm{\infty }& ,& \text{ em outros casos}\end{array}\end{array}$

Logo, considerando que $a-M^{\mathrm{\top }}u-P^{\mathrm{\top }}v=w\ge 0$, o problema dual consiste no seguinte:

$\{\begin{array}{c}max{c}^{\mathrm{\top }}u+d^{\mathrm{\top }}v\\ M^{\mathrm{\top }}u+P^{\mathrm{\top }}v\le a\\ N^{\mathrm{\top }}u+Q^{\mathrm{\top }}v=b\\ u\ge 0\end{array}$

Exemplificando com um problema de programação linear

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

$(PL)\{\begin{array}{c}min{c}^{\mathrm{\top }}x\\ Ax=b\\ x\ge 0\end{array}$

onde são dados $A_{m\times n}$, $b\in {ℝ}^m$ e $c\in {ℝ}^n$.

Calculando o dual de (PL)

Primeiramente,

$l(x,u,v)=c^{\mathrm{\top }}x+u^{\mathrm{\top }}(-x)+v^{\mathrm{\top }}(b-Ax)$

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

$\alpha (x)=\{\begin{array}{cc}f(x)& ,\text{ se }x\in C\\ +\mathrm{\infty }& ,\text{ se }x\in ̸C\end{array}$

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

$\beta (u,v)=\underset{x\in {ℝ}^n}{inf}l(x,u,v)$

$\begin{array}{cc}\beta (u,v)& =\underset{x\in {ℝ}^n}{inf}l(x,u,v)\\ & =\underset{x\in {ℝ}^n}{inf}[c^{\mathrm{\top }}x-u^{\mathrm{\top }}x+v^{\mathrm{\top }}(b-Ax)]\\ & =b^{\mathrm{\top }}v+\underset{x\in {ℝ}^n}{inf}[c-u-A^{\mathrm{\top }}v{]}^{\mathrm{\top }}x\\ & =\{\begin{array}{ccc}{b}^{\mathrm{\top }}v& ,& \text{ se }c-u-A^{\mathrm{\top }}v=0\\ -\mathrm{\infty }& ,& \text{ em outros casos}\end{array}\end{array}$

Logo, o problema dual é:

$(D)\{\begin{array}{c}max{b}^{\mathrm{\top }}v\\ c-u-A^{\mathrm{\top }}v=0\\ u\ge 0;v\in {ℝ}^m\end{array}$

ou ainda

$(D)\{\begin{array}{c}max{b}^{\mathrm{\top }}v\\ A^{\mathrm{\top }}v\le c\\ v\in {ℝ}^m\end{array}$

Calculando o dual do dual de (PL)

Considere o seguinte problema:

$(D)\{\begin{array}{c}max{b}^{\mathrm{\top }}v\\ A^{\mathrm{\top }}v\le c\\ v\in {ℝ}^m\end{array}$

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

$(D)\{\begin{array}{c}min-b^{\mathrm{\top }}v\\ A^{\mathrm{\top }}v\le c\\ v\in {ℝ}^m\end{array}$

A lagrangiana é dado por:

$l(v,y)=-b^{\mathrm{\top }}v+y^{\mathrm{\top }}(A^{\mathrm{\top }}v-c)$

Logo,

$\begin{array}{cc}\beta (y)& =\underset{v\in {ℝ}^m}{inf}l(v,y)\\ & =\underset{v\in {ℝ}^m}{inf}[-b^{\mathrm{\top }}v+y^{\mathrm{\top }}(A^{\mathrm{\top }}v-c)]\\ & =-c^{\mathrm{\top }}y+\underset{v\in {ℝ}^m}{inf}[(Ay-b{)}^{\mathrm{\top }}v]\\ & =\{\begin{array}{ccc}-c^{\mathrm{\top }}y& ,& \text{ se }Ay-b=0\\ -\mathrm{\infty }& ,& \text{ em outros casos}\end{array}\end{array}$

Logo, o dual de $(D)$ é:

$(DD)\{\begin{array}{c}max\beta (y)\\ y\ge 0\end{array},$

ou seja,

$(DD)\{\begin{array}{c}max-c^{\mathrm{\top }}y\\ Ay=b\\ y\ge 0\end{array}$

que equivale a

$(P)\{\begin{array}{c}min{c}^{\mathrm{\top }}x\\ Ax=b\\ x\ge 0\end{array}$

Um exemplo numérico contextualizado

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.

Predefinição:Resolução 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. Predefinição:Tarefa

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

Agora, o problema a considerar passa a ser

$\{\begin{array}{c}min\frac{1}{2}{x}^{\mathrm{\top }}Qx+q^{\mathrm{\top }}x+\alpha \\ x\in C\end{array}$

onde $C$ é um poliedro (interseção finita de semi-espaços), $q\in {ℝ}^n$, $\alpha \in ℝ$ e $Q_{n\times n}$ é 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 $Q$ é uma matriz simétrica positiva definida, a função é limitada inferiormente, e como $C$ é fechado, a função objetivo assume seu valor mínimo em $C$, por Wolfe).

Mesmo para $n=5$, 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 $C$ é dado por

$C=\{x\in {ℝ}^n;x\ge 0\text{ e }Ax=b\}$

com $A_{m\times n}$ e $b\in {ℝ}^m$.

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

$l:{ℝ}^n\times {ℝ}^n\times {ℝ}^m\mapsto ℝ$

$l(x,u,v)=\frac{1}{2}{x}^{\mathrm{\top }}Qx+q^{\mathrm{\top }}x+\alpha +u^{\mathrm{\top }}(b-Ax)+v^{\mathrm{\top }}(-x)$

além disso,

$\beta :{ℝ}^n\times {ℝ}^m\mapsto ℝ\cup \{-\mathrm{\infty }\}$

$\beta (u,v)=\underset{x\in {ℝ}^n}{inf}l(x,u,v)=\underset{x\in {ℝ}^n}{min}l(x,u,v)$

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

$\begin{array}{cc}\beta (u,v)& =\underset{x\in {ℝ}^n}{inf}l(x,u,v)\\ & =\underset{x\in {ℝ}^n}{min}l(x,u,v)\\ & =\underset{x\in {ℝ}^n}{min}[\frac{1}{2}{x}^{\mathrm{\top }}Qx+q^{\mathrm{\top }}x+\alpha +u^{\mathrm{\top }}(b-Ax)+v^{\mathrm{\top }}(-x)]\\ & =\underset{x\in {ℝ}^n}{min}[\frac{1}{2}{x}^{\mathrm{\top }}Qx+(q-v-A^{\mathrm{\top }}u{)}^{\mathrm{\top }}x+u^{\mathrm{\top }}b+\alpha ]\end{array}$

Considerando ${\mathrm{\nabla }}_{x}l(\overline{x},u,v)=Q\overline{x}+q-v-A^{\mathrm{\top }}u=0$, se deduz que

$\overline{x}=Q^{-1}(A^{\mathrm{\top }}u+v-q)$.

Logo,

$\begin{array}{cc}\beta (u,v)& =\frac{1}{2}{[Q^{-1}(A^{\mathrm{\top }}u+v-q)]}^{\mathrm{\top }}Q[Q^{-1}(A^{\mathrm{\top }}u+v-q)]+(q-v-A^{\mathrm{\top }}u{)}^{\mathrm{\top }}[Q^{-1}(A^{\mathrm{\top }}u+v-q)]+u^{\mathrm{\top }}b+\alpha \\ & =\frac{1}{2}(A^{\mathrm{\top }}u+v-q{)}^{\mathrm{\top }}{Q}^{-1}(A^{\mathrm{\top }}u+v-q)-(A^{\mathrm{\top }}u+v-q{)}^{\mathrm{\top }}{Q}^{-1}(A^{\mathrm{\top }}u+v-q)+u^{\mathrm{\top }}b+\alpha \\ & =\frac{-1}{2}(A^{\mathrm{\top }}u+v-q{)}^{\mathrm{\top }}{Q}^{-1}(A^{\mathrm{\top }}u+v-q)+u^{\mathrm{\top }}b+\alpha \end{array}$

Observe que, sendo os autovalores de $Q$ positivos, o mesmo vale obrigatoriamente para $Q^{-1}$. Assim, como a expressão de $\beta$ envolve $(-Q^{-1})$, tal função é fortemente côncava (conforme já era esperado para tal função).

Baseado nestas deduções, o problema dual é

$(D)\{\begin{array}{c}max\frac{-1}{2}(A^{\mathrm{\top }}u+v-q{)}^{\mathrm{\top }}{Q}^{-1}(A^{\mathrm{\top }}u+v-q)+u^{\mathrm{\top }}b+\alpha \\ u\ge 0;v\in {ℝ}^m\end{array}$

ou seja,

$(D)\{\begin{array}{c}min\frac{1}{2}(A^{\mathrm{\top }}u+v-q{)}^{\mathrm{\top }}{Q}^{-1}(A^{\mathrm{\top }}u+v-q)-(u^{\mathrm{\top }}b+\alpha )\\ u\ge 0;v\in {ℝ}^m\end{array}$

Usualmente este tipo de problema $(D)$ é resolvido por meio do método do gradiente projetado.

Revisão do método do gradiente projetado

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

Um algoritmo para o método do gradiente projetado

Este algoritmo é bastante simples.

Primeiro passo:
  Escolha $x_0\in {ℝ}^n$ e fixe $\alpha >0$.  
Passo iterativo $k$: Enquanto $x_k≠P_C(x_k-\alpha \mathrm{\nabla }f(x_k))$
  $x_{k+1}=P_C(x_k-\alpha \mathrm{\nabla }f(x_k))$

Agora, é interessante observar como se faz para projetar um ponto em $C=[0,+\mathrm{\infty }{)}^n\times {ℝ}^m$.

Exemplificando a projeção

Seja $u={\left[\begin{array}{cccccccccc}1& -1& 2& -2& 3& -3& 4& -4& 5& -5\end{array}\right]}^{\mathrm{\top }}$. Então a projeção de $u$ sobre $C=[0,+\mathrm{\infty }{)}^6\times {ℝ}^4$ é :

$P_C\left({\left[\begin{array}{cccccccccc}1& -1& 2& -2& 3& -3& 4& -4& 5& -5\end{array}\right]}^{\mathrm{\top }}\right)={\left[\begin{array}{cccccccccc}1& 0& 2& 0& 3& 0& 4& -4& 5& -5\end{array}\right]}^{\mathrm{\top }}$

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 $(D)$.

Exemplo concreto

Seja $C=\{(x,y);x+y=1,x\ge 0,y\ge 0\}$. Predefinição:Tarefa

Como calcular a projeção do ponto $(1,2)$ sobre o conjunto $C$, $P_C(1,2)$? Predefinição:Resolução

Exercícios resolvidos

Predefinição:Exercício Predefinição:Resolução Ao resolver o problema $(P)$, poderia ter sido escolhido $Ax-b$ em vez de $b-Ax$. Será que isso influenciaria o resultado final?

Acompanhe como ficaria a resolução desta maneira: Predefinição:Resolução