# 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)\leq 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)\leq 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 \geq 0,\,\forall x\in C$

#### Observação

A condição $\langle u,v\rangle \geq 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:
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 \geq 0,\,\forall x\in C$
${\bar {x}}$
$f$
$C$
${\bar {x}}$
$(P)$
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 \geq 0,\,\forall x\in C$. Na verdade, vale:
    ${\bar {P}}=P_{C}({\bar {y}})\Leftrightarrow \langle {\bar {P}}-{\bar {y}},x-{\bar {P}}\rangle \geq 0,\,\forall x\in C$

#### Proposição

Seja $\alpha >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$.

### 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)\leq 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 \geq 0,\,\forall d\in T({\bar {x}},C)$.
* Se $C$ é convexo, $f$ é convexa e $\langle \nabla f({\bar {x}}),d\rangle \geq 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.
Seja ${\tilde {C}}$ definido como:
    ${\tilde {C}}={\tilde {C}}_{a}=\left\{x\in \mathbb {R} ^{n};g_{i}(x)\leq 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
(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)$.
(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$.

##### 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}\geq 0,\,\forall i=1,\ldots ,p$
* $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:
* $\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}\geq 0,\,\forall i=1,\ldots ,p$
* $u_{i}g_{i}({\bar {x}})=0,\,\forall i=1,\ldots ,p$
* $g_{i}({\bar {x}})\leq 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.
Considere o seguinte problema:
    $\left\{{\begin{matrix}\min f(x)\\g_{i}(x)\leq 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}}\geq 0$
* $\nabla _{u}l({\bar {x}},{\bar {u}},{\bar {v}})\leq 0$
* ${\bar {u}}^{\top }\nabla _{u}l({\bar {x}},{\bar {u}},{\bar {v}})=0$
* $\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 \leq \sup _{y\in Y}\inf _{x\in X}K(x,y)\leq \inf _{x\in X}\sup _{y\in Y}K(x,y)\leq +\infty$

### Exercício

Verifique que:
    $-\infty \leq \sup _{\begin{smallmatrix}u\geq 0\\v\in \mathbb {R} ^{q}\end{smallmatrix}}\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)\leq \inf _{x\in \mathbb {R} ^{n}}\sup _{\begin{smallmatrix}u\geq 0\\v\in \mathbb {R} ^{q}\end{smallmatrix}}l(x,u,v)\leq +\infty$
Defina-se a função:
    $\alpha :\mathbb {R} ^{n}\mapsto \mathbb {R} \cup \{+\infty \}$, dada por
    $\alpha (x)=\sup _{\begin{smallmatrix}u\geq 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 \leq \sup _{\begin{smallmatrix}u\geq 0\\v\in \mathbb {R} ^{q}\end{smallmatrix}}\beta (u,v)\leq \inf _{x\in \mathbb {R} ^{n}}\alpha (x)\leq +\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\geq 0\\v\in \mathbb {R} ^{q}\end{matrix}}\right.$

### Comentários

* As funções $\alpha$ e $\beta$ são conhecidas na literatura como funções em dualidade (ou mais frequentemente, funções duais);
* O problema $(Pr)$ é 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\geq 0\\v\in \mathbb {R} ^{q}\end{smallmatrix}}\beta (u,v)$, segue-se do exercício anterior que ${\bar {\beta }}\leq {\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.$

### 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.

### Exemplo numérico: problema primal e seu dual

Considere o problema
    $(P)\left\{{\begin{matrix}\min x^{2}\\1\leq x\leq 2\end{matrix}}\right.$

## Ponto de sela

Este é um conceito muito importante relacionado à lagrangiana.

### Definição

Dado o problema $(P)$ e a lagrangiana $l$ associada a esse problema, se diz que $({\bar {x}},{\bar {u}},{\bar {v}})$ é um ponto de sela de $l$ se ${\bar {u}}\geq 0$ e:
    $l({\bar {x}},u,v)\leq l({\bar {x}},{\bar {u}},{\bar {v}})\leq l(x,{\bar {u}},{\bar {v}}),\forall x\in \mathbb {R} ^{n},\forall u\geq 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 $(Pr)$;
* $({\bar {u}},{\bar {v}})$ é solução de $(D)$;
* ${\bar {\alpha }}={\bar {\beta }}$.

### Exemplos

Considere novamente o problema de otimização dado por:
    $\left\{{\begin{matrix}\min x^{2}\\1\leq x\leq 2\end{matrix}}\right.$
Verificar se a lagrangiana associada à $(P)$ tem ponto de sela.

### 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:
* Se o problema $(P)$ tem solução, então ${\bar {\alpha }}={\bar {\beta }}$ e os problemas $(Pr)$ 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 $(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.$
$(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:

#### 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}\leq 1\\x+y\leq 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\geq 0\\y\geq 0\\x+y\leq 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?
$f(x,y)=x-y^{2}$

#### 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$
$g_{i}({\bar {x}}){\bar {u}}_{i}=0,\forall i$
${\bar {x}}$
$(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)$.

## 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)\leq 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\geq 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\geq 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.