Otimização/Métodos duais

Lagrangiana

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

$(P)\{\begin{array}{c}\min f(x)\\ g_i(x)\le 0;i=1,\dots ,p\\ h_j(x)=0;j=1,\dots ,q\end{array}$

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

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

$G(x)=\left[\begin{array}{c}{g}_1(x)\\ ⋮\\ g_p(x)\end{array}\right]$

e

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

$H(x)=\left[\begin{array}{c}{h}_1(x)\\ ⋮\\ h_q(x)\end{array}\right]$

Deste modo, a lagrangiana fica expressa por

$l(x,u,v)=f(x)+u^{\mathrm{\top }}G(x)+v^{\mathrm{\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 {ℝ}^n;g_i(x)\le 0\text{ e }{h}_j(x)=0\}$ é convexo e fechado.
• Caso geral: quando $C$ é arbitrário.

Caso particular

Observação

A condição $⟨u,v⟩\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, $\mathrm{\nabla }f$ sempre forma ângulo menor ou igual a 90 graus com os vetores do tipo $x-\overline{x}$, onde $\overline{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=\mathrm{\nabla }f$ e $v=x-\overline{x}$, $⟨u,v⟩$ é a derivada direcional de $f$ na direção $x-\overline{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:

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 $\overline{y}$ sobre o conjunto $C$, denotada por $\overline{P}=P_C(\overline{y})$, satisfaz $⟨\overline{P}-\overline{y},x-\overline{P}⟩\ge 0,\mathrm{\forall }x\in C$. Na verdade, vale:

$\overline{P}=P_C(\overline{y})\iff ⟨\overline{P}-\overline{y},x-\overline{P}⟩\ge 0,\mathrm{\forall }x\in C$

O vetor $\overline{P}-\overline{y}$ forma ângulo menor que 90 graus com o vetor $x-\overline{P}$, pois $\overline{P}$ é a projeção de $\overline{y}$ sobre o conjunto $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 {ℝ}^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.

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

Seja $\tilde{C}$ definido como:

$\tilde{C}={\tilde{C}}_a=\{x\in {ℝ}^n;g_i(x)\le 0,\mathrm{\forall }i\in I(a);h_j(x)=0\}$.

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.

Predefinição:Wikipédia 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 Predefinição:Prova

(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)$. Predefinição:Prova

(3) Condições de Mangasarian-Fromowitz: Se $\{\mathrm{\nabla }{h}_j(x)\}$ é linearmente independente e existe $\tilde{d}$ tal que $⟨\mathrm{\nabla }{h}_j(x),\tilde{d}⟩=0$ para tpdp $j$ e $⟨\mathrm{\nabla }{g}_i(x),\tilde{d}⟩<0$. Predefinição:Prova

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

${\mathrm{\nabla }}_{x}l(x,u,v)=0$

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

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

Considere o seguinte problema:

$\{\begin{array}{c}\min f(x)\\ g_i(x)\le 0;i=1,\dots ,p\\ h_j(x)=0;j=1,\dots ,q\end{array}$

Sabe-se que $l:{ℝ}^n\times {ℝ}^p\times {ℝ}^q\mapsto ℝ$ 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:

Uma inequação sobre ínfimos e supremos

Defina-se a função:

$\alpha :{ℝ}^n\mapsto ℝ\cup \{+\mathrm{\infty }\}$, dada por

$\alpha (x)=\underset{\begin{array}{c}u\ge 0\\ v\in {ℝ}^q\end{array}}{\sup }l(x,u,v)$

e também

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

$\beta (u,v)=\underset{x\in {ℝ}^n}{\inf }l(x,u,v)$

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

$-\mathrm{\infty }\le \underset{\begin{array}{c}u\ge 0\\ v\in {ℝ}^q\end{array}}{\sup }\beta (u,v)\le \underset{x\in {ℝ}^n}{\inf }\alpha (x)\le +\mathrm{\infty }$

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

$(Pr)\{\begin{array}{c}\min \alpha (x)\\ x\in {ℝ}^n\end{array}$

e

$(D)\{\begin{array}{c}\max \beta (u,v)\\ u\ge 0\\ v\in {ℝ}^q\end{array}$

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 $\overline{\alpha }=\underset{x\in {ℝ}^n}{\inf }\alpha (x)$ e $\overline{\beta }=\underset{\begin{array}{c}u\ge 0\\ v\in {ℝ}^q\end{array}}{\sup }\beta (u,v)$, segue-se do exercício anterior que $\overline{\beta }\le \overline{\alpha }$;
4. A diferença $\overline{\alpha }-\overline{\beta }$ é chamada de brecha de dualidade, ou salto de dualidade (do inglês, skip duality);

Predefinição:Exercício Predefinição:Resolução Predefinição:Exercício Predefinição:Resolução

Exemplo numérico: problema primal e seu dual

Considere o problema

$(P)\{\begin{array}{c}\min x^2\\ 1\le x\le 2\end{array}$

Ponto de sela

Este é um conceito muito importante relacionado à lagrangiana.

Exemplos

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

$\{\begin{array}{c}\min x^2\\ 1\le x\le 2\end{array}$

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

Análise do problema

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

$(P_{\overline{u},\overline{v}})\{\begin{array}{c}\min l(x,\overline{u},\overline{v})\\ x\in ℝ\end{array}$

que no caso do exemplo reduz-se a

$(P_{\overline{u},\overline{v}})\{\begin{array}{c}\min x^2+2(1-x)\\ x\in ℝ\end{array}$

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.

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_{\overline{u},\overline{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_{\overline{u},\overline{v}})$.

Agora a demonstração do teorema: Predefinição:Demonstração Predefinição:Exercício

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

Predefinição:Proposição 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_{\overline{u},\overline{v}})$ e encontra-se uma solução $\overline{x}$ para o mesmo;
3. Finalmente, se $\overline{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

$\{\begin{array}{c}\min f(x)\\ g_i(x)\le 0;i=1,\dots ,p\\ h_j(x)=0;j=1,\dots ,q\end{array}$

onde $f,g_i,h_j:{ℝ}^n\mapsto ℝ$ são funções de classe ${𝒞}^1({ℝ}^n)$, e seja a lagrangiana $l:{ℝ}^n\times {ℝ}^p\times {ℝ}^q\mapsto ℝ$ 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 ${ℝ}^p\times {ℝ}^q$ é o dual de ${ℝ}^n$" (não confundir com o significado que essa expressão teria na análise funcional. Ver nota sobre a terminologia), ou seja:

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

Definem-se então as funções $\alpha$ e $\beta$ da seguinte maneira:

$\alpha :{ℝ}^n\mapsto ℝ\cup \{+\mathrm{\infty }\}$, dada por

$\alpha (x)=\underset{\begin{array}{c}u\ge 0\\ v\in {ℝ}^q\end{array}}{\sup }l(x,u,v)$

e

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

$\beta (u,v)=\underset{x\in {ℝ}^n}{\inf }l(x,u,v)$

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

$(Pr)\{\begin{array}{c}\min \alpha (x)\\ x\in {ℝ}^n\end{array}$

e

$(D)\{\begin{array}{c}\max \beta (u,v)\\ u\ge 0\\ v\in {ℝ}^q\end{array}$

É 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 Predefinição:Busca, quando se tem um espaço topológico $X$, costuma-se chamar de dual topológico ao conjunto $X^{*}=\{t:X\mapsto ℝ;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.