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

- Definição
A função lagrangiana associada ao problema
é
definida por
.
Em alguns livros é usada a seguinte notação:
definida por

e
definida por

Deste modo, a lagrangiana fica expressa por

que é uma representação bem mais compacta.
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
. Nas próximas seções será apresentado um breve resumo das condições de otimalidade, dividindo-as em dois casos:
- Caso particular: quando
é convexo e fechado.
- Caso geral: quando
é arbitrário.
Demonstração
|
Seja uma solução de , e fixe um ponto arbitrário . Denote por a restrição da função sobre o segmento de reta que passa por e por , ou seja,
, com .
Note que .
Como é um minimizador de em , tem-se:
, para todo 
Logo,
, ou seja, 
Mas pela regra da cadeia,
, então .
Como era arbitrário, o resultado está demonstrado.
|
- Observação
A condição
significa que os vetores
e
formam um ângulo reto ou agudo (menor ou igual a 90 graus), conforme indicado na figura a seguir:
Em um ponto de mínimo,

sempre forma ângulo menor ou igual a 90 graus com os vetores do tipo

, onde

é um ponto de mínimo da função no conjunto viável

e

é um ponto qualquer deste conjunto.
No caso específico, com
e
,
é a derivada direcional de
na direção
. Quando tal número é não negativo, intuitivamente a função cresce naquela direção.
Quando
é um conjunto convexo e fechado, a existência de uma solução para o problema
é garantida pela seguinte proposição:
- Proposição
Se
,
é convexa e

então

é um minimizador global de

no conjunto

(isto é,

é solução de

).
Demonstração
|
Pela convexidade de , tem-se que:

Logo,

Portanto, , ou seja, é um minimizador de em .
|
Até aqui, não é exigido que qualquer das funções
ou
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
sobre o conjunto
, denotada por
, satisfaz
. Na verdade, vale:

O vetor

forma ângulo menor que 90 graus com o vetor

, pois

é a projeção de

sobre o conjunto

.
Demonstração
|
(1)
Como é um minimizador local de em , então

Observe que essa desigualdade equivale à

ou ainda

Tomando e , tem-se a equivalência com:

que equivale a dizer que , ou seja:

(2)
Reciprocamente, supor que , conforme a argumentação anterior, equivale a dizer que

Usando a hipótese de que é convexa, segue da proposição anterior que é um minimizador global de em .
|
Para tratar este caso, é preciso utilizar o conceito de cone tangente. O conjunto contínua o mesmo, ou seja,
, embora não seja mais suposto que ele é convexo. Mesmo assim,
ainda será fechado, pois as funções
e
que o definem são contínuas.
- Teorema
- Se
é um minimizador local de
em
, então
.
- Se
é convexo,
é convexa e
, então
é minimizador global de
em
.
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
definido como:
.
Pela segunda propriedade do cone tangente, tem-se:
. Logo,

Em outras palavras, se é dado um conjunto
e depois se restringe tal conjunto para
, através do acréscimo de restrições inativas em um ponto
, os cones tangentes aos dois conjuntos (no ponto
) coincidem.
- Definição
Toda condição que implica que
é 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[editar | editar código-fonte]
(1) Se
e
são funções afim-lineares, então para qualquer
, tem-se
. 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
são convexas e as
são afim lineares e, além disso, existe
tal que
para todo
,
, então para qualquer
, tem-se
.
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
é linearmente independente e existe
tal que
para tpdp
e
.
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
,
e
são funções de classe
em uma vizinhança do ponto
e que
. Se
é um minimizador local de
em
, então existem
e
tais que:



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

O essencial para a existência de
é que
.
- Teorema
Suponha-se que
,
e
são funções de classe
em uma vizinhança de
, que
e
são convexas e que
são afim-lineares. são funções de classe
. Se existem
e
tais que:





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:

Sabe-se que
dada por
.
Agora, tem-se as KKT:
- Teorema
Supondo que
e
são de classe
em uma vizinhança de
e que
, se
é um minimizador local de
em
, então
tal que
de modo que:





Demonstração
|
Sabe-se que
,
quaisquer que sejam . Então, calculando o ínfimo em ambos os membros (com relação aos valores de ), e considerando que pode ser ilimitado inferiormente, tem-se para qualquer :

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

|
- Exercício
Verifique que:

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:
, dada por

e também
, dada por

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

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

e

- Comentários
- As funções
e
são conhecidas na literatura como funções em dualidade (ou mais frequentemente, funções duais);
- O problema
é conhecido como problema primal, enquanto
é chamado de problema dual;
- Fazendo
e
, segue-se do exercício anterior que
;
- A diferença
é chamada de brecha de dualidade, ou salto de dualidade (do inglês, skip duality);
- Exercício
Verifique que:

