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

Origem: Wikilivros, livros abertos por um mundo aberto.

< Otimização

Ir para: navegação, pesquisa

Otimização

Índice

1 Aplicação à programação linear
- 1.1 Exemplificando com um problema de programação linear
2 Aplicação à programação quadrática
3 Exercícios resolvidos

[editar] 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 $α$ e $β$ 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.

[editar] 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$ .

[editar] Calculando o dual de (PL)

Primeiramente,

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

A função $α$ 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 $β$ 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.$

[editar] 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.$

[editar] 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 haviam 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 livro 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.

[editar] 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 $β$ 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.

[editar] 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.

[editar] Um algoritmo para o método do gradiente projetado

Este algoritmo é bastante simples.

Primeiro passo:
  Escolha  e fixe  $α > 0$ .  
Passo iterativo  $k$ : Enquanto

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.

[editar] 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)$ .

[editar] Exemplo concreto

Seja $C = \{ (x,y); \quad x + y = 1,\quad x \ge 0, \quad y \ge 0\}$ .

Este livro 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 $β$ é:

$\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).

[editar] 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: \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 livro 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 1 u 1 + x 2 u 2 + x 3 u 3 + x 4 u 4 + x 5 u 5 = x 3 + 2 x 4 + 4 x 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 $A x - b$ em vez de $b - A x$ . 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: \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 livro 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 $β$ 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$
$- a u = 0$
$- b v = 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}$ .

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

Origem: Wikilivros, livros abertos por um mundo aberto.

Índice

[editar] Aplicação à programação linear

[editar] Exemplificando com um problema de programação linear

[editar] Calculando o dual de (PL)

[editar] Calculando o dual do dual de (PL)

[editar] Um exemplo numérico contextualizado

[editar] Aplicação à programação quadrática

[editar] Revisão do método do gradiente projetado

[editar] Um algoritmo para o método do gradiente projetado

[editar] Exemplificando a projeção

[editar] Exemplo concreto

[editar] Exercícios resolvidos

Acessos

Ferramentas pessoais

Pesquisa

Navegação

Projecto

Imprimir/exportar

Ferramentas