# 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.$

### Exercício

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

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

## 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$.

#### Um algoritmo para o método do gradiente projetado

Este algoritmo é bastante simples.
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}}$

### 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\}$.
Como calcular a projeção do ponto $(1,2)$ sobre o conjunto $C$, $P_{C}(1,2)$?

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

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

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