Considere um problema típico da programação linear como:
![{\displaystyle \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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05f129936fe09d611581ae9cc6bd11e457390038)
onde são dados
,
,
,
,
,
,
e
. Por simplicidade, pode-se ainda adotar a seguinte notação:
![{\displaystyle 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\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/03b23eb7de1ca4a2e75a240b8109eced45911c11)
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:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9795bc33819ea6ded2faee23c6342d088aaa91d)
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
![{\displaystyle \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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf91717fb6c0bd281ccf88ecd5791cd3624c398a)
e
, dada por
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4d20bf7eed8c149991ae2bdb6a1a670f7e73c65)
Logo, considerando que
, o problema dual consiste no seguinte:
![{\displaystyle \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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c1edc7664369ef97e086c26dacefd1259cdcd98)
- Exercício
Verificar que
é uma solução de
![{\displaystyle (P)\left\{{\begin{matrix}\min f(x)\\x\in C\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eef18f83ee28f836454146176366aa8b2b757e7a)
se, e somente se,
![{\displaystyle {\bar {x}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/466e03e1c9533b4dab1b9949dad393883f385d80)
é uma solução de
![{\displaystyle ({\bar {P}})\left\{{\begin{matrix}\max(-f(x))\\x\in C\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c53e87fb9e9d0952079bcad10577b31d2cb11f9d)
- Exercício
Verificar que:
![{\displaystyle \inf _{x\in C}f(x)=-\sup _{x\in C}[-f(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/78c491f5e9259284908c4c5105782e8571b9e64d)
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.
|
O seguinte problema é chamado de problema standard (padrão) de programação linear:
![{\displaystyle (PL)\left\{{\begin{matrix}\min c^{\top }x\\Ax=b\\x\geq 0\\\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a901a546ad2e38754461fb4c2c6463df0200e47)
onde são dados
,
e
.
Primeiramente,
![{\displaystyle l(x,u,v)=c^{\top }x+u^{\top }(-x)+v^{\top }(b-Ax)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3bb6c806616fe5d4c7c63e0f1946d1fd8ce36528)
A função
não precisa ser calculada, pois já se mostrou que
![{\displaystyle \alpha (x)=\left\{{\begin{matrix}f(x)&,{\text{ se }}x\in C\\+\infty &,{\text{ se }}x\not \in C\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df3329b151c422d249fff4217573778198754241)
Por outro lado, quanto à função
tem-se:
![{\displaystyle \beta (u,v)=\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c60919a81be5954f676b901c01d39b06d586cbe1)
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6aa29a9fa7044b4e870a0f8b6a1eee1bf94a2ac2)
Logo, o problema dual é:
![{\displaystyle (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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a585c2e8bab509c6b5c054ae24dd4d980e7ae154)
ou ainda
![{\displaystyle (D)\left\{{\begin{matrix}\max b^{\top }v\\A^{\top }v\leq c\\v\in \mathbb {R} ^{m}\\\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d51c7ae09129a5131e76265c2dbcb0f718cc02d4)
Considere o seguinte problema:
![{\displaystyle (D)\left\{{\begin{matrix}\max b^{\top }v\\A^{\top }v\leq c\\v\in \mathbb {R} ^{m}\\\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d51c7ae09129a5131e76265c2dbcb0f718cc02d4)
que, conforme já foi mostrado em um exercício anteriormente, equivale a
![{\displaystyle (D)\left\{{\begin{matrix}\min -b^{\top }v\\A^{\top }v\leq c\\v\in \mathbb {R} ^{m}\\\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41832a53ce04b44fe18c7b8b4f3db124c5c3ad20)
A lagrangiana é dado por:
![{\displaystyle l(v,y)=-b^{\top }v+y^{\top }(A^{\top }v-c)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15b8754df3414ee76bcebf0b4bea7c9e0d9b8c8a)
Logo,
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/64b3e0e47b720debae6e525aff4d36c42bc3c9b7)
Logo, o dual de
é:
![{\displaystyle (DD)\left\{{\begin{matrix}\max \beta (y)\\y\geq 0\\\end{matrix}}\right.,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/062cec1abef94e7082231a3782caca405d5cfdf4)
ou seja,
![{\displaystyle (DD)\left\{{\begin{matrix}\max -c^{\top }y\\Ay=b\\y\geq 0\\\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09585f1c6676dc137e5432245aab46802c3dac33)
que equivale a
![{\displaystyle (P)\left\{{\begin{matrix}\min c^{\top }x\\Ax=b\\x\geq 0\\\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1a1c46336f1358e3be78cd03e2110dfc5c31862)
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:
![{\displaystyle g(p,b)=230p+130b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/575068df453ec159ee70d74b601af30c3bf513d2)
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:
![{\displaystyle \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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31e5257e09e8bd28cb67ae6db5cc468a94cfe557)
Pode-se simplificar a escrita das restrições e também da função objetivo utilizando a seguinte notação:
![{\displaystyle 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2d2035c28be89f3a49073429df47df4ecaaa371)
Nesses termos, o problema de otimização a ser resolvido é:
![{\displaystyle \left\{{\begin{matrix}\max c^{\top }x\\Ax\leq b\\x\geq 0\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d475ff1424cfe3bb2fa33137212f2bedc2dc0c8d)
ou apenas,
![{\displaystyle \left\{{\begin{matrix}\max c^{\top }x\\x\in C\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e3fe8c00ec8d112f57af4c51c6d4d6d8e1285cd)
onde é o conjunto definido pelo conjunto de restrições:
![{\displaystyle C=\left\{(p,b);Ax\leq b{\text{ e }}x\geq 0\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a0d7763543c952d5749c38801cc5fd6cf884b7d)
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
![{\displaystyle l(x,u_{1},u_{2})=-c^{\top }x+u_{1}^{\top }(Ax-b)+u_{2}^{\top }(-x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/515709728726e4ce560b7e5a8247d4191d69eaba)
Donde
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27250eb024fcfe8c2e68b50168724881e65ab3ec)
Então, o problema dual é dado por
![{\displaystyle (D)\left\{{\begin{matrix}\max -b^{\top }u_{1}\\A^{\top }u_{1}\geq 0\\u_{1}\geq 0\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce3486c604a3164e30d901c635c0e57755c0d304)
que é equivalente a
![{\displaystyle (D)\left\{{\begin{matrix}\min b^{\top }u_{1}\\A^{\top }u_{1}\geq 0\\u_{1}\geq 0\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f65baaefca4959c0b65c77680a6ab31d9e7240de)
ou, escrevendo novamente em termos dos valores numéricos,
![{\displaystyle (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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a0e32b76d4a5593a25f7e5f3852b21a0c6caaad)
|
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.
|
Agora, o problema a considerar passa a ser
![{\displaystyle \left\{{\begin{matrix}\min {\frac {1}{2}}x^{\top }Qx+q^{\top }x+\alpha \\x\in C\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6257f2404cc40329f53cde15309a9172d81491fd)
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
![{\displaystyle C=\left\{x\in \mathbb {R} ^{n};x\geq 0{\text{ e }}Ax=b\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ec7cb91f2235c91ef2103dbcb31da06e7baed22)
com
e
.
Agora será aplicado o esquema de dualidade. A lagrangiana é
![{\displaystyle l:\mathbb {R} ^{n}\times \mathbb {R} ^{n}\times \mathbb {R} ^{m}\mapsto \mathbb {R} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c99bfabb807eb078bab7bf604dc5563efc2c01aa)
![{\displaystyle 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9316d756b6d3622e4537ce2670637b6663ce9a73)
além disso,
![{\displaystyle \beta :\mathbb {R} ^{n}\times \mathbb {R} ^{m}\mapsto \mathbb {R} \cup \{-\infty \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70cb36f348f3520f97a2e31885d6c53a7813b726)
![{\displaystyle \beta (u,v)=\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)=\min _{x\in \mathbb {R} ^{n}}l(x,u,v)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/94f43bf9a62ca9ee1c8aaacce5960442fa0eb243)
e a última igualdade vale pois a função é fortemente convexa.
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc3b26f3818cb072ed0ff02a6f2d0d197e78dfe)
Considerando
, se deduz que
.
Logo,
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e1e44a9bfbc6d4aa51eee2654faf5e605253179)
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 é
![{\displaystyle (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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6919e59f6b14629dc986cb167ccaa0dbe7eedf52)
ou seja,
![{\displaystyle (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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6d3c4cc36b122b6cf2c04f3fb9b710da6191a5e)
Usualmente este tipo de problema
é resolvido por meio do método do gradiente projetado.
O método baseia-se na seguinte proposição:
Prova
|
Esta prova é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.
|
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
![{\displaystyle P_{C}\left({\begin{bmatrix}x\\y\end{bmatrix}}\right)={\begin{bmatrix}\max\{x,0\}\\0\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43ad1514fec2993a4888b5df07ef34df30d2307b)
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.
|
Seja
. Então a projeção de
sobre
é :
![{\displaystyle 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 }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/06072943c061e6d45f9b1102e9d72dd2c9616580)
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
.
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:
![{\displaystyle \|{\bar {P}}-(1,2)\|^{2}\leq \|(x,y)-(1,2)\|^{2},\quad \forall (x,y)\in C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8c34722df1fd7d39b3c855a92cae6110b123e9d)
Então:
![{\displaystyle {\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0fa95f3689ef3ac31d05106765118133d1fec091)
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 é
![{\displaystyle (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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d144caecdd943e7fd612ef700be25e1fd18f5e22)
A lagrangiana é dada por
![{\displaystyle l(x,y,u,v,w)={\frac {1}{2}}\left[(x-1)^{2}+(y-2)^{2}\right]-ux-vy+w(1-x-y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8746439bd51c747f4e607d636f436f749dec212)
Logo,
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/052f7b8f409d7d4c2db6e665766d6a820856ca6f)
Fazendo tem-se:
![{\displaystyle {\begin{bmatrix}{\bar {x}}-1-(u+w)\\{\bar {y}}-2-(v+w)\end{bmatrix}}={\begin{bmatrix}0\\0\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/294462d4a10e1699cb02b524f948da13f7af2fc8)
Donde
![{\displaystyle {\begin{bmatrix}{\bar {x}}\\{\bar {y}}\end{bmatrix}}={\begin{bmatrix}u+w+1\\v+w+2\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0cff6293f7a2267ef79f18abae3061595d4be06d)
Logo,
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d17baabd72efebb074f80c05af6d0f1a2fcadfa)
Logo, o problema dual é
![{\displaystyle (D)\left\{{\begin{matrix}\max \beta (u,v,w)\\u\geq 0;\,v\geq 0;\,w\in \mathbb {R} ^{m}\\\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e46221f133ed9765e8682cbd8322d6245390f7e2)
ou seja,
![{\displaystyle (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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88059a5bb181cb90f094214106d5e5f200a70649)
Agora, para a resolução deste problema dual, pode-se usar o método do gradiente projetado.
Para isso, note que o gradiente de é:
![{\displaystyle \nabla \beta (u,v,w)={\begin{bmatrix}u+w+1\\v+w+2\\u+v+2w+2\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1660ee3e92208c76b39707d4d6ee547902943276)
- Passo 0
Seja e escolha .
- Passo 1
- Passo 2
Logo, a solução dual é
![{\displaystyle {\begin{bmatrix}{\bar {u}}\\{\bar {v}}\\{\bar {w}}\end{bmatrix}}={\begin{bmatrix}0\\0\\-1\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/734a0aa7d298067001acadda8e48d108500b2457)
Agora, substituindo tal solução na lagrangiana, obtem-se o problema:
![{\displaystyle (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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89baa1521eeb9fcd71c7dcbb03f7decbfcd0778e)
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ício
Encontrar a solução do seguinte problema de programação linear:
![{\displaystyle \left\{{\begin{matrix}\min c^{\top }x\\Ax=b\\x\geq 0\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a41fe356f7bc96780fb33880b661d1177d3adcd)
sendo
![{\displaystyle c^{\top }={\begin{bmatrix}2&5&2&1&1\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c63e2d73b2ab60fe38b4d02fb687afccd75487c)
![{\displaystyle A={\begin{bmatrix}-1&2&1&-1&0\\1&1&0&0&-1\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff60956bcc34ef3de39c42c4d274826811511f0f)
![{\displaystyle b^{\top }={\begin{bmatrix}1&1\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/602e1eabfa940ea3374ab2a6627c65a8081e8ac2)
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
![{\displaystyle l}](https://wikimedia.org/api/rest_v1/media/math/render/svg/829091f745070b9eb97a80244129025440a1cfac)
![{\displaystyle l:\mathbb {R} ^{5}\times \mathbb {R} ^{5}\times \mathbb {R} ^{2}\mapsto \mathbb {R} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8cea8bf40aedca714e9dccda5630c6d367a6903)
![{\displaystyle l(x,u,v)=c^{\top }x-u^{\top }x+v^{\top }(b-Ax)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/956b9e6054d72de5d7d7b3978e588a65b2a7d56b)
- Identificar a função
![{\displaystyle \beta }](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ed48a5e36207156fb792fa79d29925d2f7901e8)
![{\displaystyle \beta :\mathbb {R} ^{5}\times \mathbb {R} ^{5}\mapsto \mathbb {R} \cup \{-\infty \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c5fea5f5c9961eb3322a9478d0771551bcd0ca1)
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/201890738663e2481680d82aa8ba93c8324fe597)
- Identificar o problema dual
![{\displaystyle (D)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cbcb66c83c0cf2a2d0e26d456072eef521e6823)
![{\displaystyle (D)\left\{{\begin{matrix}\max \beta (u,v)\\u\geq 0;\,v\in \mathbb {R} ^{2}\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fc16b295a1e43d79410d44afea3bda4778c85bf)
que equivale a
![{\displaystyle (D)\left\{{\begin{matrix}\max b^{\top }v\\c-u-A^{\top }v=0\\u\geq 0\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32dc0e6b429adf8322762939326062ab6bd28d52)
ou simplesmente
![{\displaystyle (D)\left\{{\begin{matrix}\max b^{\top }v\\A^{\top }v\leq c\\\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac772d8a6228fe2b8c136b0241736ea49c897ff5)
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:
![{\displaystyle \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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/765877d23300352d7e36208a7f5d1a7bffad8b4c)
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:
![{\displaystyle \nabla _{x}l({\bar {x}},{\bar {u}},{\bar {v}})=c-I{\bar {u}}-A^{\top }{\bar {v}}=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/767e64d2164f43512fe900e83ec0137ae5d427bd)
![{\displaystyle {\bar {u}}\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52d20999cfd9e6aabcbb01add632f68c06aa7abe)
, ou seja, ![{\displaystyle {\bar {x}}\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48b542bb3792cb3fc13918f77b81ae71feaf5ac0)
, ou seja, ![{\displaystyle {\bar {x}}^{\top }{\bar {u}}=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f10a12b6c4c02862d32493d6e2f581868bdccb4)
, ou seja, ![{\displaystyle A{\bar {x}}=b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb4aabd83baa69fb3f30c9233e99ca6af3008eb9)
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:
![{\displaystyle 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/38efc26714c5c7529e79ff53804abe19771a2516)
Donde . Resta usar a informação da propriedade (4) para obter e . O sistema pode ser escrito como:
![{\displaystyle \left\{{\begin{matrix}-x_{1}&+&2x_{2}&=1\\x_{1}&+&x_{2}&=1\\&+&3x_{2}&=2\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/247bae1d4a3feebcc310620c9725047d584c35a6)
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
![{\displaystyle l:\mathbb {R} ^{5}\times \mathbb {R} ^{5}\times \mathbb {R} ^{2}\mapsto \mathbb {R} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8cea8bf40aedca714e9dccda5630c6d367a6903)
![{\displaystyle l(x,u,v)=c^{\top }x-u^{\top }x+v^{\top }(Ax-b)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/77ce46563bb1ab60aa3b29da9b0e4d39a7d62307)
- Identificar a função
![{\displaystyle \beta }](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ed48a5e36207156fb792fa79d29925d2f7901e8)
![{\displaystyle \beta :\mathbb {R} ^{5}\times \mathbb {R} ^{5}\mapsto \mathbb {R} \cup \{-\infty \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c5fea5f5c9961eb3322a9478d0771551bcd0ca1)
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e7d864b5f6d196acb889804e0cad857659dcb8e)
- Identificar o problema dual
![{\displaystyle (D)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cbcb66c83c0cf2a2d0e26d456072eef521e6823)
![{\displaystyle (D)\left\{{\begin{matrix}\max \beta (u,v)\\u\geq 0;\,v\in \mathbb {R} ^{2}\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fc16b295a1e43d79410d44afea3bda4778c85bf)
que equivale a
![{\displaystyle (D)\left\{{\begin{matrix}\max -b^{\top }v\\c-u+A^{\top }v=0\\u\geq 0\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48e08e275cf528b58437d9d31122805e0299825a)
ou simplesmente
![{\displaystyle (D)\left\{{\begin{matrix}\min b^{\top }v\\-A^{\top }v\leq c\\\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/450bee41991224b79c238b6c74413c3185874200)
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:
![{\displaystyle \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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1ccd617aecd144b330651fd6ed124ccaa432bda)
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:
![{\displaystyle c-{\bar {u}}+A^{\top }{\bar {v}}=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30ad023efb8c005c36604bf7720f7a7562489025)
Resta ainda saber quem é e quem é :
![{\displaystyle {\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49e36016ae79ed36ddae01ab1e9e286f6286b093)
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:
|
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:
![{\displaystyle \nabla _{u,v}L(u,v,a,b)=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5856503b985f504ab7eebcee063262fc6668e8fb)
![{\displaystyle u\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3dab5b88f0c9e756fe41d3e632de584f6bffcde2)
![{\displaystyle v\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b83ef9770a86a11dfb1be6808c501b16b8e9748)
![{\displaystyle a\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c33f2f7ac8b81e1296d581427bdb2d30a50a2b12)
![{\displaystyle b\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb90a1049b38d6a352b9bde75bda4cd2f76515dc)
![{\displaystyle -au=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/596145e7848f07f7eef073918655a6ecf4a86fe9)
![{\displaystyle -bv=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/647f7ae2e719cfd0cb9bc774c8183efdb2418917)
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 é .
|