Resolução
|
Se tem-se que e .
Substituindo na lagrangeana tem-se que e tomando , se vê que o supremo dos valores é atingido, tendo como valor.
Por outro lado, se existe um índice tal que e/ou .
No primeiro caso, seja e
, onde .
Com esta escolha, a lagrangiana será
.
Tomando o limite quando tem-se que .
Para o outro caso a prova é análoga.
|
- Exercício
Verifique que
consiste de maximizar uma função côncava em um poliedro. Lembre-se:
- Uma função
é côncava quando
for convexa.
- Um poliedro é qualquer intersecção finita de semiespaços fechados.
Resolução
|
Primeiro será mostrado que : , dada por é uma função côncava. Para isso, basta mostrar que para cada vale
.
Chamando e tem-se:
![{\displaystyle {\begin{aligned}\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)\\&\geq \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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/434f94214c721abea1b49027c86d23a09e6cdda7)
Quanto ao conjunto ser um poliedro, isso segue do fato de e serem interseções finitas de semiespaços fechados.
|
Considere o problema

Resolução
|
O problema é ilustrado na imagem a direita.
Primeiramente, é preciso identificar quais são as funções e envolvidas:
- A função objetivo é aquela que se pretende minimizar, ou seja,
;
- Como aparecem apenas restrições de desigualdade, não há qualquer função
;
- Reescrevendo as desigualdades como
e , conclúi-se que as funções são:
e .
Neste caso, a lagrangiana é:
, dado por

Em seguida, é preciso calcular e :
, é dada por
![{\displaystyle \alpha (x)=\sup _{\begin{smallmatrix}u_{1}\geq 0\\u_{2}\geq 0\end{smallmatrix}}[x^{2}+u_{1}(1-x)+u_{2}(x-2)]=x^{2}+\sup _{u_{1}\geq 0}[u_{1}(1-x)]+\sup _{u_{2}\geq 0}[u_{2}(x-2)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9082a1a4303bb18a33f94ea92a7ce881fd704ed6)
E, conforme um dos exercícios anteriores (ou através de uma breve análise dos supremos envolvidos na expressão anterior), tem-se:
![{\displaystyle \alpha (x)=\left\{{\begin{matrix}x^{2}&,{\text{ se }}x\in [1,2]\\+\infty &,{\text{ se }}x\not \in [1,2]\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6439ceff6745a32d909c0b7036f317d6d7726133)
Analogamente, tem-se:
, dada por
![{\displaystyle \beta (u_{1},u_{2})=\inf _{x\in \mathbb {R} ^{n}}[x^{2}+u_{1}(1-x)+u_{2}(x-2)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a98376c97397bf81c9b1fb4a087f4270c5347ad2)
Observe que em relação a , tem-se uma função fortemente convexa, que portanto possui um único minimizador. Além disso, é diferenciável, donde o seu único minimizador é dado pela equação:

ou seja,

donde

Portanto,

Assim, os problemas em dualidade são:

e

Pelo primeiro item do exercício, tem-se que a minimização do problema é equivalente à minimização do problema original.
Por outro lado, através da lagrangiana, obtem-se além do problema primal , um problema dual , cuja estrutura é muito melhor que a do original (pois pelo outro exercício, consiste da maximização de uma função côncava em um poliedro), e que servirá para encontrar o mínimo do problema primal (e consequentemente, do original).
|
Este é um conceito muito importante relacionado à lagrangiana.
- Definição
Dado o problema
e a lagrangiana
associada a esse problema, se diz que
é um ponto de sela de
se
e:
.
Demonstração
|
Se é um ponto de sela de , então e se tem:
.
Em particular, como
.
segue da segunda desigualdade que

e calculando o ínfimo sobre todos os tem-se:

Por outro lado, da inequação sobre ínfimos e supremos, tem-se , então .
Logo, todos os membros das desigualdades acima coincidem, ou seja,

Mas da definição de tem-se:
.
Portanto, é solução do problema enquanto significa que é solução de
Reciprocamente, supondo que é solução do problema , tem-se:

e admitindo que é solução do problema , segue:

Além disso, usando como hipótese que , segue da definição que:
, quaisquer que sejam .
Em particular, tomando , e , resulta:
, ou seja,
Logo, pela definição de tem-se:
, quaisquer que sejam .
Portanto, é um ponto de sela da lagrangiana .
|
Considere novamente o problema de otimização dado por:

Verificar se a lagrangiana associada à
tem ponto de sela.
Resolução
|
O problema é ilustrado na imagem a direita, e conforme foi deduzido anteriormente, tem-se:




Além disso, como foi mostrado anteriormente, vale
![{\displaystyle \alpha (x)=\left\{{\begin{matrix}x^{2}&,{\text{ se }}x\in [1,2]\\+\infty &,{\text{ se }}x\not \in [1,2]\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6439ceff6745a32d909c0b7036f317d6d7726133)
e também

ou seja,
![{\displaystyle {\begin{aligned}\beta (u,v)&={\frac {1}{4}}([u_{1}^{2}+u_{2}^{2}-2u_{1}u_{2}]+[4u_{1}-2u_{1}^{2}+2u_{1}u_{2}]+[2u_{1}u_{2}-2u_{2}^{2}-8u_{2}])\\&={\frac {-1}{4}}(u_{1}^{2}+u_{2}^{2}-2u_{1}u_{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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6736fe63d7f9bf147b002019b991a95de3c9aa5b)
Agora, consideram-se os seguintes problemas em dualidade:

e

Donde é solução do problema primal, e .
Intuitivamente, nos pontos em que assumir seu valor máximo, deve-se ter , pois conforme aumenta, decresce.
Mas pela desigualdade a respeito de supremos e ínfimos, tem-se , quaisquer que sejam , .
Como , e ao tomar e tem-se , segue-se que é uma solução do problema dual .
Finalmente, como , e , segue que . Portanto, pelo teorema anterior, o ponto é ponto de sela da lagrangiana .
|
Considerando
,
,
e
, se
é uma solução do problema dual, considere o seguinte problema:

que no caso do exemplo reduz-se a

A solução deste problema é obtida resolvendo
, sendo portanto
. Note que esta é a solução do problema primal
(e consequentemente do problema original
).
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
são de classe
e convexas, e que as funções
são afim lineares e
. Nestas condições:
- Se o problema
tem solução, então
e os problemas
e
têm solução.
- Se
tem solução, e
é solução de
, então as soluções de
são as soluções de
, onde

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

.
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
, pode-se optar por resolver
(um problema concavo em um poliedro), e depois resolver
(que é um problema convexo sem restrições). Em outras palavras, é possível trocar um problema difícil por dois problemas mais fáceis,
e
.
Agora a demonstração do teorema:
Demonstração
|
(1) Como tem solução, seja uma solução de . Pelo teorema de KKT (que se aplica pois as funções são de classe e se tem a qualificação das restrições), segue a existência de e , tais que:





Como são funções convexas e afim lineares, então a função lagrangiana é convexa em (pela forma de ). Isto significa que:
.
Usando (1), conclúi-se uma das duas desigualdades que definem um ponto de sela em :
.
Considerando que é solução de , tal ponto satisfaz as restrições e . Então, usando , segue que:

pois e .
Mas, por KKT, . Além disso, .
Logo:

Assim,

quaisquer que sejam , e . Mas isso implica, por definição, que é um ponto de sela de .
Logo, , é solução do problema primal e é solução do problema dual
(2)Seja solução de (que existe, pelo item 1). Sabe-se pelo item anterior que o problema primal tem solução e que .
Seja solução de . Então, é ponto de sela de , logo valem as desigualdades:
.
Uma vez que está fixo e a segunda desigualdade vale para qualquer , conclui-se que é solução do problema

As soluções deste problema são soluções de e, consequentemente, do problema original.
|
- Exercício
Verificar se existe salto de dualidade nos problemas em dualidade para o seguinte problema de minimização:

- Exercício
Juntamente com o problema
do exercício anterior, considere o seguinte problema:

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

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
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
a lagrangiana
e os problemas em dualidade
e
e
soluções de
.
Se
é solução do problema


(o conjunto dos pontos que satisfazem as restrições) e

, então

é também uma solução do problema

.
Tal proposição fornece um roteiro para quem precisa resolver o problema
relativamente difícil:
- Primeiramente, resolve-se
;
- Depois, constrói-se o problema
e encontra-se uma solução
para o mesmo;
- Finalmente, se
satisfaz as últimas condições da proposição, ele é também uma solução de
.
Demonstração
|
Se é uma solução de , . Então, pela definição de , tem-se:

Como é solução de , então:

ou seja,

Portanto,

Por outro lado, como , tem-se e .
Por hipótese, , então

Logo,
.
Então para tem-se que e . Consequentemente,

quaisquer que sejam , ou seja,
,
quaisquer que sejam .
Portanto, é ponto de sela de , e assim, é solução primal (solução de ), e em consequência, solução de .
|
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

onde
são funções de classe
, e seja a lagrangiana
definido por
.
Convenciona-se que:
é a variável primal;
é a variável dual;
Nesse sentido, "o
é o dual de
" (não confundir com o significado que essa expressão teria na análise funcional. Ver nota sobre a terminologia), ou seja:
é onde "mora" a variável primal
;
é onde "mora" a variável dual
;
Definem-se então as funções
e
da seguinte maneira:
, dada por

e
, dada por

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

e

É possível verificar que
equivale ao problema original
e que
consiste da maximização de uma função côncava em um poliedro (convexo).
Logo, o dual de
é
.
Dado qualquer problema
, seu dual
é 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)".
Na subárea da matemática denominada Análise Funcional, quando se tem um espaço topológico
, costuma-se chamar de dual topológico ao conjunto
.
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.