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

Aplicação à programação linear

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

$\left\{{\begin{matrix}\min a^{\top }x+b^{\top }y\\Mx+Ny\geq c\\Px+Qy=d\\x\geq 0;\,y\in \mathbb {R} ^{n}\end{matrix}}\right.$

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

$C=\left\{{\begin{bmatrix}x\\y\end{bmatrix}};Mx+Ny\geq c,\,Px+Qy=d,\,x\geq 0{\text{ e }}y\in \mathbb {R} ^{n}\right\}$

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{aligned}l(x,y,u,v,w)&=[a^{\top }x+b^{\top }y]+u^{\top }[c-Mx-Ny]+v^{\top }[d-Px-Qy]+w^{\top }[-x]\\&=[a-M^{\top }u-P^{\top }v-w]^{\top }x+[b-N^{\top }u-Q^{\top }v]^{\top }y+[c^{\top }u+d^{\top }v]\\\end{aligned}}$

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 :\mathbb {R} ^{n}\mapsto \mathbb {R} \cup \{+\infty \}$, dada por

$\alpha (x)=\sup _{\begin{smallmatrix}u\geq 0\\v\in \mathbb {R} ^{q}\\w\geq 0\end{smallmatrix}}l(x,y,u,v,w)=\left\{{\begin{array}{rcl}a^{\top }x+b^{\top }y&,&{\text{ se }}{\begin{bmatrix}x\\y\end{bmatrix}}\in C\\+\infty &,&{\text{ em outros casos}}\end{array}}\right.$

e

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

${\begin{aligned}\beta (u,v)&=\inf _{\begin{smallmatrix}x\in \mathbb {R} ^{n}\\y\in \mathbb {R} ^{m}\end{smallmatrix}}l(x,y,u,v,w)\\&=\inf _{\begin{smallmatrix}x\in \mathbb {R} ^{n}\\y\in \mathbb {R} ^{m}\end{smallmatrix}}[a-M^{\top }u-P^{\top }v-w]^{\top }x+[b-N^{\top }u-Q^{\top }v]^{\top }y+[c^{\top }u+d^{\top }v]\\&=[c^{\top }u+d^{\top }v]+\inf _{x\in \mathbb {R} ^{n}}[a-M^{\top }u-P^{\top }v-w]^{\top }x+\inf _{y\in \mathbb {R} ^{m}}[b-N^{\top }u-Q^{\top }v]^{\top }y\\&=\left\{{\begin{array}{rcl}c^{\top }u+d^{\top }v&,&{\text{ se }}\left\{{\begin{array}{rcl}a-M^{\top }u-P^{\top }v-w&=&0\\b-N^{\top }u-Q^{\top }v&=&0\\u\geq 0;\,w\geq 0&&\end{array}}\right.\\-\infty &,&{\text{ em outros casos}}\end{array}}\right.\end{aligned}}$

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

$\left\{{\begin{matrix}\max c^{\top }u+d^{\top }v\\M^{\top }u+P^{\top }v\leq a\\N^{\top }u+Q^{\top }v=b\\u\geq 0\end{matrix}}\right.$

Exercício

Verificar que ${\bar {x}}$ é uma solução de

$(P)\left\{{\begin{matrix}\min f(x)\\x\in C\end{matrix}}\right.$

se, e somente se, ${\bar {x}}$ é uma solução de

$({\bar {P}})\left\{{\begin{matrix}\max(-f(x))\\x\in C\end{matrix}}\right.$

Resolução
Seja ${\bar {x}}$ uma solução de $(P)$. Então, por definição, tem-se para todo $x\in C$ que $f({\bar {x}})\leq f(x)$ mas isto equivale a $-f(x)\leq -f({\bar {x}}),$ ou seja, ${\bar {x}}$ é uma solução de $({\bar {P}})$.

Exercício

Verificar que:

$\inf _{x\in C}f(x)=-\sup _{x\in C}[-f(x)]$

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

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

$(PL)\left\{{\begin{matrix}\min c^{\top }x\\Ax=b\\x\geq 0\\\end{matrix}}\right.$

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

Calculando o dual de (PL)

Primeiramente,

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

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

$\alpha (x)=\left\{{\begin{matrix}f(x)&,{\text{ se }}x\in C\\+\infty &,{\text{ se }}x\not \in C\end{matrix}}\right.$

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

$\beta (u,v)=\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)$

${\begin{aligned}\beta (u,v)&=\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)\\&=\inf _{x\in \mathbb {R} ^{n}}[c^{\top }x-u^{\top }x+v^{\top }(b-Ax)]\\&=b^{\top }v+\inf _{x\in \mathbb {R} ^{n}}[c-u-A^{\top }v]^{\top }x\\&=\left\{{\begin{array}{rcl}b^{\top }v&,&{\text{ se }}c-u-A^{\top }v=0\\-\infty &,&{\text{ em outros casos}}\end{array}}\right.\end{aligned}}$

Logo, o problema dual é:

$(D)\left\{{\begin{matrix}\max b^{\top }v\\c-u-A^{\top }v=0\\u\geq 0;\,v\in \mathbb {R} ^{m}\\\end{matrix}}\right.$

ou ainda

$(D)\left\{{\begin{matrix}\max b^{\top }v\\A^{\top }v\leq c\\v\in \mathbb {R} ^{m}\\\end{matrix}}\right.$

Calculando o dual do dual de (PL)

Considere o seguinte problema:

$(D)\left\{{\begin{matrix}\max b^{\top }v\\A^{\top }v\leq c\\v\in \mathbb {R} ^{m}\\\end{matrix}}\right.$

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

$(D)\left\{{\begin{matrix}\min -b^{\top }v\\A^{\top }v\leq c\\v\in \mathbb {R} ^{m}\\\end{matrix}}\right.$

A lagrangiana é dado por:

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

Logo,

${\begin{aligned}\beta (y)&=\inf _{v\in \mathbb {R} ^{m}}l(v,y)\\&=\inf _{v\in \mathbb {R} ^{m}}[-b^{\top }v+y^{\top }(A^{\top }v-c)]\\&=-c^{\top }y+\inf _{v\in \mathbb {R} ^{m}}[(Ay-b)^{\top }v]\\&=\left\{{\begin{array}{rcl}-c^{\top }y&,&{\text{ se }}Ay-b=0\\-\infty &,&{\text{ em outros casos}}\end{array}}\right.\end{aligned}}$

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

$(DD)\left\{{\begin{matrix}\max \beta (y)\\y\geq 0\\\end{matrix}}\right.,$

ou seja,

$(DD)\left\{{\begin{matrix}\max -c^{\top }y\\Ay=b\\y\geq 0\\\end{matrix}}\right.$

que equivale a

$(P)\left\{{\begin{matrix}\min c^{\top }x\\Ax=b\\x\geq 0\\\end{matrix}}\right.$

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.

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: $p$: Indica a quantidade (em litros) de cerveja preta; $b$: 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: $g(p,b)=230p+130b$ Por hora, considere que são aceitáveis os valores de $p$ e $b$ serem reais (não apenas inteiros positivos, mas também "números quebrados" como $3,5$, $7,11$, etc). Como o estoque de cada ingrediente é limitado, tem-se restrições que devem ser consideradas. Matematicamente tais restrições podem ser expressas assim: $\left\{{\begin{matrix}2,5p&+&7,5b&\leq &240\\0,125p&+&0,125b&\leq &5\\17,5p&+&10b&\leq &595\\p\geq 0&&&&\\b\geq 0&&&&\\\end{matrix}}\right.$ Pode-se simplificar a escrita das restrições e também da função objetivo utilizando a seguinte notação: $A={\begin{bmatrix}2,5&7,5\\0,125&0,125\\17,5&10\end{bmatrix}},\quad x={\begin{bmatrix}p\\b\end{bmatrix}},\quad b={\begin{bmatrix}240\\5\\595\end{bmatrix}}\quad {\text{e}}\quad c={\begin{bmatrix}230\\130\end{bmatrix}}$ Nesses termos, o problema de otimização a ser resolvido é: $\left\{{\begin{matrix}\max c^{\top }x\\Ax\leq b\\x\geq 0\end{matrix}}\right.$ ou apenas, $\left\{{\begin{matrix}\max c^{\top }x\\x\in C\end{matrix}}\right.$ onde $C$ é o conjunto definido pelo conjunto de restrições: $C=\left\{(p,b);Ax\leq b{\text{ e }}x\geq 0\right\}$ Tal problema tem solução pois a função objetivo $g(p,b)$ é linear (contínua) e o conjunto de restrições forma um conjunto compacto. Para este problema, a lagrangiana é dado por $l(x,u_{1},u_{2})=-c^{\top }x+u_{1}^{\top }(Ax-b)+u_{2}^{\top }(-x)$ Donde ${\begin{aligned}\beta (u_{1},u_{2})&=\inf _{x\in \mathbb {R} ^{2}}l(x,u_{1},u_{2})\\&=\inf _{x\in \mathbb {R} ^{2}}[-c^{\top }x+u_{1}^{\top }(Ax-b)+u_{2}^{\top }(-x)]\\&=-b^{\top }u_{1}+\inf _{x\in \mathbb {R} ^{2}}[(A^{\top }u_{1}-c-u_{2})^{\top }x]\\&=\left\{{\begin{array}{rcl}-b^{\top }u_{1}&,&{\text{ se }}A^{\top }u_{1}-c-u_{2}=0\\-\infty &,&{\text{ em outros casos}}\end{array}}\right.\end{aligned}}$ Então, o problema dual é dado por $(D)\left\{{\begin{matrix}\max -b^{\top }u_{1}\\A^{\top }u_{1}\geq 0\\u_{1}\geq 0\end{matrix}}\right.$ que é equivalente a $(D)\left\{{\begin{matrix}\min b^{\top }u_{1}\\A^{\top }u_{1}\geq 0\\u_{1}\geq 0\end{matrix}}\right.$ ou, escrevendo novamente em termos dos valores numéricos, $(D)\left\{{\begin{matrix}\min 240u_{1}+5u_{2}+595u_{3}\\7,5u_{1}+0,125u_{2}+10u_{3}\leq 130\\2,5u_{1}+0,125u_{2}+17,5u_{3}\leq 230\\u_{1}\geq 0;u_{2}\geq 0\\\end{matrix}}\right.$

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

Agora, o problema a considerar passa a ser

$\left\{{\begin{matrix}\min {\frac {1}{2}}x^{\top }Qx+q^{\top }x+\alpha \\x\in C\end{matrix}}\right.$

onde $C$ é um poliedro (interseção finita de semi-espaços), $q\in \mathbb {R} ^{n}$, $\alpha \in \mathbb {R}$ 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=\left\{x\in \mathbb {R} ^{n};x\geq 0{\text{ e }}Ax=b\right\}$

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

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

$l:\mathbb {R} ^{n}\times \mathbb {R} ^{n}\times \mathbb {R} ^{m}\mapsto \mathbb {R}$

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

além disso,

$\beta :\mathbb {R} ^{n}\times \mathbb {R} ^{m}\mapsto \mathbb {R} \cup \{-\infty \}$

$\beta (u,v)=\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)=\min _{x\in \mathbb {R} ^{n}}l(x,u,v)$

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

${\begin{aligned}\beta (u,v)&=\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)\\&=\min _{x\in \mathbb {R} ^{n}}l(x,u,v)\\&=\min _{x\in \mathbb {R} ^{n}}[{\frac {1}{2}}x^{\top }Qx+q^{\top }x+\alpha +u^{\top }(b-Ax)+v^{\top }(-x)]\\&=\min _{x\in \mathbb {R} ^{n}}[{\frac {1}{2}}x^{\top }Qx+(q-v-A^{\top }u)^{\top }x+u^{\top }b+\alpha ]\\\end{aligned}}$

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

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

Logo,

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

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)\left\{{\begin{matrix}\max {\frac {-1}{2}}(A^{\top }u+v-q)^{\top }Q^{-1}(A^{\top }u+v-q)+u^{\top }b+\alpha \\u\geq 0;\,v\in \mathbb {R} ^{m}\\\end{matrix}}\right.$

ou seja,

$(D)\left\{{\begin{matrix}\min {\frac {1}{2}}(A^{\top }u+v-q)^{\top }Q^{-1}(A^{\top }u+v-q)-(u^{\top }b+\alpha )\\u\geq 0;\,v\in \mathbb {R} ^{m}\\\end{matrix}}\right.$

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:

Proposição

Seja $f$ uma função convexa em $C$, um conjunto convexo e fechado. Se o ponto ${\bar {x}}\in C$ é tal que ${\bar {x}}=P_{C}({\bar {x}}-\alpha \nabla f({\bar {x}}))$, então $f({\bar {x}})\leq f(x),\forall x\in C$.

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

Este algoritmo é bastante simples.

Primeiro passo:
  Escolha $x_{0}\in \mathbb {R} ^{n}$ e fixe $\alpha >0$.  
Passo iterativo $k$: Enquanto $x_{k}\not =P_{C}(x_{k}-\alpha \nabla f(x_{k}))$
  $x_{k+1}=P_{C}(x_{k}-\alpha \nabla f(x_{k}))$

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

Exercício

Dado $C=[0,+\infty )^{n}\times \mathbb {R} ^{m}$, mostre que

$P_{C}\left({\begin{bmatrix}x\\y\end{bmatrix}}\right)={\begin{bmatrix}\max\{x,0\}\\0\end{bmatrix}}$

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

Seja $u={\begin{bmatrix}1&-1&2&-2&3&-3&4&-4&5&-5\end{bmatrix}}^{\top }$. Então a projeção de $u$ sobre $C=[0,+\infty )^{6}\times \mathbb {R} ^{4}$ é :

$P_{C}\left({\begin{bmatrix}1&-1&2&-2&3&-3&4&-4&5&-5\end{bmatrix}}^{\top }\right)={\begin{bmatrix}1&0&2&0&3&0&4&-4&5&-5\end{bmatrix}}^{\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);\quad x+y=1,\quad x\geq 0,\quad y\geq 0\}$.

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

Como calcular a projeção do ponto $(1,2)$ sobre o conjunto $C$, $P_{C}(1,2)$?

Resolução

Seja ${\bar {P}}$ a projeção de $(1,2)$ sobre $C$. Então: $\|{\bar {P}}-(1,2)\|^{2}\leq \|(x,y)-(1,2)\|^{2},\quad \forall (x,y)\in C$ Então: ${\frac {1}{2}}\|{\bar {P}}-(1,2)\|^{2}=\min _{(x,y)\in C}{\frac {1}{2}}\|(x,y)-(1,2)\|^{2},\quad \forall (x,y)\in C$ Nota: O leitor deve observar que a inclusão de ${\frac {1}{2}}$ é válida, e foi feita apenas para simplificar as contas. Logo o modelo matemático para resolver este problema é $(P)\left\{{\begin{matrix}\min {\frac {1}{2}}\left[(x-1)^{2}+(y-2)^{2}\right]\\x\geq 0;y\geq 0\\x+y=1\end{matrix}}\right.$ A lagrangiana é dada por $l(x,y,u,v,w)={\frac {1}{2}}\left[(x-1)^{2}+(y-2)^{2}\right]-ux-vy+w(1-x-y)$ Logo, ${\begin{aligned}\beta (u,v,w)&=\inf _{\begin{smallmatrix}x\in \mathbb {R} \\y\in \mathbb {R} \end{smallmatrix}}l(x,y,u,v,w)\\&=\inf _{\begin{smallmatrix}x\in \mathbb {R} \\y\in \mathbb {R} \end{smallmatrix}}\left[{\frac {1}{2}}\left[(x-1)^{2}+(y-2)^{2}\right]-ux-vy+w(1-x-y)\right]\\&=\inf _{\begin{smallmatrix}x\in \mathbb {R} \\y\in \mathbb {R} \end{smallmatrix}}\left[{\frac {1}{2}}\left[(x-1)^{2}+(y-2)^{2}\right]-(u+w)x-(v+w)y+w\right]\end{aligned}}$ Fazendo $\nabla _{(x,y)}l({\bar {x}},{\bar {y}},u,v,w)=0$ tem-se: ${\begin{bmatrix}{\bar {x}}-1-(u+w)\\{\bar {y}}-2-(v+w)\end{bmatrix}}={\begin{bmatrix}0\\0\end{bmatrix}}$ Donde ${\begin{bmatrix}{\bar {x}}\\{\bar {y}}\end{bmatrix}}={\begin{bmatrix}u+w+1\\v+w+2\end{bmatrix}}$ Logo, ${\begin{aligned}\beta (u,v,w)&={\frac {1}{2}}\left[\left((u+w+1)-1\right)^{2}+\left((v+w+2)-2\right)^{2}\right]-(u+w)(u+w+1)-(v+w)(v+w+2)+w\\&={\frac {1}{2}}\left[(u+w)^{2}+(v+w)^{2}\right]-(u+w)(u+w+1)-(v+w)(v+w+2)+w\\&={\frac {-1}{2}}\left[(u+w)^{2}+(v+w)^{2}\right]-(u+w)-2(v+w)+w\\&={\frac {-1}{2}}\left[(u+w)^{2}+(v+w)^{2}\right]-u-2v-2w\end{aligned}}$ Logo, o problema dual é $(D)\left\{{\begin{matrix}\max \beta (u,v,w)\\u\geq 0;\,v\geq 0;\,w\in \mathbb {R} ^{m}\\\end{matrix}}\right.$ ou seja, $(D)\left\{{\begin{matrix}\min {\frac {1}{2}}\left[(u+w)^{2}+(v+w)^{2}\right]+u+2(v+w)\\u\geq 0;\,v\geq 0;\,w\in \mathbb {R} ^{m}\\\end{matrix}}\right.$ Agora, para a resolução deste problema dual, pode-se usar o método do gradiente projetado. Para isso, note que o gradiente de $\beta$ é: $\nabla \beta (u,v,w)={\begin{bmatrix}u+w+1\\v+w+2\\u+v+2w+2\end{bmatrix}}$ Passo 0 Seja $\alpha ={\frac {1}{2}}$ e escolha $x_{0}={\begin{bmatrix}u_{0}\\v_{0}\\w_{0}\end{bmatrix}}={\begin{bmatrix}0\\0\\0\end{bmatrix}}$. Passo 1 $x_{1}={\begin{bmatrix}u_{1}\\v_{1}\\w_{1}\end{bmatrix}}=P_{[0,+\infty )^{2}\times \mathbb {R} }\left({\begin{bmatrix}0\\0\\0\end{bmatrix}}-{\frac {1}{2}}{\begin{bmatrix}1\\2\\2\end{bmatrix}}\right)=P_{[0,+\infty )^{2}\times \mathbb {R} }\left({\begin{bmatrix}-1/2\\-1\\-1\end{bmatrix}}\right)={\begin{bmatrix}0\\0\\-1\end{bmatrix}}$ Passo 2 $x_{2}={\begin{bmatrix}u_{2}\\v_{2}\\w_{2}\end{bmatrix}}=P_{[0,+\infty )^{2}\times \mathbb {R} }\left({\begin{bmatrix}0\\0\\-1\end{bmatrix}}-{\frac {1}{2}}{\begin{bmatrix}0\\1\\0\end{bmatrix}}\right)=P_{[0,+\infty )^{2}\times \mathbb {R} }\left({\begin{bmatrix}0\\-1/2\\-1\end{bmatrix}}\right)={\begin{bmatrix}0\\0\\-1\end{bmatrix}}={\begin{bmatrix}u_{1}\\v_{1}\\w_{1}\end{bmatrix}}$ Logo, a solução dual é ${\begin{bmatrix}{\bar {u}}\\{\bar {v}}\\{\bar {w}}\end{bmatrix}}={\begin{bmatrix}0\\0\\-1\end{bmatrix}}$ Agora, substituindo tal solução na lagrangiana, obtem-se o problema: $(P_{{\bar {u}},{\bar {v}},{\bar {w}}})\left\{{\begin{matrix}\min {\frac {1}{2}}\left[(x-1)^{2}+(y-2)^{2}+x+y-1\right]\\x\in \mathbb {R} ;\,y\in \mathbb {R} \end{matrix}}\right.$ que é um problema quadrático sem restrições. Neste caso, basta igualar o gradiente a zero para determinar uma solução: ${\begin{bmatrix}0\\0\end{bmatrix}}=\nabla _{(x,y)}l({\bar {x}},{\bar {y}},{\bar {u}},{\bar {v}},{\bar {w}})={\begin{bmatrix}({\bar {x}}-1)+1\\({\bar {y}}-2)+1\end{bmatrix}}={\begin{bmatrix}{\bar {x}}\\{\bar {y}}-1\end{bmatrix}}$ Donde ${\bar {x}}=0$ e ${\bar {y}}=1$. De acordo com a teoria desenvolvida, a solução ${\begin{bmatrix}0\\1\end{bmatrix}}$ do problema é também solução do problema original, pois o produto é igual a zero (ver condições da proposição).

Exercícios resolvidos

Exercício

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

$\left\{{\begin{matrix}\min c^{\top }x\\Ax=b\\x\geq 0\end{matrix}}\right.$

sendo

$c^{\top }={\begin{bmatrix}2&5&2&1&1\end{bmatrix}}$

$A={\begin{bmatrix}-1&2&1&-1&0\\1&1&0&0&-1\end{bmatrix}}$

$b^{\top }={\begin{bmatrix}1&1\end{bmatrix}}$

Resolução

Primeiramente observe que $x\in \mathbb {R} ^{5}$, então não é possível obter uma interpretação geométrica do problema. Será usado o esquema de dualidade lagrangiana: Identificar a lagrangiana $l$ $l:\mathbb {R} ^{5}\times \mathbb {R} ^{5}\times \mathbb {R} ^{2}\mapsto \mathbb {R}$ $l(x,u,v)=c^{\top }x-u^{\top }x+v^{\top }(b-Ax)$ Identificar a função $\beta$ $\beta :\mathbb {R} ^{5}\times \mathbb {R} ^{5}\mapsto \mathbb {R} \cup \{-\infty \}$ ${\begin{aligned}\beta (u,v)&=\inf _{x\in \mathbb {R} ^{5}}l(x,u,v)\\&=\inf _{x\in \mathbb {R} ^{5}}[c^{\top }x-u^{\top }x+v^{\top }(b-Ax)]\\&=\inf _{x\in \mathbb {R} ^{5}}b^{\top }v+(c-u-A^{\top }v)^{\top }x\\&=\left\{{\begin{array}{rcl}b^{\top }v&,&{\text{ se }}c-u-A^{\top }v=0\\-\infty &,&{\text{ em outros casos}}\end{array}}\right.\end{aligned}}$ Identificar o problema dual $(D)$ $(D)\left\{{\begin{matrix}\max \beta (u,v)\\u\geq 0;\,v\in \mathbb {R} ^{2}\end{matrix}}\right.$ que equivale a $(D)\left\{{\begin{matrix}\max b^{\top }v\\c-u-A^{\top }v=0\\u\geq 0\end{matrix}}\right.$ ou simplesmente $(D)\left\{{\begin{matrix}\max b^{\top }v\\A^{\top }v\leq c\\\end{matrix}}\right.$ Agora, se tem um problema em $\mathbb {R} ^{2}$, 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: $\left\{{\begin{matrix}-v_{1}&+&v_{2}&\leq 2\\2v_{1}&+&v_{2}&\leq 5\\v_{1}&&&\leq 2\\-v_{1}&&&\leq 1\\-v_{2}&&&\leq 1\end{matrix}}\right.$ Tal conjunto é um pentágono (irregular, mas convexo), logo o valor máximo de $b^{\top }v$ é assumido quando $v={\begin{bmatrix}v_{1}\\v_{2}\end{bmatrix}}$ for um dos cinco vértices. Através de simples verificação, comprova-se que o ponto de máximo é $v={\begin{bmatrix}1\\3\end{bmatrix}}$. Conforme a teoria, este ponto é uma solução do problema dual $(D)$. Como $(D)$ é 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 $l$. Considere as condições de KKT: $\nabla _{x}l({\bar {x}},{\bar {u}},{\bar {v}})=c-I{\bar {u}}-A^{\top }{\bar {v}}=0$ ${\bar {u}}\geq 0$ $\nabla _{u}l({\bar {x}},{\bar {u}},{\bar {v}})=-{\bar {x}}\leq 0$, ou seja, ${\bar {x}}\geq 0$ ${\bar {u}}^{\top }\nabla _{u}l({\bar {x}},{\bar {u}},{\bar {v}})={\bar {u}}^{\top }(-{\bar {x}})=0$, ou seja, ${\bar {x}}^{\top }{\bar {u}}=0$ $\nabla _{v}l({\bar {x}},{\bar {u}},{\bar {v}})=b-A{\bar {x}}=0$, ou seja, $A{\bar {x}}=b$ Note que, a partir de 2 e 3, conclui-se que 4 só é possível quando ${\bar {x}}_{i}^{\top }{\bar {u}}_{i}=0,\,\forall i$. Para se obter ${\bar {u}}$, basta lembrar que em $(D)$ se tem: $c-{\bar {u}}-A^{\top }{\bar {v}}=0$ (comprovando 1) Logo, ${\bar {u}}=c-A^{\top }{\bar {v}}={\begin{bmatrix}2\\5\\2\\1\\1\end{bmatrix}}-{\begin{bmatrix}-1&1\\2&1\\1&0\\-1&0\\0&-1\end{bmatrix}}{\begin{bmatrix}1\\3\end{bmatrix}}={\begin{bmatrix}2\\5\\2\\1\\1\end{bmatrix}}-{\begin{bmatrix}2\\5\\1\\-1\\-3\end{bmatrix}}={\begin{bmatrix}0\\0\\1\\2\\4\end{bmatrix}}\geq 0$ comprovando a propriedade (2). Como valem as propriedades (3) e (5), tem-se: $0=x_{1}u_{1}+x_{2}u_{2}+x_{3}u_{3}+x_{4}u_{4}+x_{5}u_{5}=x_{3}+2x_{4}+4x_{5}$ Donde $x_{3}=x_{4}=x_{5}=0$. Resta usar a informação da propriedade (4) para obter $x_{1}$ e $x_{2}$. O sistema $A{\bar {x}}=b$ pode ser escrito como: $\left\{{\begin{matrix}-x_{1}&+&2x_{2}&=1\\x_{1}&+&x_{2}&=1\\&+&3x_{2}&=2\end{matrix}}\right.$ Logo, $x_{2}={\frac {2}{3}}$ e $x_{1}={\frac {1}{3}}$. Se ${\bar {x}}$, ${\bar {u}}$ e ${\bar {v}}$ satisfazem todas as propriedades, então ${\bar {x}}={\begin{bmatrix}{\frac {1}{3}}&{\frac {2}{3}}&0&0&0\end{bmatrix}}^{\top }$ é solução do problema $(P)$, pois todas as condições de KKT são necessárias e suficientes.

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:

Resolução

;Identificar a lagrangiana $l$ $l:\mathbb {R} ^{5}\times \mathbb {R} ^{5}\times \mathbb {R} ^{2}\mapsto \mathbb {R}$ $l(x,u,v)=c^{\top }x-u^{\top }x+v^{\top }(Ax-b)$ Identificar a função $\beta$ $\beta :\mathbb {R} ^{5}\times \mathbb {R} ^{5}\mapsto \mathbb {R} \cup \{-\infty \}$ ${\begin{aligned}\beta (u,v)&=\inf _{x\in \mathbb {R} ^{5}}l(x,u,v)\\&=\inf _{x\in \mathbb {R} ^{5}}[c^{\top }x-u^{\top }x+v^{\top }(Ax-b)]\\&=\inf _{x\in \mathbb {R} ^{5}}-b^{\top }v+(c-u+A^{\top }v)^{\top }x\\&=\left\{{\begin{array}{rcl}-b^{\top }v&,&{\text{ se }}c-u+A^{\top }v=0\\-\infty &,&{\text{ em outros casos}}\end{array}}\right.\end{aligned}}$ Identificar o problema dual $(D)$ $(D)\left\{{\begin{matrix}\max \beta (u,v)\\u\geq 0;\,v\in \mathbb {R} ^{2}\end{matrix}}\right.$ que equivale a $(D)\left\{{\begin{matrix}\max -b^{\top }v\\c-u+A^{\top }v=0\\u\geq 0\end{matrix}}\right.$ ou simplesmente $(D)\left\{{\begin{matrix}\min b^{\top }v\\-A^{\top }v\leq c\\\end{matrix}}\right.$ Novamente, chega-se até um problema em $\mathbb {R} ^{2}$, 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: $\left\{{\begin{matrix}v_{1}&-&v_{2}&\leq 2\\-2v_{1}&-&v_{2}&\leq 5\\-v_{1}&&&\leq 2\\v_{1}&&&\leq 1\\v_{2}&&&\leq 1\end{matrix}}\right.$ Este conjunto também é um pentágono, de modo que o valor mínimo de $b^{\top }v$ é assumido quando $v={\begin{bmatrix}v_{1}\\v_{2}\end{bmatrix}}$ 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 $(D)$, é $v={\begin{bmatrix}-1\\-3\end{bmatrix}}$. Nas condições de KKT, a única mudança é na propriedade (1), que se torna: $c-{\bar {u}}+A^{\top }{\bar {v}}=0$ Resta ainda saber quem é ${\bar {u}}$ e quem é ${\bar {x}}$: ${\bar {u}}=c+A^{\top }{\bar {v}}={\begin{bmatrix}2\\5\\2\\1\\1\end{bmatrix}}+{\begin{bmatrix}-1&1\\2&1\\1&0\\-1&0\\0&-1\end{bmatrix}}{\begin{bmatrix}-1\\-3\end{bmatrix}}={\begin{bmatrix}2\\5\\2\\1\\1\end{bmatrix}}+{\begin{bmatrix}-2\\-5\\-1\\1\\3\end{bmatrix}}={\begin{bmatrix}0\\0\\1\\2\\4\end{bmatrix}}\geq 0$ como antes. Como ao obter ${\bar {u}}$ e ${\bar {v}}$ chegou-se ao mesmo resultado de antes, o ponto ${\bar {x}}$ continuará sendo o mesmo.

Exercício

Formule como um problema de minimização com restrições o problema de projetar ortogonalmente o ponto $(-5,2)$ sobre o conjunto $C=\{(x,y):x\geq 0,y\geq 0\}$. Depois, calcule explicitamente a função lagrangiana e o problema dual.

Resolução

Matematicamente resolver esse problema é resolver ${\begin{cases}{\text{min}}{\frac {1}{2}}[(x+5)^{2}+(y-2)^{2}]\\x\geq 0\ y\geq 0\end{cases}}$ Definimos a lagrangeana como $l(x,y,u,v)={\frac {1}{2}}[(x+5)^{2}+(y-2)^{2}]+u(-x)+v(-y)$ $\beta (u,v)=\inf _{\begin{smallmatrix}x\in \mathbb {R} \\y\in \mathbb {R} \end{smallmatrix}}l(x,y,u,v)$ $\beta (u,v)=\inf _{\begin{smallmatrix}x\in \mathbb {R} \\y\in \mathbb {R} \end{smallmatrix}}[{\frac {1}{2}}[(x+5)^{2}+(y-2)^{2}]-ux-vy]$ Como a função é quadrática , podemos calcular o gradiente e igualar a zero: $\nabla _{x,y}l(x,y,u,v)={\begin{bmatrix}{\bar {x}}+5-u\\{\bar {y}}-2-v\end{bmatrix}}$ $={\begin{bmatrix}0\\0\end{bmatrix}}$ Donde, ${\bar {x}}=u-5$ e ${\bar {y}}=v+2$ Substituindo na função $\beta$ temos: $\beta (u,v)={\frac {1}{2}}[(u-5+5)^{2}+(v+2-2)^{2}]-u(u-5)-v(v+2)$ $\beta (u,v)={\frac {1}{2}}[u^{2}+v^{2}]-u^{2}+5u-v^{2}-2v)$ $\beta (u,v)=-[{\frac {1}{2}}(u^{2}+v^{2})-5u+2v)]$ O problema dual fica então: ${\begin{cases}{\text{max}}-[{\frac {1}{2}}(u^{2}+v^{2})-5u+2v]\\u\geq 0\ v\geq 0\end{cases}}$ Que é equivalente a: ${\begin{cases}{\text{min}}\ {\frac {1}{2}}(u^{2}+v^{2})-5u+2v\\u\geq 0\ v\geq 0\end{cases}}$

Exercício

No exercício anterior, se $u$ é a variável dual relacionada a variável primal $x$ e $v$ é a variável dual relacionada a variável primal $y$, então verifique se $(u,v)=(10,0)$ é 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 ${\begin{cases}{\text{min}}\ {\frac {1}{2}}(u^{2}+v^{2})-5u+2v\\u\geq 0\ v\geq 0\end{cases}}$ observamos que é um problema com restrições. Podemos usar as equações de KKT para resolve-lo. Definimos a lagrangeana como $L(u,v,a,b)={\frac {1}{2}}(u^{2}+v^{2})-5u+2v-au-bv$ Agora usando o teorema de KKT devemos ter: $\nabla _{u,v}L(u,v,a,b)=0$ $u\geq 0$ $v\geq 0$ $a\geq 0$ $b\geq 0$ $-au=0$ $-bv=0$ Calculando o gradiente temos $\nabla _{u,v}L(u,v,a,b)={\begin{bmatrix}{\bar {u}}-5-a\\{\bar {v}}+2-b\end{bmatrix}}$ $={\begin{bmatrix}0\\0\end{bmatrix}}$ E portanto ${\bar {u}}=a+5$ e ${\bar {v}}=b-2$. Olhando nas equações acima obtemos ${\bar {u}}=5$ , ${\bar {v}}=0$, $b=2$ e $a=0$. Portanto $(5,0)$ é a solução dual. Voltando na lagrangiana do problema original e substituindo os multiplicadores de Lagrange obtemos um problema sem restrições: ${\begin{cases}{\text{min}}\ {\frac {1}{2}}[(x+5)^{2}+(y-2)^{2}]+5(-x)\\x,y\in \mathbb {R} \end{cases}}$ Calculando o gradiente temos: $\nabla l(x,y,5,0)={\begin{bmatrix}{\bar {x}}+5-5\\{\bar {y}}-2\end{bmatrix}}$ $={\begin{bmatrix}0\\0\end{bmatrix}}$ Portanto $(0,2)$ é a solução primal. Logo $(0,2,5,0)$ é 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 é ${\frac {25}{2}}$ e o valor ótimo do dual também é ${\frac {25}{2}}$.