Mostrar código-fonte de Otimização/Métodos duais



== Lagrangiana ==
O conceito de lagrangiana está sempre relacionado ao seguinte problema:
:<math>(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.</math>

{{Definição
|A '''função lagrangiana''' associada ao problema <math>(P)</math> é
:<math>l:\mathbb{R}^n \times \mathbb{R}^p \times \mathbb{R}^q \mapsto \mathbb{R}</math> definida por
:<math>l(x, u, v) = f(x) + \sum_{i=1}^{p} u_i g_i (x) + \sum_{j=1}^{q} v_j h_j (x)</math>.
}}

{{Wikipédia|Multiplicadores de Lagrange}}

Em alguns livros é usada a seguinte notação:
:<math>G:\mathbb{R}^n \mapsto \mathbb{R}^p</math> definida por
:<math>G(x) = \begin{bmatrix} g_1(x)\\ \vdots \\ g_p(x)\end{bmatrix}</math>
e
:<math>H:\mathbb{R}^n \mapsto \mathbb{R}^q</math> definida por
:<math>H(x) = \begin{bmatrix} h_1(x)\\ \vdots \\ h_q(x)\end{bmatrix}</math>

Deste modo, a lagrangiana fica expressa por
:<math>l(x, u, v) = f(x) + u^\top G(x) + v^\top H(x)</math>
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 <math>(P)</math>. Nas próximas seções será apresentado um breve resumo das condições de otimalidade, dividindo-as em dois casos:
* Caso particular: quando <math>C = \{ x \in \mathbb{R}^n; g_i(x) \le 0 \text{ e } h_j(x) = 0\}</math> é convexo e fechado.
* Caso geral: quando <math>C</math> é arbitrário.

=== Caso particular ===

{{Proposição
|Seja <math>f</math> função de classe <math>\mathcal{C}^1</math> no conjunto <math>C</math>. Se <math>\bar{x}</math> é um minimizador local de <math>f</math> no conjunto convexo e fechado <math>C</math>, então:
:<math>\langle \nabla f(x), x - \bar{x} \rangle \ge 0, \, \forall x \in C</math>
}}
{{Demonstração
|Seja <math>\bar{x} \in C</math> uma solução de <math>(P)</math>, e fixe um ponto arbitrário <math>x \in C</math>. Denote por <math>\theta</math> a restrição da função <math>f</math> sobre o segmento de reta que passa por <math>x</math> e por <math>\bar{x}</math>, ou seja, 
:<math>\theta (t) = f(\bar{x} + t (x - \bar{x}))</math>, com <math>t \in (0, 1)</math>.

Note que <math>\theta(0) = f(\bar{x})</math>.

Como <math>\bar{x}</math> é um minimizador de <math>f</math> em <math>C</math>, tem-se:
:<math>\theta(t) = f(\bar{x} + t (x - \bar{x})) \ge f(\bar{x}) = \theta(0)</math>, para todo <math>t \in (0, 1)</math>
Logo, 
:<math>\frac{\theta(t) - \theta(0)}{t - 0} \ge 0</math>, ou seja, <math>\theta'(0) = \lim_{t \to 0} \frac{\theta(t) - \theta(0)}{t - 0} \ge 0</math>
Mas pela regra da cadeia, 
:<math>\theta'(0) = \langle \nabla f(\bar{x}), x - \bar{x}\rangle</math>, então <math>\langle \nabla f(\bar{x}), x - \bar{x}\rangle \ge 0</math>.

Como <math>x \in C</math> era arbitrário, o resultado está demonstrado.
}}
;Observação
A condição <math>\langle u, v \rangle \ge 0</math> significa que os vetores <math>u</math> e <math>v</math> formam um ângulo reto ou agudo (menor ou igual a 90 graus), conforme indicado na figura a seguir:

[[Imagem:Gradiente de uma função em um ponto de mínimo.svg|400px|center|thumb|Em um ponto de mínimo, <math>\nabla f</math> sempre forma ângulo menor ou igual a 90 graus com os vetores do tipo <math>x-\bar{x}</math>, onde <math>\bar{x}</math> é um ponto de mínimo da função no conjunto viável <math>C</math> e <math>x</math> é um ponto qualquer deste conjunto.]]

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


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

{{Proposição
|Se <math>\bar{x} \in C</math>, <math>f</math> é convexa e
:<math>\langle \nabla f(x), x - \bar{x} \rangle \ge 0, \, \forall x \in C</math>
então <math>\bar{x}</math> é um minimizador global de <math>f</math> no conjunto <math>C</math> (isto é, <math>\bar{x}</math> é solução de <math>(P)</math>).
}}
{{Demonstração
|Pela convexidade de <math>f</math>, tem-se que:
:<math>f(x) \ge f(\bar{x}) + \langle \nabla f(x), x - \bar{x} \rangle, \, \forall x \in \mathbb{R}^n</math>
Logo, 
:<math>f(x) - f(\bar{x}) \ge \langle \nabla f(x), x - \bar{x} \rangle \ge 0, \, \forall x \in C</math>
Portanto, <math>f(x) \ge f(\bar{x}), \, \forall x \in C</math>, ou seja, <math>\bar{x}</math> é um minimizador de <math>f</math> em <math>C</math>.
}}

Até aqui, não é exigido que qualquer das funções <math>g_i</math> ou <math>h_j</math> 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 <math>\bar{y}</math> sobre o conjunto <math>C</math>, denotada por <math>\bar{P} = P_C (\bar{y})</math>, satisfaz <math>\langle \bar{P} - \bar{y}, x - \bar{P} \rangle \ge 0, \, \forall x \in C</math>. Na verdade, vale:
:<math>\bar{P} = P_C (\bar{y}) \Leftrightarrow \langle \bar{P} - \bar{y}, x - \bar{P} \rangle \ge 0, \, \forall x \in C</math>

[[Image:Propriedade das projeções.svg|center|540px|thumb|O vetor <math>\bar{P}-\bar{y}</math> forma ângulo menor que 90 graus com o vetor <math>x - \bar{P}</math>, pois <math>\bar{P}</math> é a projeção de <math>\bar{y}</math> sobre o conjunto <math>C</math>.]]

{{Proposição
|Seja <math>\alpha > 0</math> um número real fixado.
# Se <math>\bar{x}</math> é um minimizador local de <math>f</math> em <math>C</math>, então <math>\bar{x} = P_C(\bar{x} - \alpha \nabla f (\bar{x}))</math>
# Se <math>f</math> é convexa e <math>\bar{x} = P_C(\bar{x} - \alpha \nabla f (\bar{x}))</math>, então <math>\bar{x}</math> é um minimizador global de <math>f</math> em <math>C</math>.
}}
{{Demonstração
|(1)

Como <math>\bar{x}</math> é um minimizador local de <math>f</math> em <math>C</math>, então
:<math>\langle \nabla f(x), x - \bar{x} \rangle \ge 0, \, \forall x \in C</math>

Observe que essa desigualdade equivale à
:<math>\langle \alpha \nabla f(x), x - \bar{x} \rangle \ge 0, \, \forall x \in C</math>
ou ainda
:<math>\langle \bar{x} - (\bar{x} - \alpha \nabla f(x)), x - \bar{x} \rangle \ge 0, \, \forall x \in C</math>

Tomando <math>\bar{y} = \bar{x} - \alpha \nabla f(x)</math> e <math>P = \bar{x}</math>, tem-se a equivalência com:
:<math>\langle P - \bar{y}, x - P \rangle \ge 0, \, \forall x \in C</math>
que equivale a dizer que <math>P = P_C(\bar{y})</math>, ou seja:
:<math>\bar{x} = P = P_C(\bar{y}) = P_C(\bar{x} - \alpha \nabla f(x))</math>

(2)

Reciprocamente, supor que <math>\bar{x} = P = P_C(\bar{y}) = P_C(\bar{x} - \alpha \nabla f(x))</math>, conforme a argumentação anterior, equivale a dizer que 
:<math>\langle \nabla f(x), x - \bar{x} \rangle \ge 0, \, \forall x \in C</math>

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

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

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

Este teorema pode ser demonstrado de forma análoga a que foi feita anteriormente.
{{Demonstração}}

Seja <math>\tilde{C}</math> definido como:
:<math>\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\}</math>.

Pela segunda propriedade do cone tangente, tem-se:
:<math>T(a, V \cap \tilde{C}) = T(a, C) = T(a, V \cap \tilde{C})</math>. Logo, 
:<math>T(a, C) = T(a, \tilde{C})</math>

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

{{Definição
|Toda condição que implica que <math>T(a, C) = L(a, C)</math> é chamada de '''condição de qualificação das restrições'''.
}}

{{Wikipédia|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'').

==== Exemplos de condições de qualificação das restrições ====
(1) Se <math>g_i</math> e <math>h_i</math> são funções afim-lineares, então para qualquer <math>x \in C</math>, tem-se <math>T(x, C) = L(x, C)</math>. Prova-se isso trivialmente
{{Prova}}

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

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

{{Teorema||(Karush–Kuhn–Tucker)
|Suponha que <math>f</math>, <math>g_i</math> e <math>h_j</math> são funções de classe <math>\mathcal{C}^1</math> em uma vizinhança do ponto <math>\bar{x}</math> e que <math>T(\bar{x}, C) = L(\bar{x}, C)</math>. Se <math>\bar{x}</math> é um minimizador local de <math>f</math> em <math>C</math>, então existem <math>u \in \mathbb{R}^p</math> e <math>v \in \mathbb{R}^q</math> tais que:
# <math>\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</math>
# <math>u_i \ge 0, \, \forall i = 1, \ldots, p</math>
# <math>u_i g_i(\bar{x}) = 0, \, \forall i = 1, \ldots, q</math>
}}

{{Wikipédia|Condições de Karush-Kuhn-Tucker}}

Note que aqui aparece a lagrangiana, pois a primeira condição é equivalente a:
:<math>\nabla_x l(x, u, v) = 0</math>

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

{{Teorema
|Suponha-se que <math>f</math>, <math>g_i</math> e <math>h_j</math> são funções de classe <math>\mathcal{C}^1</math> em uma vizinhança de <math>\bar{x}</math>, que <math>f</math> e <math>g_i</math> são convexas e que <math>h_j</math> são afim-lineares. são funções de classe <math>\mathcal{C}^1</math>. Se existem <math>u \in \mathbb{R}^p</math> e <math>v \in \mathbb{R}^q</math> tais que:
# <math>\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</math>
# <math>u_i \ge 0, \, \forall i = 1, \ldots, p</math>
# <math>u_i g_i(\bar{x}) = 0, \, \forall i = 1, \ldots, p</math>
# <math>g_i(\bar{x}) \le 0, \, \forall i = 1, \ldots, p</math>
# <math>h_j(\bar{x}) = 0, \, \forall j = 1, \ldots, q</math>
}}

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

{{Tarefa|Confrontar as informações presentes nestes últimos teoremas com algum livro. Parece estar precisando de pequenas correções.}}

Considere o seguinte problema:
:<math>\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.</math>

Sabe-se que <math>l:\mathbb{R}^n \times \mathbb{R}^p \times \mathbb{R}^q \mapsto \mathbb{R}</math> dada por
:<math>l(x, u, v) = f(x) + \sum_{i=1}^{p} u_i g_i (x) + \sum_{j=1}^{q} v_j h_j (x)</math>.

Agora, tem-se as KKT:

{{Teorema
|Supondo que <math>f, g_i</math> e <math>h_j</math> são de classe <math>\mathcal{C}^1</math> em uma vizinhança de <math>\bar{x} \in C</math> e que <math>T(\bar{x}, C) = L(\bar{x}, C)</math>, se <math>\bar{x}</math> é um minimizador local de <math>f</math> em <math>C</math>, então <math>\exists \bar{u} \in \mathbb{R}^p</math> tal que <math>\exists \bar{v} \in \mathbb{R}^q</math> de modo que:
# <math>\nabla_x l (\bar{x}, \bar{u}, \bar{v}) = 0</math>
# <math>\bar{u} \ge 0</math>
# <math>\nabla_u l (\bar{x}, \bar{u}, \bar{v}) \le 0</math>
# <math>\bar{u}^\top \nabla_u l (\bar{x}, \bar{u}, \bar{v}) = 0</math>
# <math>\nabla_v l (\bar{x}, \bar{u}, \bar{v}) = 0</math>
}}

== Uma inequação sobre ínfimos e supremos ==
{{Teorema
|Sejam <math>X \subset \mathbb{R}^n</math> e <math>Y \subset \mathbb{R}^m</math> dois subconjuntos arbitrários e considere uma aplicação 

<math>K: X \times Y \mapsto \mathbb{R}</math>. Então
:<math>- \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</math>
}}

{{Demonstração
|Sabe-se que
:<math>K(x, y) \le \sup_{y \in Y} K(x, y) \le + \infty</math>, 
quaisquer que sejam <math>x \in X, y \in Y</math>. Então, calculando o ínfimo em ambos os membros (com relação aos valores de <math>x</math>), e considerando que <math>K(x, y)</math> pode ser ilimitado inferiormente, tem-se para qualquer <math>y \in Y </math>:
:<math>- \infty \le \inf_{x \in X} K(x, y) \le \inf_{x \in X} \sup_{y \in Y} K(x, y) \le + \infty</math>
Assim, calculando o supremo (com relação aos valores de <math>y</math>), segue das desigualdades anteriores:
:<math>- \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</math>
}}

{{Exercício
|Verifique que:
:<math>- \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</math>
}}
{{Demonstração}}

Defina-se a função:
:<math>\alpha: \mathbb{R}^n \mapsto \mathbb{R} \cup \{+\infty\} </math>, dada por
:<math>\alpha(x) = \sup_{\begin{smallmatrix}u \ge 0 \\v \in \mathbb{R}^q \end{smallmatrix}} l(x, u, v)</math>

e também
:<math>\beta: [ 0, +\infty )^p \times \mathbb{R}^q \mapsto \mathbb{R} \cup \{-\infty\} </math>, dada por
:<math>\beta(u, v) = \inf_{x \in \mathbb{R}^n} l(x, u, v)</math>

Conforme o exercício anterior, tem-se então
:<math>- \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</math>

Observando a relação entre essas funções, é natural considerar dois problemas de otimização:
:<math>(Pr)\left\{\begin{matrix}
\min \alpha(x)\\
x \in \mathbb{R}^n
\end{matrix}\right.</math>
e
:<math>(D)\left\{\begin{matrix}
\max \beta(u, v)\\
u \ge 0\\
v \in \mathbb{R}^q
\end{matrix}\right.</math>

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


{{Exercício
|Verifique que:
<math>\alpha (x) = \left\{\begin{matrix}
f(x) & , \text{ se } x \in C\\
+\infty & , \text{ se } x \not\in C
\end{matrix}\right.</math>
}}
{{Resolução
|Se <math>x\in C</math> tem-se que <math>g_i(x) \le 0; i = 1, \ldots, p</math> e <math>h_j(x) = 0; j = 1, \ldots, q </math>.

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

Por outro lado, se <math>x\notin C</math> existe um índice <math>j</math> tal que <math>h_j(x)\neq 0</math> e/ou <math>g_i(x)> 0</math>. 
No primeiro caso, seja <math>u=0 </math> e
:<math>v_j=\begin{cases} 
 th_i(x),  & i=j \\
 0, & i\ne j 
\end{cases}
</math>, onde <math>t > 0 </math>.

Com esta escolha, a lagrangiana será
:<math>l(x, u, v)= f(x)+t(h_j(x))^2</math>.

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

Para o outro caso a prova é análoga.
}}
{{Exercício
|Verifique que <math>(D)</math> consiste de maximizar uma função côncava em um poliedro. Lembre-se: 
:# Uma função <math>f</math> é côncava quando <math>-f</math> for convexa.
:# Um poliedro é qualquer intersecção finita de semiespaços fechados.
}}
{{Resolução
|Primeiro será mostrado que :<math>\beta: [ 0, +\infty )^p \times \mathbb{R}^q \mapsto \mathbb{R} \cup \{-\infty\} </math>, dada por <math>\beta(u, v) = \inf_{x \in \mathbb{R}^n} l(x, u, v)</math> é uma função côncava. Para isso, basta mostrar que para cada <math>t\in [0, 1]</math> vale
:<math>\beta(ta+(1-t)b, tc+(1-t)d)\ge t\beta(a, c)+(1-t)\beta(b, d)</math>.

Chamando <math>\bar{u}=ta+(1-t)b</math> e <math>\bar{v}=tc+(1-t)d</math> tem-se:
:<math>\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}</math>

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


=== Exemplo numérico: problema primal e seu dual ===
Considere o problema 
:<math>(P) \left\{\begin{matrix}
\min x^2\\
1 \le x \le 2
\end{matrix}\right.</math>
{{Resolução
|[[Imagem:Função quadrática restrita a um intervalo.svg|thumb|right]]
O problema é ilustrado na imagem a direita.

Primeiramente, é preciso identificar quais são as funções <math>f, g_i</math> e <math>h_j</math> envolvidas:
* A função objetivo é aquela que se pretende minimizar, ou seja, <math>f: \mathbb{R} \mapsto \mathbb{R}; f(x) = x^2</math>;
* Como aparecem apenas restrições de desigualdade, não há qualquer função <math>h_j</math>;
* Reescrevendo as desigualdades como <math>1-x \le 0</math> e <math>x-2 \le 0</math>, conclúi-se que as funções <math>g_i</math> são: 

:<math>g_1: \mathbb{R} \mapsto \mathbb{R}; g_1(x) = 1-x</math> e <math>g_2: \mathbb{R} \mapsto \mathbb{R}; g_2(x) = x-2</math>.

Neste caso, a lagrangiana é:
:<math>l: \mathbb{R} \times \mathbb{R}^2 \mapsto \mathbb{R}</math>, dado por
:<math>l(x, u_1, u_2) = x^2 + u_1 (1-x) + u_2 (x-2) </math>

Em seguida, é preciso calcular <math>\alpha</math> e <math>\beta</math>:
:<math>\alpha: \mathbb{R}^n \mapsto \mathbb{R} \cup \{+\infty\} </math>, é dada por
:<math>\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) ]</math>

E, conforme um dos exercícios anteriores (ou através de uma breve análise dos supremos envolvidos na expressão anterior), tem-se:
:<math>\alpha(x) = \left\{\begin{matrix}
x^2 & , \text{ se } x \in [1, 2]\\
+\infty & , \text{ se } x \not\in [1, 2]
\end{matrix}\right.</math>

Analogamente, tem-se:
:<math>\beta: \mathbb{R}^2 \mapsto \mathbb{R} \cup \{-\infty\} </math>, dada por
:<math>\beta(u_1, u_2) = \inf_{x \in \mathbb{R}^n} [x^2 + u_1 (1-x) + u_2 (x-2) ]</math>

Observe que em relação a <math>x</math>, tem-se uma função fortemente convexa, que portanto possui um único minimizador. Além disso, <math>l</math> é diferenciável, donde o seu único minimizador <math>x_0</math> é dado pela equação:
:<math>\nabla_x l (x_0, u_1, u_2) = 0</math>
ou seja, 
:<math>2 x_0 + u_1 - u_2 = 0</math>
donde
:<math>x_0 = \frac{u_2 - u_1}{2}</math>

Portanto, 
:<math>\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)</math>

Assim, os problemas em dualidade são:
:<math>(Pr)\left\{\begin{matrix}
\min \alpha(x)\\
x \in \mathbb{R}^n
\end{matrix}\right.</math>
e
:<math>(D)\left\{\begin{matrix}
\max \beta(u_1, u_2)\\
u_1, u_2 \ge 0
\end{matrix}\right.</math>

Pelo primeiro item do exercício, tem-se que a minimização do problema <math>(Pr)</math> é equivalente à minimização do problema original.

Por outro lado, através da lagrangiana, obtem-se além do problema primal <math>(Pr)</math>, um problema dual <math>(D)</math>, cuja estrutura é muito melhor que a do original (pois pelo outro exercício, consiste da maximização de uma função côncava <math>\beta</math> 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 <math>(P)</math> e a lagrangiana <math>l</math> associada a esse problema, se diz que <math>(\bar{x}, \bar{u}, \bar{v})</math> é um '''ponto de sela''' de <math>l</math> se <math>\bar{u} \ge 0</math> e:
:<math>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 </math>.
}}

{{Teorema
|O ponto <math>(\bar{x}, \bar{u}, \bar{v})</math> é um ponto de sela de <math>l</math> se, e somente se:
# <math>\bar{x}</math> é solução de <math>(Pr)</math>;
# <math>(\bar{u}, \bar{v})</math> é solução de <math>(D)</math>;
# <math>\bar{\alpha} = \bar{\beta}</math>.
}}
{{Demonstração
|Se <math>(\bar{x}, \bar{u}, \bar{v})</math> é um ponto de sela de <math>l</math>, então <math>\bar{u} \ge 0</math> e se tem:
:<math>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 </math>.

Em particular, como
:<math>\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})</math>.

segue da segunda desigualdade que
:<math>\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</math>
e calculando o ínfimo sobre todos os <math>x \in \mathbb{R}</math> tem-se:
:<math>\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}</math>

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

Logo, todos os membros das desigualdades acima coincidem, ou seja, 
:<math>\bar{\alpha}(\bar{x}) =l(\bar{x}, \bar{u}, \bar{v}) = \beta(\bar{u}, \bar{v}) = \bar{\beta}</math>

Mas da definição de <math>\bar{\beta}</math> tem-se:
:<math>\bar{\beta} = \sup_{\begin{smallmatrix}u \ge 0\\v \in \mathbb{R}^q\end{smallmatrix}} \beta(u, v)</math>.
Portanto, <math>(\bar{u}, \bar{v})</math> é solução do problema <math>(D)</math> enquanto <math>\bar{\alpha} = \inf_{x \in \mathbb{R}^n} \alpha (x)</math> significa que <math>\bar{x}</math> é solução de <math>(Pr)</math>



Reciprocamente, supondo que <math>\bar{x}</math> é solução do problema <math>(Pr)</math>, tem-se:
:<math>\alpha(\bar{x}) = \inf_{x \in \mathbb{R}^n} \alpha(x)</math>
e admitindo que <math>(\bar{u}, \bar{v})</math> é solução do problema <math>(D)</math>, segue:
:<math>\beta(\bar{u}, \bar{v}) = \sup_{\begin{smallmatrix}u \ge 0 \\v \in \mathbb{R}^q \end{smallmatrix}} \beta(u, v)</math>

Além disso, usando como hipótese que <math>\bar{\alpha} = \bar{\beta}</math>, segue da definição que:
:<math>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})</math>, quaisquer que sejam <math>x \in \mathbb{R}^n, u \ge 0, v \in \mathbb{R}^q</math>.

Em particular, tomando <math>u = \bar{u}</math>, <math>v = \bar{v}</math> e <math>x = \bar{x}</math>, resulta:
:<math>l(\bar{x}, \bar{u}, \bar{v}) \le \bar{\alpha} = \bar{\beta} \le l(\bar{x}, \bar{u}, \bar{v})</math>, ou seja, 

<math>l(\bar{x}, \bar{u}, \bar{v}) = \bar{\alpha} = \bar{\beta}</math>

Logo, pela definição de <math>\alpha, \beta</math> tem-se:
:<math>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})</math>, quaisquer que sejam <math>x \in \mathbb{R}^n, u \ge 0, v \in \mathbb{R}^q</math>.

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

}}

{{Wikipédia|Ponto de sela}}

=== Exemplos ===
Considere novamente o problema de otimização dado por:
:<math>\left\{\begin{matrix}
\min x^2\\
1 \le x \le 2
\end{matrix}\right.</math>

Verificar se a lagrangiana associada à <math>(P)</math> tem ponto de sela.

{{Resolução
|[[Imagem:Função quadrática restrita a um intervalo.svg|thumb|right]]
O problema é ilustrado na imagem a direita, e conforme foi deduzido anteriormente, tem-se:
* <math>f: \mathbb{R} \mapsto \mathbb{R}; f(x) = x^2 </math>
* <math>g_1: \mathbb{R} \mapsto \mathbb{R}; g_1(x) = 1-x </math>
* <math>g_2: \mathbb{R} \mapsto \mathbb{R}; g_2(x) = x-2 </math>
* <math>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) </math>

Além disso, como foi mostrado anteriormente, vale
:<math>\alpha (x) = \left\{\begin{matrix}
x^2 & , \text{ se } x \in [1, 2]\\
+\infty & , \text{ se } x \not\in [1, 2]
\end{matrix}\right.</math>

e também
:<math>\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)</math>

ou seja, 
:<math>\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}
</math>

Agora, consideram-se os seguintes problemas em dualidade:
:<math>(Pr)\left\{\begin{matrix}
\min \alpha(x)\\
x \in \mathbb{R}^n
\end{matrix}\right.</math>
e
:<math>(D)\left\{\begin{matrix}
\max \beta(u_1, u_2)\\
u_1, u_2 \ge 0
\end{matrix}\right.</math>

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

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

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

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

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


}}

=== Análise do problema ===

Considerando <math>(P)</math>, <math>(Pr)</math>, <math>(D)</math> e <math>l</math>, se <math>(\bar{u}, \bar{v})</math> é uma solução do problema dual, considere o seguinte problema:
:<math>(P_{ \bar{u}, \bar{v} })\left\{\begin{matrix}
\min l(x, \bar{u}, \bar{v})\\
x \in \mathbb{R}
\end{matrix}\right.</math>
que no caso do exemplo reduz-se a
:<math>(P_{ \bar{u}, \bar{v} })\left\{\begin{matrix}
\min x^2 + 2(1-x)\\
x \in \mathbb{R}
\end{matrix}\right.</math>

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

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 <math>f, g_i: \mathbb{R}^n \mapsto \mathbb{R}</math> são de classe <math>\mathcal{C}^1</math> e convexas, e que as funções <math>h_j</math> são afim lineares e <math>T(x, C) = L(x, C), \forall x \in C</math>. Nestas condições:
# Se o problema <math>(P)</math> tem solução, então <math>\bar{\alpha} = \bar{\beta} </math> e os problemas <math>(Pr)</math> e <math>(D)</math> têm solução.
# Se <math>(P)</math> tem solução, e <math>(\bar{u}, \bar{v})</math> é solução de <math>(D)</math>, então as soluções de <math>(Pr)</math> são as soluções de <math>(P_{\bar{u}, \bar{v}})</math>, onde
:<math>(P_{ \bar{u}, \bar{v} })\left\{\begin{matrix}
\min l(x, \bar{u}, \bar{v})\\
x \in \mathbb{R}
\end{matrix}\right.</math>
que também são as soluções de <math>(P)</math>.
}}

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 <math>(P)</math>, pode-se optar por resolver <math>(D)</math> (um problema concavo em um poliedro), e depois resolver <math>(P_{ \bar{u}, \bar{v} })</math> (que é um problema convexo sem restrições). Em outras palavras, é possível trocar um problema difícil por dois problemas mais fáceis, <math>(D)</math> e <math>(P_{ \bar{u}, \bar{v} })</math>.

Agora a demonstração do teorema:
{{Demonstração
|(1) Como <math>(P)</math> tem solução, seja <math>\bar{x}</math> uma solução de <math>(P)</math>. Pelo teorema de KKT (que se aplica pois as funções são de classe <math>\mathcal{C}^1</math> e se tem a qualificação das restrições), segue a existência de <math>\bar{u} \in \mathbb{R}^p</math> e <math>\bar{v} \in \mathbb{R}^q</math>, tais que:
# <math>\nabla_x l (\bar{x}, \bar{u}, \bar{v}) = 0</math>
# <math>\bar{u} \ge 0</math>
# <math>\nabla_u l (\bar{x}, \bar{u}, \bar{v}) \le 0</math>
# <math>\bar{u}^\top \nabla_u l (\bar{x}, \bar{u}, \bar{v}) = 0</math>
# <math>\nabla_v l (\bar{x}, \bar{u}, \bar{v}) = 0</math>

Como <math>f, g_i</math> são funções convexas e <math>h_j</math> afim lineares, então a função lagrangiana <math>l(x, \bar{u}, \bar{v})</math> é convexa em <math>x</math> (pela forma de <math>l</math>). Isto significa que:
:<math>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</math>.
Usando (1), conclúi-se uma das duas desigualdades que definem um ponto de sela em <math>(\bar{x}, \bar{u}, \bar{v})</math>:
:<math>l(x, \bar{u}, \bar{v}) \ge l(\bar{x}, \bar{u}, \bar{v})</math>.

Considerando que <math>\bar{x}</math> é solução de <math>(P)</math>, tal ponto satisfaz as restrições <math>g_i(x) \le 0; i = 1, \ldots, p</math> e <math>h_j(x) = 0; j = 1, \ldots, q</math>. Então, usando <math>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})</math>, segue que:
:<math>l(\bar{x}, u, v) \le f(\bar{x})</math>
pois <math>h_j (\bar{x}) = 0</math> e <math>u_i \ge 0</math>.

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

Logo:
:<math>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})</math>

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

Logo, <math>\bar{\alpha} = \bar{\beta}</math>, <math>\bar{x}</math> é solução do problema primal <math>(Pr)</math> e <math>(\bar{u}, \bar{v})</math> é solução do problema dual <math>(D)</math>

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

Seja <math>\bar{x}</math> solução de <math>(Pr)</math>. Então, <math>(\bar{x}, \bar{u}, \bar{v})</math> é ponto de sela de <math>l</math>, logo valem as desigualdades:
:<math>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 </math>.

Uma vez que <math>( \bar{u}, \bar{v} )</math> está fixo e a segunda desigualdade vale para qualquer <math>x \in \mathbb{R}^n</math>, conclui-se que <math>\bar{x}</math> é solução do problema
:<math>(P_{ \bar{u}, \bar{v} })\left\{\begin{matrix}
\min l(x, \bar{u}, \bar{v})\\
x \in \mathbb{R}
\end{matrix}\right.</math>

As soluções deste problema são soluções de <math>(Pr)</math> e, consequentemente, do problema original.
}}
{{Exercício
|Verificar se existe salto de dualidade nos problemas em dualidade para o seguinte problema de minimização:
:<math>(P_1)\left\{\begin{matrix}
\min x-y^2\\
x^2 + y^2 \le 1\\
x + y \le 1
\end{matrix}\right.</math>
}}

{{Exercício
|Juntamente com o problema <math>(P_1)</math> do exercício anterior, considere o seguinte problema:
:<math>(P_2)\left\{\begin{matrix}
\min x-y^2\\
x \ge 0\\
y \ge 0\\
x + y \le 1
\end{matrix}\right.</math>

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 <math>f(x, y) = x-y^2</math> 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 <math>x \in \mathbb{R}^5</math> 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 <math>(P)</math> a lagrangiana <math>l</math> e os problemas em dualidade <math>(Pr)</math> e <math>(D)</math> e <math>(\bar{u}, \bar{v})</math> soluções de <math>(D)</math>.

Se <math>\bar{x}</math> é solução do problema 
:<math>(P_{ \bar{u}, \bar{v} })\left\{\begin{matrix}
\min l(x, \bar{u}, \bar{v})\\
x \in \mathbb{R}
\end{matrix}\right. , </math>
<math>\bar{x} \in C</math> (o conjunto dos pontos que satisfazem as restrições) e <math>g_i(\bar{x})\bar{u}_i = 0, \forall i</math>, então <math>\bar{x}</math> é também uma solução do problema <math>(P)</math>.
}}
Tal proposição fornece um roteiro para quem precisa resolver o problema <math>(P)</math> relativamente difícil:
# Primeiramente, resolve-se <math>(D)</math>;
# Depois, constrói-se o problema <math>(P_{ \bar{u}, \bar{v} })</math> e encontra-se uma solução <math>\bar{x}</math> para o mesmo;
# Finalmente, se <math>\bar{x}</math> satisfaz as últimas condições da proposição, ele é também uma solução de <math>(P)</math>.
{{Demonstração
|Se <math>(\bar{u}, \bar{v})</math> é uma solução de <math>(D)</math>, <math>\bar{\beta} = \beta (\bar{u}, \bar{v})</math>. Então, pela definição de <math>\beta (\bar{u}, \bar{v})</math>, tem-se:
:<math>\bar{\beta} = \sup_{\begin{smallmatrix}u \ge 0 \\v \in \mathbb{R}^q\end{smallmatrix}} \beta(u, v)</math>
Como <math>\bar{x}</math> é solução de <math>(P_{ \bar{u}, \bar{v} })</math>, então:
:<math>l(\bar{x}, \bar{u}, \bar{v}) \le l(x, \bar{u}, \bar{v}), \forall x \in \mathbb{R}^n</math>
ou seja, 
:<math>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}</math>

Portanto, 
:<math>l(\bar{x}, \bar{u}, \bar{v}) = \bar{\beta} = \beta (\bar{u}, \bar{v})</math>

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

Por hipótese, <math>g_i(\bar{x})\bar{u}_i = 0</math>, então
:<math>\sum_{i=1}^{p} \bar{u}_i g_i (\bar{x}) = 0 = \sum_{j=1}^{q} \bar{v}_j h_j (\bar{x}) </math>

Logo, 
:<math>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})</math>.

Então para <math>u \ge 0</math> tem-se que <math>u_i g_i(\bar{x}) \le 0, \forall i</math> e <math>v_j h_j(\bar{x}) = 0, \forall j</math>. Consequentemente, 
:<math>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})</math>
quaisquer que sejam <math>u \ge 0, v \in \mathbb{R}^q</math>, ou seja, 
:<math>l(\bar{x}, u, v) = f(\bar{x}) = l(\bar{x}, \bar{u}, \bar{v}) \le l(x, \bar{u}, \bar{v}) </math>, 
quaisquer que sejam <math>u \ge 0, v \in \mathbb{R}^q</math>.

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

}}

