Otimização/Métodos duais

Origem: Wikilivros, livros abertos por um mundo aberto.

< Otimização

Ir para: navegação, pesquisa

Otimização

Índice

1 Lagrangiana
2 Condições de otimalidade
- 2.1 Caso particular
- 2.2 Caso geral
  - 2.2.1 Exemplos de condições de qualificação das restrições
3 Uma inequação sobre ínfimos e supremos
- 3.1 Exemplo numérico: problema primal e seu dual
4 Ponto de sela
- 4.1 Exemplos
- 4.2 Análise do problema
5 Resumo do esquema de dualidade
- 5.1 Conclusões
6 Uma nota sobre a terminologia

[editar] Lagrangiana

O conceito de lagrangiana está sempre relacionado ao seguinte problema:

$(P)\left\{\begin{matrix} \min f(x)\\ g_i(x) \le 0; i = 1, \ldots, p\\ h_j(x) = 0; j = 1, \ldots, q \end{matrix}\right.$

Definição

A função lagrangiana associada ao problema $(P)$ é

$l:\mathbb{R}^n \times \mathbb{R}^p \times \mathbb{R}^q \mapsto \mathbb{R}$ definida por

$l(x, u, v) = f(x) + \sum_{i=1}^{p} u_i g_i (x) + \sum_{j=1}^{q} v_j h_j (x)$ .

A Wikipédia tem mais sobre este assunto:

Multiplicadores de Lagrange

Em alguns livros é usada a seguinte notação:

$G:\mathbb{R}^n \mapsto \mathbb{R}^p$ definida por

$G(x) = \begin{bmatrix} g_1(x)\\ \vdots \\ g_p(x)\end{bmatrix}$

e

$H:\mathbb{R}^n \mapsto \mathbb{R}^q$ definida por

$H(x) = \begin{bmatrix} h_1(x)\\ \vdots \\ h_q(x)\end{bmatrix}$

Deste modo, a lagrangiana fica expressa por

$l(x, u, v) = f(x) + u^\top G(x) + v^\top H(x)$

que é uma representação bem mais compacta.

[editar] Condições de otimalidade

Para permitir a compreensão da importância da função lagrangiana em otimização, é preciso ter em mente os principais resultados que garantem a otimalidade de uma solução para o problema $(P)$ . Nas próximas seções será apresentado um breve resumo das condições de otimalidade, dividindo-as em dois casos:

Caso particular: quando $C = \{ x \in \mathbb{R}^n; g_i(x) \le 0 \text{ e } h_j(x) = 0\}$ é convexo e fechado.
Caso geral: quando $C$ é arbitrário.

[editar] Caso particular

Proposição

Seja $f$ função de classe $\mathcal{C}^1$ no conjunto $C$ . Se $\bar{x}$ é um minimizador local de $f$ no conjunto convexo e fechado $C$ , então:

$\langle \nabla f(x), x - \bar{x} \rangle \ge 0, \, \forall x \in C$

Demonstração

Seja $\bar{x} \in C$ uma solução de

(P)

, e fixe um ponto arbitrário $x \in C$ . Denote por

θ

a restrição da função

f

sobre o segmento de reta que passa por

x

e por $\bar{x}$ , ou seja,

$\theta (t) = f(\bar{x} + t (x - \bar{x}))$ , com $t \in (0, 1)$ .

Note que $\theta(0) = f(\bar{x})$ .

Como $\bar{x}$ é um minimizador de $f$ em $C$ , tem-se:

$\theta(t) = f(\bar{x} + t (x - \bar{x})) \ge f(\bar{x}) = \theta(0)$ , para todo $t \in (0, 1)$

Logo,

$\frac{\theta(t) - \theta(0)}{t - 0} \ge 0$ , ou seja, $\theta'(0) = \lim_{t \to 0} \frac{\theta(t) - \theta(0)}{t - 0} \ge 0$

Mas pela regra da cadeia,

$\theta'(0) = \langle \nabla f(\bar{x}), x - \bar{x}\rangle$ , então $\langle \nabla f(\bar{x}), x - \bar{x}\rangle \ge 0$ .

Como $x \in C$ era arbitrário, o resultado está demonstrado.

Observação

A condição $\langle u, v \rangle \ge 0$ significa que os vetores $u$ e $v$ formam um ângulo reto ou agudo (menor ou igual a 90 graus), conforme indicado na figura a seguir:

Em um ponto de mínimo, $\nabla f$ sempre forma ângulo menor ou igual a 90 graus com os vetores do tipo $x-\bar{x}$ , onde $\bar{x}$ é um ponto de mínimo da função no conjunto viável

C

e

x

é um ponto qualquer deste conjunto.

No caso específico, com $u=\nabla f$ e $v=x-\bar{x}$ , $\langle u, v \rangle$ é a derivada direcional de $f$ na direção $x-\bar{x}$ . Quando tal número é não negativo, intuitivamente a função cresce naquela direção.

Quando $C$ é um conjunto convexo e fechado, a existência de uma solução para o problema $(P)$ é garantida pela seguinte proposição:

Proposição

Se $\bar{x} \in C$ , $f$ é convexa e

$\langle \nabla f(x), x - \bar{x} \rangle \ge 0, \, \forall x \in C$

então $\bar{x}$ é um minimizador global de

f

no conjunto

C

(isto é, $\bar{x}$ é solução de

(P)

).

Demonstração

Pela convexidade de

f

, tem-se que:

$f(x) \ge f(\bar{x}) + \langle \nabla f(x), x - \bar{x} \rangle, \, \forall x \in \mathbb{R}^n$

Logo,

$f(x) - f(\bar{x}) \ge \langle \nabla f(x), x - \bar{x} \rangle \ge 0, \, \forall x \in C$

Portanto, $f(x) \ge f(\bar{x}), \, \forall x \in C$ , ou seja, $\bar{x}$ é um minimizador de $f$ em $C$ .

Até aqui, não é exigido que qualquer das funções $g i$ ou $h j$ sejam diferenciáveis. Isto será utilizado mais adiante, nos algoritmos.

A próxima proposição fornece uma caracterização dos minimizadores, em termos do conceito de projeção.

Lembre-se que a projeção de um ponto $\bar{y}$ sobre o conjunto $C$ , denotada por $\bar{P} = P_C (\bar{y})$ , satisfaz $\langle \bar{P} - \bar{y}, x - \bar{P} \rangle \ge 0, \, \forall x \in C$ . Na verdade, vale:

$\bar{P} = P_C (\bar{y}) \Leftrightarrow \langle \bar{P} - \bar{y}, x - \bar{P} \rangle \ge 0, \, \forall x \in C$

O vetor $\bar{P}-\bar{y}$ forma ângulo menor que 90 graus com o vetor $x - \bar{P}$ , pois $\bar{P}$ é a projeção de $\bar{y}$ sobre o conjunto

C

.

Proposição

Seja $α > 0$ um número real fixado.

Se $\bar{x}$ é um minimizador local de $f$ em $C$ , então $\bar{x} = P_C(\bar{x} - \alpha \nabla f (\bar{x}))$
Se $f$ é convexa e $\bar{x} = P_C(\bar{x} - \alpha \nabla f (\bar{x}))$ , então $\bar{x}$ é um minimizador global de $f$ em $C$ .

Demonstração

(1)

Como $\bar{x}$ é um minimizador local de $f$ em $C$ , então

$\langle \nabla f(x), x - \bar{x} \rangle \ge 0, \, \forall x \in C$

Observe que essa desigualdade equivale à

$\langle \alpha \nabla f(x), x - \bar{x} \rangle \ge 0, \, \forall x \in C$

ou ainda

$\langle \bar{x} - (\bar{x} - \alpha \nabla f(x)), x - \bar{x} \rangle \ge 0, \, \forall x \in C$

Tomando $\bar{y} = \bar{x} - \alpha \nabla f(x)$ e $P = \bar{x}$ , tem-se a equivalência com:

$\langle P - \bar{y}, x - P \rangle \ge 0, \, \forall x \in C$

que equivale a dizer que $P = P_C(\bar{y})$ , ou seja:

$\bar{x} = P = P_C(\bar{y}) = P_C(\bar{x} - \alpha \nabla f(x))$

(2)

Reciprocamente, supor que $\bar{x} = P = P_C(\bar{y}) = P_C(\bar{x} - \alpha \nabla f(x))$ , conforme a argumentação anterior, equivale a dizer que

$\langle \nabla f(x), x - \bar{x} \rangle \ge 0, \, \forall x \in C$

Usando a hipótese de que $f$ é convexa, segue da proposição anterior que $\bar{x}$ é um minimizador global de $f$ em $C$ .

[editar] Caso geral

Para tratar este caso, é preciso utilizar o conceito de cone tangente. O conjunto contínua o mesmo, ou seja, $C = \{ x \in \mathbb{R}^n; g_i(x) \le 0 \text{ e } h_j(x) = 0\}$ , embora não seja mais suposto que ele é convexo. Mesmo assim, $C$ ainda será fechado, pois as funções $g i$ e $h j$ que o definem são contínuas.

Teorema

Se $\bar{x}$ é um minimizador local de $f$ em $C$ , então $\langle \nabla f(\bar{x}) , d \rangle \ge 0, \, \forall d \in T(\bar{x}, C)$ .
Se $C$ é convexo, $f$ é convexa e $\langle \nabla f(\bar{x}) , d \rangle \ge 0, \, \forall d \in T(\bar{x}, C)$ , então $\bar{x}$ é minimizador global de $f$ em $C$ .

Este teorema pode ser demonstrado de forma análoga a que foi feita anteriormente.

Demonstração
Esta demonstração é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

Seja $\tilde{C}$ definido como:

$\tilde{C} = \tilde{C}_a = \left\{x \in \mathbb{R}^n; g_i(x) \le 0, \, \forall i \in I(a);\quad h_j(x) = 0 \right\}$ .

Pela segunda propriedade do cone tangente, tem-se:

$T(a, V \cap \tilde{C}) = T(a, C) = T(a, V \cap \tilde{C})$ . Logo,

$T(a, C) = T(a, \tilde{C})$

Em outras palavras, se é dado um conjunto $\tilde{C}$ e depois se restringe tal conjunto para $C$ , através do acréscimo de restrições inativas em um ponto $a$ , os cones tangentes aos dois conjuntos (no ponto $a$ ) coincidem.

Definição

Toda condição que implica que $T (a, C) = L (a, C)$ é chamada de condição de qualificação das restrições.

A Wikipédia tem mais sobre este assunto:

Condições de qualificação das restrições

Observação: Também se pode dizer condições de regularidade das restrições (do inglês, Regularity conditions).

[editar] Exemplos de condições de qualificação das restrições

(1) Se $g i$ e $h i$ são funções afim-lineares, então para qualquer $x \in C$ , tem-se $T (x, C) = L (x, C)$ . Prova-se isso trivialmente

Prova
Esta prova é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

(2) Condições de Slater: Se as funções $g i$ são convexas e as $h i$ são afim lineares e, além disso, existe $\hat{x} \in C$ tal que $g_i(\hat{x}) < 0$ para todo $i$ , $h_j (\hat{x}) = 0$ , então para qualquer $x \in C$ , tem-se $T (x, C) = L (x, C)$ .

Prova
Esta prova é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

(3) Condições de Mangasarian-Fromowitz: Se $\{\nabla h_j(x)\}$ é linearmente independente e existe $\tilde{d}$ tal que $\langle \nabla h_j(x), \tilde{d}\rangle = 0$ para tpdp $j$ e $\langle \nabla g_i(x), \tilde{d}\rangle < 0$ .

Prova
Esta prova é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

Teorema (Karush–Kuhn–Tucker)

Suponha que $f$ , $g i$ e $h j$ são funções de classe $\mathcal{C}^1$ em uma vizinhança do ponto $\bar{x}$ e que $T(\bar{x}, C) = L(\bar{x}, C)$ . Se $\bar{x}$ é um minimizador local de $f$ em $C$ , então existem $u \in \mathbb{R}^p$ e $v \in \mathbb{R}^q$ tais que:

$\nabla f(\bar{x}) + \sum_{i=1}^p u_i \nabla g_i(\bar{x}) + \sum_{j=1}^q v_j \nabla h_j(\bar{x}) = 0$
$u_i \ge 0, \, \forall i = 1, \ldots, p$
$u_i g_i(\bar{x}) = 0, \, \forall i = 1, \ldots, q$

A Wikipédia tem mais sobre este assunto:

Condições de Karush-Kuhn-Tucker

Note que aqui aparece a lagrangiana, pois a primeira condição é equivalente a:

$\nabla_x l(x, u, v) = 0$

O essencial para a existência de $l (u, v)$ é que $T(\bar{x}, C) = L(\bar{x}, C)$ .

Teorema

Suponha-se que $f$ , $g i$ e $h j$ são funções de classe $\mathcal{C}^1$ em uma vizinhança de $\bar{x}$ , que $f$ e $g i$ são convexas e que $h j$ são afim-lineares. são funções de classe $\mathcal{C}^1$ . Se existem $u \in \mathbb{R}^p$ e $v \in \mathbb{R}^q$ tais que:

$\nabla f(\bar{x}) + \sum_{i=1}^p u_i \nabla g_i(\bar{x}) + \sum_{j=1}^q v_i \nabla h_j(\bar{x}) = 0$
$u_i \ge 0, \, \forall i = 1, \ldots, p$
$u_i g_i(\bar{x}) = 0, \, \forall i = 1, \ldots, p$
$g_i(\bar{x}) \le 0, \, \forall i = 1, \ldots, p$
$h_j(\bar{x}) = 0, \, \forall j = 1, \ldots, q$

A partir deste teorema são construídos alguns algoritmos.

Este livro tem a seguinte tarefa pendente: Confrontar as informações presentes nestes últimos teoremas com algum livro. Parece estar precisando de pequenas correções.

Considere o seguinte problema:

$\left\{\begin{matrix} \min f(x)\\ g_i(x) \le 0; i = 1, \ldots, p\\ h_j(x) = 0; j = 1, \ldots, q \end{matrix}\right.$

Sabe-se que $l:\mathbb{R}^n \times \mathbb{R}^p \times \mathbb{R}^q \mapsto \mathbb{R}$ dada por

$l(x, u, v) = f(x) + \sum_{i=1}^{p} u_i g_i (x) + \sum_{j=1}^{q} v_j h_j (x)$ .

Agora, tem-se as KKT:

Teorema

Supondo que $f, g i$ e $h j$ são de classe $\mathcal{C}^1$ em uma vizinhança de $\bar{x} \in C$ e que $T(\bar{x}, C) = L(\bar{x}, C)$ , se $\bar{x}$ é um minimizador local de $f$ em $C$ , então $\exists \bar{u} \in \mathbb{R}^p$ tal que $\exists \bar{v} \in \mathbb{R}^q$ de modo que:

$\nabla_x l (\bar{x}, \bar{u}, \bar{v}) = 0$
$\bar{u} \ge 0$
$\nabla_u l (\bar{x}, \bar{u}, \bar{v}) \le 0$
$\bar{u}^\top \nabla_u l (\bar{x}, \bar{u}, \bar{v}) = 0$
$\nabla_v l (\bar{x}, \bar{u}, \bar{v}) = 0$

[editar] Uma inequação sobre ínfimos e supremos

Teorema

Sejam $X \subset \mathbb{R}^n$ e $Y \subset \mathbb{R}^m$ dois subconjuntos arbitrários e considere uma aplicação $K: X \times Y \mapsto \mathbb{R}$ . Então

$- \infty \le \sup_{y \in Y} \inf_{x \in X} K(x, y) \le \inf_{x \in X} \sup_{y \in Y} K(x, y) \le + \infty$

Demonstração

Sabe-se que

$K(x, y) \le \sup_{y \in Y} K(x, y) \le + \infty$ ,

quaisquer que sejam $x \in X, y \in Y$ . Então, calculando o ínfimo em ambos os membros (com relação aos valores de $x$ ), e considerando que $K (x, y)$ pode ser ilimitado inferiormente, tem-se para qualquer $y \in Y$ :

$- \infty \le \inf_{x \in X} K(x, y) \le \inf_{x \in X} \sup_{y \in Y} K(x, y) \le + \infty$

Assim, calculando o supremo (com relação aos valores de $y$ ), segue das desigualdades anteriores:

$- \infty \le \sup_{y \in Y} \inf_{x \in X} K(x, y) \le \inf_{x \in X} \sup_{y \in Y} K(x, y) \le + \infty$

Exercício

Verifique que:

$- \infty \le \sup_{\begin{smallmatrix}u \ge 0\\v \in \mathbb{R}^q \end{smallmatrix}} \inf_{x \in \mathbb{R}^n} l(x, u, v) \le \inf_{x \in \mathbb{R}^n} \sup_{\begin{smallmatrix}u \ge 0\\v \in \mathbb{R}^q \end{smallmatrix}} l(x, u, v) \le + \infty$

Demonstração
Esta demonstração é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a neste módulo.

Defina-se a função:

$\alpha: \mathbb{R}^n \mapsto \mathbb{R} \cup \{+\infty\}$ , dada por

$\alpha(x) = \sup_{\begin{smallmatrix}u \ge 0 \\v \in \mathbb{R}^q \end{smallmatrix}} l(x, u, v)$

e também

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

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

Conforme o exercício anterior, tem-se então

$- \infty \le \sup_{\begin{smallmatrix}u \ge 0 \\v \in \mathbb{R}^q\end{smallmatrix}} \beta(u, v) \le \inf_{x \in \mathbb{R}^n} \alpha(x) \le + \infty$

Observando a relação entre essas funções, é natural considerar dois problemas de otimização:

$(Pr)\left\{\begin{matrix} \min \alpha(x)\\ x \in \mathbb{R}^n \end{matrix}\right.$

e

$(D)\left\{\begin{matrix} \max \beta(u, v)\\ u \ge 0\\ v \in \mathbb{R}^q \end{matrix}\right.$

Comentários

As funções $α$ e $β$ são conhecidas na literatura como funções em dualidade (ou mais frequentemente, funções duais);
O problema $(P r)$ é conhecido como problema primal, enquanto $(D)$ é chamado de problema dual;
Fazendo $\bar{\alpha} = \inf_{x \in \mathbb{R}^n} \alpha (x)$ e $\bar{\beta} = \sup_{\begin{smallmatrix}u \ge 0 \\v \in \mathbb{R}^q\end{smallmatrix}} \beta(u, v)$ , segue-se do exercício anterior que $\bar{\beta} \le \bar{\alpha}$ ;
A diferença $\bar{\alpha} - \bar{\beta}$ é chamada de brecha de dualidade, ou salto de dualidade (do inglês, skip duality);

Exercício

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

Resolução

Se $x\in C$ tem-se que $g_i(x) \le 0; i = 1, \ldots, p$ e $h_j(x) = 0; j = 1, \ldots, q$ .

Substituindo na lagrangeana tem-se que $l(x, u, v)\leq f(x)$ e tomando $u = 0$ , se vê que o supremo dos valores $l (x, u, v)$ é atingido, tendo $f (x)$ como valor.

Por outro lado, se $x\notin C$ existe um índice $j$ tal que $h_j(x)\neq 0$ e/ou $g i (x) > 0$ . No primeiro caso, seja $u = 0$ e

$v_j=\begin{cases} th_i(x), & i=j \\ 0, & i\ne j \end{cases}$ , onde

t > 0

.

Com esta escolha, a lagrangiana será

l (x, u, v) = f (x) + t (h j (x)) 2

.

Tomando o limite quando $t \rightarrow \infty$ tem-se que $l(x, u, v)\rightarrow \infty$ .

Para o outro caso a prova é análoga.

Exercício

Verifique que $(D)$ consiste de maximizar uma função côncava em um poliedro. Lembre-se:

Uma função $f$ é côncava quando $- f$ for convexa.
Um poliedro é qualquer intersecção finita de semiespaços fechados.

Resolução

Primeiro será mostrado que : $\beta: [ 0, +\infty )^p \times \mathbb{R}^q \mapsto \mathbb{R} \cup \{-\infty\}$ , dada por $\beta(u, v) = \inf_{x \in \mathbb{R}^n} l(x, u, v)$ é uma função côncava. Para isso, basta mostrar que para cada $t\in [0, 1]$ vale

$\beta(ta+(1-t)b, tc+(1-t)d)\ge t\beta(a, c)+(1-t)\beta(b, d)$ .

Chamando $\bar{u}=ta+(1-t)b$ e $\bar{v}=tc+(1-t)d$ tem-se:

$\begin{align} \beta(\bar{u}, \bar{v})& = \inf_{x \in \mathbb{R}^n} l(x, ta+(1-t)b, tc+(1-t)d)\\ & = \inf_{x \in \mathbb{R}^n} f(x)+(ta+(1-t)b)^{\top}g(x)+(tc+(1-t)d)^{\top}h(x)\\ & = \inf_{x \in \mathbb{R}^n} f(x)+ta^{\top}g(x)+(1-t)b^{\top}g(x)+tc^{\top}h(x)+(1-t)d^{\top}h(x)\\ & = \inf_{x \in \mathbb{R}^n} tf(x)+(1-t)f(x) +ta^{\top}g(x)+(1-t)b^{\top}g(x)+tc^{\top}h(x)+(1-t)d^{\top}h(x)\\ & = \inf_{x \in \mathbb{R}^n} t[f(x)+a^{\top}g(x)+c^{\top}h(x)]+(1-t)[f(x)+b^{\top}g(x)+d^{\top}h(x)]\\ & = \inf_{x \in \mathbb{R}^n} tl(x, a, c)+(1-t)l(x, b, d)\\ & \ge \inf_{x \in \mathbb{R}^n} tl(x, a, c)+\inf_{x \in \mathbb{R}^n} (1-t)l(x, b, d)\\ & = t\inf_{x \in \mathbb{R}^n} l(x, a, c)+(1-t)\inf_{x \in \mathbb{R}^n} l(x, b, d)\\ & =t\beta(a, c)+(1-t)\beta(b, d). \end{align}$

Quanto ao conjunto ser um poliedro, isso segue do fato de $\mathbb{R}^q$ e $u\ge 0$ serem interseções finitas de semiespaços fechados.

[editar] Exemplo numérico: problema primal e seu dual

Considere o problema

$(P) \left\{\begin{matrix} \min x^2\\ 1 \le x \le 2 \end{matrix}\right.$

Resolução

O problema é ilustrado na imagem a direita.

Primeiramente, é preciso identificar quais são as funções $f, g i$ e $h j$ envolvidas:

A função objetivo é aquela que se pretende minimizar, ou seja, $f: \mathbb{R} \mapsto \mathbb{R}; f(x) = x^2$ ;
Como aparecem apenas restrições de desigualdade, não há qualquer função $h j$ ;
Reescrevendo as desigualdades como $1-x \le 0$ e $x-2 \le 0$ , conclúi-se que as funções $g i$ são:

$g_1: \mathbb{R} \mapsto \mathbb{R}; g_1(x) = 1-x$ e $g_2: \mathbb{R} \mapsto \mathbb{R}; g_2(x) = x-2$ .

Neste caso, a lagrangiana é:

$l: \mathbb{R} \times \mathbb{R}^2 \mapsto \mathbb{R}$ , dado por

l (x, u 1, u 2) = x 2 + u 1 (1 - x) + u 2 (x - 2)

Em seguida, é preciso calcular $α$ e $β$ :

$\alpha: \mathbb{R}^n \mapsto \mathbb{R} \cup \{+\infty\}$ , é dada por

$\alpha(x) = \sup_{\begin{smallmatrix}u_1 \ge 0\\u_2 \ge 0\end{smallmatrix}} [x^2 + u_1 (1-x) + u_2 (x-2) ] = x^2 + \sup_{u_1 \ge 0} [ u_1 (1-x) ] + \sup_{u_2 \ge 0} [ u_2 (x-2) ]$

E, conforme um dos exercícios anteriores (ou através de uma breve análise dos supremos envolvidos na expressão anterior), tem-se:

$\alpha(x) = \left\{\begin{matrix} x^2 & , \text{ se } x \in [1, 2]\\ +\infty & , \text{ se } x \not\in [1, 2] \end{matrix}\right.$

Analogamente, tem-se:

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

$\beta(u_1, u_2) = \inf_{x \in \mathbb{R}^n} [x^2 + u_1 (1-x) + u_2 (x-2) ]$

Observe que em relação a $x$ , tem-se uma função fortemente convexa, que portanto possui um único minimizador. Além disso, $l$ é diferenciável, donde o seu único minimizador $x 0$ é dado pela equação:

$\nabla_x l (x_0, u_1, u_2) = 0$

ou seja,

2 x 0 + u 1 - u 2 = 0

donde

$x_0 = \frac{u_2 - u_1}{2}$

Portanto,

$\beta(u_1, u_2) =\left( \frac{u_1 - u_2}{2}\right)^2 + u_1 \left(1- \frac{u_1 - u_2}{2}\right) + u_2 \left( \frac{u_1 - u_2}{2}-2\right)$

Assim, os problemas em dualidade são:

$(Pr)\left\{\begin{matrix} \min \alpha(x)\\ x \in \mathbb{R}^n \end{matrix}\right.$

e

$(D)\left\{\begin{matrix} \max \beta(u_1, u_2)\\ u_1, u_2 \ge 0 \end{matrix}\right.$

Pelo primeiro item do exercício, tem-se que a minimização do problema $(P r)$ é equivalente à minimização do problema original.

Por outro lado, através da lagrangiana, obtem-se além do problema primal $(P r)$ , um problema dual $(D)$ , cuja estrutura é muito melhor que a do original (pois pelo outro exercício, consiste da maximização de uma função côncava $β$ em um poliedro), e que servirá para encontrar o mínimo do problema primal (e consequentemente, do original).

[editar] Ponto de sela

Este é um conceito muito importante relacionado à lagrangiana.

Definição

Dado o problema $(P)$ e a lagrangiana $l$ associada à esse problema, se diz que $(\bar{x}, \bar{u}, \bar{v})$ é um ponto de sela de $l$ se $\bar{u} \ge 0$ e:

$l(\bar{x}, u, v) \le l(\bar{x}, \bar{u}, \bar{v}) \le l(x, \bar{u}, \bar{v}), \forall x \in \mathbb{R}^n, \forall u \ge 0, \forall v \in \mathbb{R}^q$ .

Teorema

O ponto $(\bar{x}, \bar{u}, \bar{v})$ é um ponto de sela de $l$ se, e somente se:

$\bar{x}$ é solução de $(P r)$ ;
$(\bar{u}, \bar{v})$ é solução de $(D)$ ;
$\bar{\alpha} = \bar{\beta}$ .

Demonstração

Se $(\bar{x}, \bar{u}, \bar{v})$ é um ponto de sela de

l

, então $\bar{u} \ge 0$ e se tem:

$l(\bar{x}, u, v) \le l(\bar{x}, \bar{u}, \bar{v}) \le l(x, \bar{u}, \bar{v}), \forall x \in \mathbb{R}^n, \forall u \ge 0, \forall v \in \mathbb{R}^q$ .

Em particular, como

$\alpha (\bar{x}) = \sup_{\begin{smallmatrix}u \ge 0\\v \in \mathbb{R}^q \end{smallmatrix}} l(\bar{x}, u, v) \le l(\bar{x}, \bar{u}, \bar{v})$ .

segue da segunda desigualdade que

$\bar{\alpha} \le \alpha(\bar{x}) \le l(\bar{x}, \bar{u}, \bar{v}) \le l(x, \bar{u}, \bar{v}), \forall x \in \mathbb{R}^n$

e calculando o ínfimo sobre todos os $x \in \mathbb{R}$ tem-se:

$\bar{\alpha} \le \alpha(\bar{x}) \le l(\bar{x}, \bar{u}, \bar{v}) \le \inf_{x \in \mathbb{R}^n} l(x, \bar{u}, \bar{v}) = \beta(\bar{u}, \bar{v}) \le \bar{\beta}$

Por outro lado, da inequação sobre ínfimos e supremos, tem-se $\bar{\alpha} \ge \bar{\beta}$ , então $\bar{\alpha} = \bar{\beta}$ .

Logo, todos os membros das desigualdades acima coincidem, ou seja,

$\bar{\alpha}(\bar{x}) =l(\bar{x}, \bar{u}, \bar{v}) = \beta(\bar{u}, \bar{v}) = \bar{\beta}$

Mas da definição de $\bar{\beta}$ tem-se:

$\bar{\beta} = \sup_{\begin{smallmatrix}u \ge 0\\v \in \mathbb{R}^q\end{smallmatrix}} \beta(u, v)$ .

Portanto, $(\bar{u}, \bar{v})$ é solução do problema $(D)$ enquanto $\bar{\alpha} = \inf_{x \in \mathbb{R}^n} \alpha (x)$ significa que $\bar{x}$ é solução de $(P r)$

Reciprocamente, supondo que $\bar{x}$ é solução do problema $(P r)$ , tem-se:

$\alpha(\bar{x}) = \inf_{x \in \mathbb{R}^n} \alpha(x)$

e admitindo que $(\bar{u}, \bar{v})$ é solução do problema $(D)$ , segue:

$\beta(\bar{u}, \bar{v}) = \sup_{\begin{smallmatrix}u \ge 0 \\v \in \mathbb{R}^q \end{smallmatrix}} \beta(u, v)$

Além disso, usando como hipótese que $\bar{\alpha} = \bar{\beta}$ , segue da definição que:

$l(\bar{x}, u, v) \le \alpha(\bar{x}) = \bar{\alpha} = \bar{\beta} = \beta(\bar{u}, \bar{v}) \le l(x, \bar{u}, \bar{v})$ , quaisquer que sejam $x \in \mathbb{R}^n, u \ge 0, v \in \mathbb{R}^q$ .

Em particular, tomando $u = \bar{u}$ , $v = \bar{v}$ e $x = \bar{x}$ , resulta:

$l(\bar{x}, \bar{u}, \bar{v}) \le \bar{\alpha} = \bar{\beta} \le l(\bar{x}, \bar{u}, \bar{v})$ , ou seja,

$l(\bar{x}, \bar{u}, \bar{v}) = \bar{\alpha} = \bar{\beta}$

Logo, pela definição de $α,β$ tem-se:

$l(\bar{x}, u, v) \le \alpha(\bar{x})= l(\bar{x}, \bar{u}, \bar{v}) = \beta(\bar{x}) = l(x, \bar{u}, \bar{v})$ , quaisquer que sejam $x \in \mathbb{R}^n, u \ge 0, v \in \mathbb{R}^q$ .

Portanto, $(\bar{x}, \bar{u}, \bar{v})$ é um ponto de sela da lagrangiana $l$ .

A Wikipédia tem mais sobre este assunto:

Ponto de sela

[editar] Exemplos

Considere novamente o problema de otimização dado por:

$\left\{\begin{matrix} \min x^2\\ 1 \le x \le 2 \end{matrix}\right.$

Verificar se a lagrangiana associada à $(P)$ tem ponto de sela.

Resolução

O problema é ilustrado na imagem a direita, e conforme foi deduzido anteriormente, tem-se:

$f: \mathbb{R} \mapsto \mathbb{R}; f(x) = x^2$
$g_1: \mathbb{R} \mapsto \mathbb{R}; g_1(x) = 1-x$
$g_2: \mathbb{R} \mapsto \mathbb{R}; g_2(x) = x-2$
$l: \mathbb{R} \times \mathbb{R}^2 \mapsto \mathbb{R}; l(x, u_1, u_2) = x^2 + u_1 (1-x) + u_2 (x-2)$

Além disso, como foi mostrado anteriormente, vale

$\alpha (x) = \left\{\begin{matrix} x^2 & , \text{ se } x \in [1, 2]\\ +\infty & , \text{ se } x \not\in [1, 2] \end{matrix}\right.$

e também

$\beta(u, v) = \left( \frac{u_1 - u_2}{2}\right)^2 + u_1 \left(1- \frac{u_1 - u_2}{2}\right) + u_2 \left( \frac{u_1 - u_2}{2}-2\right)$

ou seja,

$\begin{align} \beta(u, v) & = \frac{1}{4} ( [u_1^2 + u_2^2 - 2u_1u_2] + [4u_1 - 2u_1^2 + 2 u_1 u_2] + [2u_1u_2 - 2u_2^2 - 8u_2])\\ & = \frac{-1}{4} ( u_1^2 + u_2^2 - 2u_1u_2 - 4u_1 + 8u_2)\\ & = \frac{-1}{4} ( (u_1 - u_2)^2 - 4(u_1 - u_2)) - u_2\\ & = \frac{-1}{4} ( (u_1 - u_2)^2 - 4(u_1 - u_2) + 4) + 1 - u_2\\ & = \frac{-1}{4} (u_1 - u_2 - 2)^2 + 1 - u_2 \end{align}$

Agora, consideram-se os seguintes problemas em dualidade:

$(Pr)\left\{\begin{matrix} \min \alpha(x)\\ x \in \mathbb{R}^n \end{matrix}\right.$

e

$(D)\left\{\begin{matrix} \max \beta(u_1, u_2)\\ u_1, u_2 \ge 0 \end{matrix}\right.$

Donde $\bar{x} = 1$ é solução do problema primal, e $\alpha(\bar{x}) = 1$ .

Intuitivamente, nos pontos em que $\beta(u_1, u_2) = \frac{-1}{4} (u_1 - u_2 - 2)^2 + 1 - u_2$ assumir seu valor máximo, deve-se ter $u 2 = 0$ , pois conforme $u 2$ aumenta, $β(u 1, u 2)$ decresce.

Mas pela desigualdade a respeito de supremos e ínfimos, tem-se $\beta(u_1, u_2) \le \alpha (\bar{x}) = 1$ , quaisquer que sejam $u_1 \ge 0$ , $u_2 \ge 0$ .

Como $\beta(u_1, u_2) \le 1$ , e ao tomar $u 1 = 2$ e $u 2 = 0$ tem-se $β(2,0) = 1$ , segue-se que $(\bar{u_1}, \bar{u_2}) = (2, 0)$ é uma solução do problema dual $(D)$ .

Finalmente, como $\bar{\alpha}=\alpha(\bar{x}) = 1$ , e $\bar{\beta} = \beta(\bar{u_1}, \bar{u_2}) = 1$ , segue que $\bar{\alpha} = \bar{\beta}$ . Portanto, pelo teorema anterior, o ponto $(\bar{x}, \bar{u_1}, \bar{u_2})$ é ponto de sela da lagrangiana $l$ .

[editar] Análise do problema

Considerando $(P)$ , $(P r)$ , $(D)$ e $l$ , se $(\bar{u}, \bar{v})$ é uma solução do problema dual, considere o seguinte problema:

$(P_{ \bar{u}, \bar{v} })\left\{\begin{matrix} \min l(x, \bar{u}, \bar{v})\\ x \in \mathbb{R} \end{matrix}\right.$

que no caso do exemplo reduz-se a

$(P_{ \bar{u}, \bar{v} })\left\{\begin{matrix} \min x^2 + 2(1-x)\\ x \in \mathbb{R} \end{matrix}\right.$

A solução deste problema é obtida resolvendo $2 x - 2 = 0$ , sendo portanto $x = 1$ . Note que esta é a solução do problema primal $(P r)$ (e consequentemente do problema original $(P)$ ).

Será apenas uma coincidência? Ou ainda, em que situações a solução deste último problema será também solução do problema original?

A resposta será dada pelo próximo teorema. Acompanhe.

Teorema (dualidade lagrangiana convexa)

Suponha-se que $f, g_i: \mathbb{R}^n \mapsto \mathbb{R}$ são de classe $\mathcal{C}^1$ e convexas, e que as funções $h j$ são afim lineares e $T(x, C) = L(x, C), \forall x \in C$ . Nestas condições:

Se o problema $(P)$ tem solução, então $\bar{\alpha} = \bar{\beta}$ e os problemas $(P r)$ e $(D)$ têm solução.
Se $(P)$ tem solução, e $(\bar{u}, \bar{v})$ é solução de $(D)$ , então as soluções de $(P r)$ são as soluções de $(P_{\bar{u}, \bar{v}})$ , onde

$(P_{ \bar{u}, \bar{v} })\left\{\begin{matrix} \min l(x, \bar{u}, \bar{v})\\ x \in \mathbb{R} \end{matrix}\right.$

que também são as soluções de

(P)

.

Antes da demonstração, vale a pena imaginar a seguinte aplicação da segunda parte do teorema: Se por alguma razão não se sabe resolver o problema original $(P)$ , pode-se optar por resolver $(D)$ (um problema concavo em um poliedro), e depois resolver $(P_{ \bar{u}, \bar{v} })$ (que é um problema convexo sem restrições). Em outras palavras, é possível trocar um problema difícil por dois problemas mais fáceis, $(D)$ e $(P_{ \bar{u}, \bar{v} })$ .

Agora a demonstração do teorema:

Demonstração

(1) Como

(P)

tem solução, seja $\bar{x}$ uma solução de

(P)

. Pelo teorema de KKT (que se aplica pois as funções são de classe $\mathcal{C}^1$ e se tem a qualificação das restrições), segue a existência de $\bar{u} \in \mathbb{R}^p$ e $\bar{v} \in \mathbb{R}^q$ , tais que:

$\nabla_x l (\bar{x}, \bar{u}, \bar{v}) = 0$
$\bar{u} \ge 0$
$\nabla_u l (\bar{x}, \bar{u}, \bar{v}) \le 0$
$\bar{u}^\top \nabla_u l (\bar{x}, \bar{u}, \bar{v}) = 0$
$\nabla_v l (\bar{x}, \bar{u}, \bar{v}) = 0$

Como $f, g i$ são funções convexas e $h j$ afim lineares, então a função lagrangiana $l(x, \bar{u}, \bar{v})$ é convexa em $x$ (pela forma de $l$ ). Isto significa que:

$l(x, \bar{u}, \bar{v}) \ge l(\bar{x}, \bar{u}, \bar{v}) + < \nabla_x l(\bar{x}, \bar{u}, \bar{v}), x-\bar{x}>, \forall x \in \mathbb{R}^n$ .

Usando (1), conclúi-se uma das duas desigualdades que definem um ponto de sela em $(\bar{x}, \bar{u}, \bar{v})$ :

$l(x, \bar{u}, \bar{v}) \ge l(\bar{x}, \bar{u}, \bar{v})$ .

Considerando que $\bar{x}$ é solução de $(P)$ , tal ponto satisfaz as restrições $g_i(x) \le 0; i = 1, \ldots, p$ e $h_j(x) = 0; j = 1, \ldots, q$ . Então, usando $l(\bar{x}, u, v) = f(\bar{x}) + \sum_{i=1}^{p} u_i g_i (\bar{x}) + \sum_{j=1}^{q} v_j h_j (\bar{x})$ , segue que:

$l(\bar{x}, u, v) \le f(\bar{x})$

pois $h_j (\bar{x}) = 0$ e $u_i \ge 0$ .

Mas, por KKT, $0 = \bar{u}^\top \nabla_u l (\bar{x}, \bar{u}, \bar{v}) = \sum_{i=1}^{p} \bar{u}_i g_i (\bar{x})$ . Além disso, $\sum_{j=1}^{q} \bar{v}_j h_j (\bar{x}) = 0$ .

Logo:

$l(\bar{x}, \bar{u}, \bar{v}) = f(\bar{x}) + \sum_{i=1}^{p} \bar{u}_i g_i (\bar{x}) + \sum_{j=1}^{q} \bar{v}_j h_j (\bar{x}) = f(\bar{x})$

Assim,

$l(x, \bar{u}, \bar{v}) \ge l(\bar{x}, \bar{u}, \bar{v}) \ge l(\bar{x}, u, v)$

quaisquer que sejam $x \in \mathbb{R}^n$ , $u \ge 0$ e $v \in \mathbb{R}^q$ . Mas isso implica, por definição, que $(\bar{x}, \bar{u}, \bar{v})$ é um ponto de sela de $l$ .

Logo, $\bar{\alpha} = \bar{\beta}$ , $\bar{x}$ é solução do problema primal $(P r)$ e $(\bar{u}, \bar{v})$ é solução do problema dual $(D)$

(2)Seja $(\bar{u}, \bar{v})$ solução de $(D)$ (que existe, pelo item 1). Sabe-se pelo item anterior que o problema primal $(P r)$ tem solução e que $\bar{\alpha} = \bar{\beta}$ .

Seja $\bar{x}$ solução de $(P r)$ . Então, $(\bar{x}, \bar{u}, \bar{v})$ é ponto de sela de $l$ , logo valem as desigualdades:

$l(\bar{x}, u, v) \le l(\bar{x}, \bar{u}, \bar{v}) \le l(x, \bar{u}, \bar{v}), \forall x \in \mathbb{R}^n, \forall u \ge 0, \forall v \in \mathbb{R}^q$ .

Uma vez que $( \bar{u}, \bar{v} )$ está fixo e a segunda desigualdade vale para qualquer $x \in \mathbb{R}^n$ , conclui-se que $\bar{x}$ é solução do problema

$(P_{ \bar{u}, \bar{v} })\left\{\begin{matrix} \min l(x, \bar{u}, \bar{v})\\ x \in \mathbb{R} \end{matrix}\right.$

As soluções deste problema são soluções de $(P r)$ e, consequentemente, do problema original.

Exercício

Verificar se existe salto de dualidade nos problemas em dualidade para o seguinte problema de minimização:

$(P_1)\left\{\begin{matrix} \min x-y^2\\ x^2 + y^2 \le 1\\ x + y \le 1 \end{matrix}\right.$

Exercício

Juntamente com o problema $(P 1)$ do exercício anterior, considere o seguinte problema:

$(P_2)\left\{\begin{matrix} \min x-y^2\\ x \ge 0\\ y \ge 0\\ x + y \le 1 \end{matrix}\right.$

Os problemas são equivalentes? (no sentido de que têm as mesmas funções objetivo e o mesmo conjunto de restrições) O que acontece com relação às condições de KKT? Apesar de

f (x, y) = x - y 2

não ser convexa, é válido o resultado do teorema? Para que serve KKT? É possível resolver o problema dual e usar a resposta para resolver o primal?

Exercício

Experimente escolher $x \in \mathbb{R}^5$ e uma transformação linear, e um poliedro (intersecção finita de semi-espaços). É difícil de resolver o problema primal. Tente resolver o dual, usando os métodos conhecidos.

A seguir será apresentada uma proposição que responde a uma pergunta deixada anteriormente:

Proposição

Considere o problema $(P)$ a lagrangiana $l$ e os problemas em dualidade $(P r)$ e $(D)$ e $(\bar{u}, \bar{v})$ soluções de $(D)$ . Se $\bar{x}$ é solução do problema

$(P_{ \bar{u}, \bar{v} })\left\{\begin{matrix} \min l(x, \bar{u}, \bar{v})\\ x \in \mathbb{R} \end{matrix}\right. ,$

$\bar{x} \in C$ (o conjunto dos pontos que satisfazem as restrições) e $g_i(\bar{x})\bar{u}_i = 0, \forall i$ , então $\bar{x}$ é também uma solução do problema

(P)

.

Tal proposição fornece um roteiro para quem precisa resolver o problema $(P)$ relativamente difícil:

Primeiramente, resolve-se $(D)$ ;
Depois, constrói-se o problema $(P_{ \bar{u}, \bar{v} })$ e encontra-se uma solução $\bar{x}$ para o mesmo;
Finalmente, se $\bar{x}$ satisfaz as últimas condições da proposição, ele é também uma solução de $(P)$ .

Demonstração

Se $(\bar{u}, \bar{v})$ é uma solução de

(D)

, $\bar{\beta} = \beta (\bar{u}, \bar{v})$ . Então, pela definição de $\beta (\bar{u}, \bar{v})$ , tem-se:

$\bar{\beta} = \sup_{\begin{smallmatrix}u \ge 0 \\v \in \mathbb{R}^q\end{smallmatrix}} \beta(u, v)$

Como $\bar{x}$ é solução de $(P_{ \bar{u}, \bar{v} })$ , então:

$l(\bar{x}, \bar{u}, \bar{v}) \le l(x, \bar{u}, \bar{v}), \forall x \in \mathbb{R}^n$

ou seja,

$l(\bar{x}, \bar{u}, \bar{v}) = \min_{x \in \mathbb{R}^n} l(x, \bar{u}, \bar{v}) = \inf_{x \in \mathbb{R}^n} l(x, \bar{u}, \bar{v}) = \bar{\beta}$

Portanto,

$l(\bar{x}, \bar{u}, \bar{v}) = \bar{\beta} = \beta (\bar{u}, \bar{v})$

Por outro lado, como $x \in C$ , tem-se $g_i(x) \le 0; i = 1, \ldots, p$ e $h_j(x) = 0; j = 1, \ldots, q$ .

Por hipótese, $g_i(\bar{x})\bar{u}_i = 0$ , então

$\sum_{i=1}^{p} \bar{u}_i g_i (\bar{x}) = 0 = \sum_{j=1}^{q} \bar{v}_j h_j (\bar{x})$

Logo,

$l(\bar{x}, \bar{u}, \bar{v}) = f(\bar{x}) + \sum_{i=1}^{p} \bar{u}_i g_i (\bar{x}) + \sum_{j=1}^{q} \bar{v}_j h_j (\bar{x}) = f(\bar{x})$ .

Então para $u \ge 0$ tem-se que $u_i g_i(\bar{x}) \le 0, \forall i$ e $v_j h_j(\bar{x}) = 0, \forall j$ . Consequentemente,

$l(\bar{x}, u, v) = f(\bar{x}) + \sum_{i=1}^{p} u_i g_i (\bar{x}) + \sum_{j=1}^{q} v_j h_j (\bar{x}) \le f(\bar{x})$

quaisquer que sejam $u \ge 0, v \in \mathbb{R}^q$ , ou seja,

$l(\bar{x}, u, v) = f(\bar{x}) = l(\bar{x}, \bar{u}, \bar{v}) \le l(x, \bar{u}, \bar{v})$ ,

quaisquer que sejam $u \ge 0, v \in \mathbb{R}^q$ .

Portanto, $(\bar{x}, \bar{u}, \bar{v})$ é ponto de sela de $l$ , e assim, $\bar{x}$ é solução primal (solução de $(P r)$ ), e em consequência, solução de $(P)$ .

[editar] Resumo do esquema de dualidade

Neste ponto, pode-se sintetizar a estratégia geral para a resolução de problemas de otimização utilizando esquemas de dualidade.

Considere o problema

$\left\{\begin{matrix} \min f(x)\\ g_i(x) \le 0; i = 1, \ldots, p\\ h_j(x) = 0; j = 1, \ldots, q \end{matrix}\right.$

onde $f, g_i, h_j:\mathbb{R}^n \mapsto \mathbb{R}$ são funções de classe $\mathcal{C}^1 (\mathbb{R}^n)$ , e seja a lagrangiana $l:\mathbb{R}^n \times \mathbb{R}^p \times \mathbb{R}^q \mapsto \mathbb{R}$ definido por

$l(x, u, v) = f(x) + \sum_{i=1}^{p} u_i g_i (x) + \sum_{j=1}^{q} v_j h_j (x)$ .

Convenciona-se que:

$x$ é a variável primal;
$(u, v)$ é a variável dual;

Nesse sentido, "o $\mathbb{R}^p \times \mathbb{R}^q$ é o dual de $\mathbb{R}^n$ " (não confundir com o significado que essa expressão teria na análise funcional. Ver nota sobre a terminologia), ou seja:

$\mathbb{R}^n$ é onde "mora" a variável primal $x$ ;
$\mathbb{R}^p \times \mathbb{R}^q$ é onde "mora" a variável dual $(u, v)$ ;

Definem-se então as funções $α$ e $β$ da seguinte maneira:

$\alpha: \mathbb{R}^n \mapsto \mathbb{R} \cup \{+\infty\}$ , dada por

$\alpha(x) = \sup_{\begin{smallmatrix}u \ge 0 \\v \in \mathbb{R}^q \end{smallmatrix}} l(x, u, v)$

e

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

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

A partir destas duas funções, formulam-se os seguintes problemas duais:

$(Pr)\left\{\begin{matrix} \min \alpha(x)\\ x \in \mathbb{R}^n \end{matrix}\right.$

e

$(D)\left\{\begin{matrix} \max \beta(u, v)\\ u \ge 0\\ v \in \mathbb{R}^q \end{matrix}\right.$

É possível verificar que $(P r)$ equivale ao problema original $(P)$ e que $(D)$ consiste da maximização de uma função côncava em um poliedro (convexo).

Logo, o dual de $(P)$ é $(D)$ .

[editar] Conclusões

Dado qualquer problema $(P)$ , seu dual $(D)$ é um problema côncavo (isto é, a função objetivo é côncava), tal que os pontos satisfazendo o conjunto de restrições formam um poliedro convexo.

Apesar da controvérsia filosófica existente acerca do nome destes conceitos (coisa que poderia muito bem vir a ser alterada no futuro), a moral da história é que "transforma-se um problema geralmente difícil (sem estrutura) em um problema mais fácil (cheio de estrutura)".

[editar] Uma nota sobre a terminologia

Na subárea da matemática denominada Análise Funcional, quando se tem um espaço topológico $X$ , costuma-se chamar de dual topológico ao conjunto $X^* = \{ t : X \mapsto \mathbb{R}; t \text{ é linear e continua} \}$ .

Aparentemente, os conceitos de dual da otimização e da análise funcional não tem relação um com o outro.

Um dos primeiros a falar de dualidade (espaços duais) foi o francês Fenchel, mas foi fortemente criticado por Urruty e Lemaréchal, pois os dois conceitos de dualidade não estão relacionados. Também o francês Brezis concordou que há um problema a ser resolvido com a nomenclatura, e um dos conceitos deveria deixar de ser chamado assim.

A Wikipédia tem mais sobre este assunto:

Análise funcional

Otimização/Métodos duais

Origem: Wikilivros, livros abertos por um mundo aberto.

Índice

[editar] Lagrangiana

[editar] Condições de otimalidade

[editar] Caso particular

[editar] Caso geral

[editar] Exemplos de condições de qualificação das restrições

[editar] Uma inequação sobre ínfimos e supremos

[editar] Exemplo numérico: problema primal e seu dual

[editar] Ponto de sela

[editar] Exemplos

[editar] Análise do problema

[editar] Resumo do esquema de dualidade

[editar] Conclusões

[editar] Uma nota sobre a terminologia

Acessos

Ferramentas pessoais

Pesquisa

Navegação

Projecto

Imprimir/exportar

Ferramentas