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 \ge c\\ Px + Qy = d\\ x \ge 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 \ge c,\,Px + Qy = d,\,x \ge 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{align} 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{align}$

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 \ge 0 \\v \in \mathbb{R}^q\\w \ge 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{align} \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\ge 0;\, w \ge 0 & & \end{array}\right.\\ -\infty & , & \text{ em outros casos} \end{array}\right. \end{align}$

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

$\left\{\begin{matrix} \max c^\top u + d^\top v\\ M^\top u + P^\top v \le a\\ N^\top u + Q^\top v = b\\ u \ge 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}) \le f(x)$ mas isto equivale a $-f(x) \le -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 \ge 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{align} \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{align}$

Logo, o problema dual é:

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

ou ainda

$(D)\left\{\begin{matrix} \max b^\top v\\ A^\top v \le 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 \le 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 \le 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{align} \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{align}$

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

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

ou seja,

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

que equivale a

$(P)\left\{\begin{matrix} \min c^\top x\\ Ax = b\\ x \ge 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) = 230 p + 130 b$ 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,5 p & + & 7,5 b & \le & 240\\ 0,125 p & + & 0,125 b & \le & 5\\ 17,5 p & + & 10 b & \le & 595\\ p \ge 0 & & & & \\ b \ge 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 \le b\\ x \ge 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 \le b \text{ e } x \ge 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{align} \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{align}$ Então, o problema dual é dado por $(D)\left\{\begin{matrix} \max -b^\top u_1\\ A^\top u_1 \ge 0\\ u_1 \ge 0 \end{matrix}\right.$ que é equivalente a $(D)\left\{\begin{matrix} \min b^\top u_1\\ A^\top u_1 \ge 0\\ u_1 \ge 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 \le 130\\ 2,5u_1 + 0,125u_2 + 17,5u_3 \le 230\\ u_1 \ge 0; u_2 \ge 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 Q x + 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 \ge 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 Q x + 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{align} \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 Q x + q^\top x + \alpha + u^\top (b - Ax) + v^\top (-x)]\\ & = \min_{x \in \mathbb{R}^n} [\frac{1}{2}x^\top Q x + (q - v - A^\top u)^\top x + u^\top b + \alpha]\\ \end{align}$

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{align} \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{align}$

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 \ge 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 \ge 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}) \le 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 \ge 0, \quad y \ge 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 \le \|(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 \ge 0; y \ge 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{align} \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{align}$ 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{align} \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{align}$ Logo, o problema dual é $(D)\left\{\begin{matrix} \max \beta(u,v,w)\\ u \ge 0;\, v \ge 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 \ge 0;\, v \ge 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 \ge 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{align} \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{align}$ Identificar o problema dual $(D)$ $(D)\left\{\begin{matrix} \max \beta(u,v)\\ u \ge 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 \ge 0 \end{matrix}\right.$ ou simplesmente $(D)\left\{\begin{matrix} \max b^\top v\\ A^\top v \le 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 & \le 2\\ 2v_1 & + & v_2 & \le 5\\ v_1 & & & \le 2\\ -v_1 & & & \le 1\\ -v_2 & & & \le 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} \ge 0$ $\nabla_u l (\bar{x}, \bar{u}, \bar{v}) = - \bar{x} \le 0$, ou seja, $\bar{x} \ge 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} \ge 0$ comprovando a propriedade (2). Como valem as propriedades (3) e (5), tem-se: $0 = x_1u_1 + x_2u_2 + x_3u_3 + x_4u_4 + x_5u_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{align} \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{align}$ Identificar o problema dual $(D)$ $(D)\left\{\begin{matrix} \max \beta(u,v)\\ u \ge 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 \ge 0 \end{matrix}\right.$ ou simplesmente $(D)\left\{\begin{matrix} \min b^\top v\\ -A^\top v \le 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 & \le 2\\ -2v_1 & - & v_2 & \le 5\\ -v_1 & & & \le 2\\ v_1 & & & \le 1\\ v_2 & & & \le 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} \ge 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 \ge 0, y \ge 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\ge 0 \ y\ge 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\ge 0 \ v\ge 0 \end{cases}$ Que é equivalente a: $\begin{cases} \text{min}\ \frac{1}{2}(u^2+v^2)-5u+2v \\ u\ge 0 \ v\ge 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\ge 0 \ v\ge 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\ge 0$ $v\ge 0$ $a\ge 0$ $b\ge 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}$.