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$

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}}))\geq f({\bar {x}})=\theta (0)$, para todo $t\in (0,1)$ Logo, ${\frac {\theta (t)-\theta (0)}{t-0}}\geq 0$, ou seja, $\theta '(0)=\lim _{t\to 0}{\frac {\theta (t)-\theta (0)}{t-0}}\geq 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 \geq 0$. Como $x\in C$ era arbitrário, o resultado está demonstrado.

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:

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 \geq 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)\geq f({\bar {x}})+\langle \nabla f(x),x-{\bar {x}}\rangle ,\,\forall x\in \mathbb {R} ^{n}$ Logo, $f(x)-f({\bar {x}})\geq \langle \nabla f(x),x-{\bar {x}}\rangle \geq 0,\,\forall x\in C$ Portanto, $f(x)\geq 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 \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$

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 \geq 0,\,\forall x\in C$ Observe que essa desigualdade equivale à $\langle \alpha \nabla f(x),x-{\bar {x}}\rangle \geq 0,\,\forall x\in C$ ou ainda $\langle {\bar {x}}-({\bar {x}}-\alpha \nabla f(x)),x-{\bar {x}}\rangle \geq 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 \geq 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 \geq 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)\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

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

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)\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

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}\geq 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}\geq 0,\,\forall i=1,\ldots ,p$
3. $u_{i}g_{i}({\bar {x}})=0,\,\forall i=1,\ldots ,p$
4. $g_{i}({\bar {x}})\leq 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)\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:

1. $\nabla _{x}l({\bar {x}},{\bar {u}},{\bar {v}})=0$
2. ${\bar {u}}\geq 0$
3. $\nabla _{u}l({\bar {x}},{\bar {u}},{\bar {v}})\leq 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 \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$

Demonstração

Sabe-se que $K(x,y)\leq \sup _{y\in Y}K(x,y)\leq +\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 \leq \inf _{x\in X}K(x,y)\leq \inf _{x\in X}\sup _{y\in Y}K(x,y)\leq +\infty$ Assim, calculando o supremo (com relação aos valores de $y$), segue das desigualdades anteriores: $-\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$

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\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

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\geq 0\\v\in \mathbb {R} ^{q}\end{smallmatrix}}\beta (u,v)$, segue-se do exercício anterior que ${\bar {\beta }}\leq {\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)\leq 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\neq 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)\geq 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{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}}$ Quanto ao conjunto ser um poliedro, isso segue do fato de $\mathbb {R} ^{q}$ e $u\geq 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\leq x\leq 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\leq 0$ e $x-2\leq 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}\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)]$ 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, $2x_{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}\geq 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 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:

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}}\geq 0$ e se tem: $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}$. Em particular, como $\alpha ({\bar {x}})=\sup _{\begin{smallmatrix}u\geq 0\\v\in \mathbb {R} ^{q}\end{smallmatrix}}l({\bar {x}},u,v)\leq l({\bar {x}},{\bar {u}},{\bar {v}})$. segue da segunda desigualdade que ${\bar {\alpha }}\leq \alpha ({\bar {x}})\leq l({\bar {x}},{\bar {u}},{\bar {v}})\leq 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 }}\leq \alpha ({\bar {x}})\leq l({\bar {x}},{\bar {u}},{\bar {v}})\leq \inf _{x\in \mathbb {R} ^{n}}l(x,{\bar {u}},{\bar {v}})=\beta ({\bar {u}},{\bar {v}})\leq {\bar {\beta }}$ Por outro lado, da inequação sobre ínfimos e supremos, tem-se ${\bar {\alpha }}\geq {\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\geq 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\geq 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)\leq \alpha ({\bar {x}})={\bar {\alpha }}={\bar {\beta }}=\beta ({\bar {u}},{\bar {v}})\leq l(x,{\bar {u}},{\bar {v}})$, quaisquer que sejam $x\in \mathbb {R} ^{n},u\geq 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}})\leq {\bar {\alpha }}={\bar {\beta }}\leq 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)\leq \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\geq 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\leq x\leq 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{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}}$ 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}\geq 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})\leq \alpha ({\bar {x}})=1$, quaisquer que sejam $u_{1}\geq 0$, $u_{2}\geq 0$. Como $\beta (u_{1},u_{2})\leq 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}}\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$ 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}})\geq 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}})\geq l({\bar {x}},{\bar {u}},{\bar {v}})$. Considerando que ${\bar {x}}$ é solução de $(P)$, tal ponto satisfaz as restrições $g_{i}(x)\leq 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)\leq f({\bar {x}})$ pois $h_{j}({\bar {x}})=0$ e $u_{i}\geq 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}})\geq l({\bar {x}},{\bar {u}},{\bar {v}})\geq l({\bar {x}},u,v)$ quaisquer que sejam $x\in \mathbb {R} ^{n}$, $u\geq 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)\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}$. 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}\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? 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\geq 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}})\leq 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)\leq 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\geq 0$ tem-se que $u_{i}g_{i}({\bar {x}})\leq 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}})\leq f({\bar {x}})$ quaisquer que sejam $u\geq 0,v\in \mathbb {R} ^{q}$, ou seja, $l({\bar {x}},u,v)=f({\bar {x}})=l({\bar {x}},{\bar {u}},{\bar {v}})\leq l(x,{\bar {u}},{\bar {v}})$, quaisquer que sejam $u\geq 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)\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.