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.

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

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

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.

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:

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

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:

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

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

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

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:

Uma função $f$ é côncava quando $-f$ for convexa.
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:

${\bar {x}}$ é solução de $(Pr)$ ;
$({\bar {u}},{\bar {v}})$ é solução de $(D)$ ;
${\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:

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.

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:

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

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.