== 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
:<math>\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.</math>
onde <math>f, g_i, h_j:\mathbb{R}^n \mapsto \mathbb{R}</math> são funções de classe <math>\mathcal{C}^1 (\mathbb{R}^n)</math>, e seja a lagrangiana <math>l:\mathbb{R}^n \times \mathbb{R}^p \times \mathbb{R}^q \mapsto \mathbb{R}</math> definido por
:<math>l(x, u, v) = f(x) + \sum_{i=1}^{p} u_i g_i (x) + \sum_{j=1}^{q} v_j h_j (x)</math>.

Convenciona-se que:
* <math>x</math> é a '''variável primal''';
* <math>(u, v)</math> é a '''variável dual''';

Nesse sentido, "o <math>\mathbb{R}^p \times \mathbb{R}^q</math> é o dual de <math>\mathbb{R}^n</math>" (não confundir com o significado que essa expressão teria na análise funcional. Ver [[#Uma nota sobre a terminologia|nota sobre a terminologia]]), ou seja:
* <math>\mathbb{R}^n</math> é onde "mora" a variável primal <math>x</math>;
* <math>\mathbb{R}^p \times \mathbb{R}^q</math> é onde "mora" a variável dual <math>(u, v)</math>;

Definem-se então as funções <math>\alpha</math> e <math>\beta</math> da seguinte maneira:
:<math>\alpha: \mathbb{R}^n \mapsto \mathbb{R} \cup \{+\infty\} </math>, dada por
:<math>\alpha(x) = \sup_{\begin{smallmatrix}u \ge 0 \\v \in \mathbb{R}^q \end{smallmatrix}} l(x, u, v)</math>

e 
:<math>\beta: \mathbb{R}^p \times \mathbb{R}^q \mapsto \mathbb{R} \cup \{-\infty\} </math>, dada por
:<math>\beta(u, v) = \inf_{x \in \mathbb{R}^n} l(x, u, v)</math>

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

:<math>(Pr)\left\{\begin{matrix}
\min \alpha(x)\\
x \in \mathbb{R}^n
\end{matrix}\right.</math>
e
:<math>(D)\left\{\begin{matrix}
\max \beta(u, v)\\
u \ge 0\\
v \in \mathbb{R}^q
\end{matrix}\right.</math>

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

Logo, o dual de <math>(P)</math> é <math>(D)</math>.

=== Conclusões ===
Dado qualquer problema <math>(P)</math>, seu dual <math>(D)</math> é 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 {{busca|Análise Funcional}}, quando se tem um espaço topológico <math>X</math>, costuma-se chamar de '''dual topológico''' ao conjunto <math>X^* = \{ t : X \mapsto \mathbb{R}; t \text{ é linear e continua} \}</math>.

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 [[w:Werner Fenchel|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.

{{Wikipédia|Análise funcional}}

{{AutoCat}}