Otimização/Métodos duais

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

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.

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.

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 $\theta$ 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 $\alpha > 0$ um número real fixado.

1. Se $\bar{x}$ é um minimizador local de $f$ em $C$, então $\bar{x} = P_C(\bar{x} - \alpha \nabla f (\bar{x}))$
2. 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$.

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

1. 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)$.
2. 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.

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

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:

1. $\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$
2. $u_i \ge 0, \, \forall i = 1, \ldots, p$
3. $u_i g_i(\bar{x}) = 0, \, \forall i = 1, \ldots, q$

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:

1. $\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$
2. $u_i \ge 0, \, \forall i = 1, \ldots, p$
3. $u_i g_i(\bar{x}) = 0, \, \forall i = 1, \ldots, p$
4. $g_i(\bar{x}) \le 0, \, \forall i = 1, \ldots, p$
5. $h_j(\bar{x}) = 0, \, \forall j = 1, \ldots, q$

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

Este módulo 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:

1. $\nabla_x l (\bar{x}, \bar{u}, \bar{v}) = 0$
2. $\bar{u} \ge 0$
3. $\nabla_u l (\bar{x}, \bar{u}, \bar{v}) \le 0$
4. $\bar{u}^\top \nabla_u l (\bar{x}, \bar{u}, \bar{v}) = 0$
5. $\nabla_v l (\bar{x}, \bar{u}, \bar{v}) = 0$

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

1. As funções $\alpha$ e $\beta$ são conhecidas na literatura como funções em dualidade (ou mais frequentemente, funções duais);
2. O problema $(Pr)$ é conhecido como problema primal, enquanto $(D)$ é chamado de problema dual;
3. 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}$;
4. 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:

1. Uma função $f$ é côncava quando $-f$ for convexa.
2. 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.

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 $\alpha$ e $\beta$: $\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 $(Pr)$ é equivalente à minimização do problema original. Por outro lado, através da lagrangiana, obtem-se além do problema primal $(Pr)$, 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 $\beta$ em um poliedro), e que servirá para encontrar o mínimo do problema primal (e consequentemente, do original).

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:

1. $\bar{x}$ é solução de $(Pr)$;
2. $(\bar{u}, \bar{v})$ é solução de $(D)$;
3. $\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 $(Pr)$ Reciprocamente, supondo que $\bar{x}$ é solução do problema $(Pr)$, 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 $\alpha, \beta$ 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$.

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, $\beta(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 $\beta(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$.

Análise do problema

Considerando $(P)$, $(Pr)$, $(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 $2x-2=0$, sendo portanto $x=1$. Note que esta é a solução do problema primal $(Pr)$ (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:

1. Se o problema $(P)$ tem solução, então $\bar{\alpha} = \bar{\beta}$ e os problemas $(Pr)$ e $(D)$ têm solução.
2. Se $(P)$ tem solução, e $(\bar{u}, \bar{v})$ é solução de $(D)$, então as soluções de $(Pr)$ 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 $(Pr)$ 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 $(Pr)$ tem solução e que $\bar{\alpha} = \bar{\beta}$. Seja $\bar{x}$ solução de $(Pr)$. 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 $(Pr)$ 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 $(Pr)$ 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:

1. Primeiramente, resolve-se $(D)$;
2. Depois, constrói-se o problema $(P_{ \bar{u}, \bar{v} })$ e encontra-se uma solução $\bar{x}$ para o mesmo;
3. 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 $(Pr)$), e em consequência, solução de $(P)$.

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 $\alpha$ e $\beta$ 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 $(Pr)$ 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)$.

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)".

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.