Dualidade (otimização)

Na teoria da otimização matemática, a dualidade, ou princípio da dualidade, é o princípio de que os problemas de otimização podem ser vistos a partir de duas perspectivas: o problema primordial (primal) ou o problema dual. A solução para o problema dual fornece um limite inferior para a solução do problema primal (minimização). No entanto, em geral, os valores ótimos dos problemas primários e duais não precisam ser iguais. Sua diferença é chamada de diferença de dualidade. Para problemas de otimização convexa, a diferença de dualidade é zero sob uma condição de qualificação de restrição.

Problema dual

Geralmente, o termo "problema dual" refere-se ao problema dual de Lagrange, mas outros problemas duais são usados ​​- por exemplo, o problema dual de Wolfe e o problema dual de Fenchel. O problema dual de Lagrange é obtido pela formação do Lagrangeano de um problema de minimização usando multiplicadores de Lagrange não-negativos para adicionar as restrições à função objetivo e, em seguida, resolvendo os valores primários das variáveis ​​que minimizam a função objetivo original. Essa solução fornece as variáveis ​​primárias como funções dos multiplicadores de Lagrange, que são chamadas de variáveis ​​duais, de modo que o novo problema é maximizar a função objetivo com relação às variáveis ​​duais sob as restrições derivadas nas variáveis ​​duais (incluindo pelo menos a não-negatividade restrições).

Em geral, dados dois pares duplos de espaços locais convexos separados $(X,X^{*})$e $(Y,Y^{*})$e a função $f:X\rightarrow \mathbb {R} \cup \{+\infty \}$, podemos definir o problema primordial como encontrar ${\widehat {x}}$de tal modo que $f({\hat {x}})={\underset {x\epsilon X}{\inf }}f(x)$. Em outras palavras, se ${\widehat {x}}$ existe, $f({\hat {x}})$ é o mínimo da função $f$ e o ínfimo (maior limite inferior) da função é atingido.

Se houver condições de restrição, elas podem ser incorporadas na função $f$ deixando ${\tilde {f}}=f+Irestric{\tilde {o}}es$ onde $Irestric{\check {o}}es$ é uma função adequada em $X$que tem um mínimo de 0 sobre as restrições, e para o qual se pode provar que ${\underset {x\epsilon X}{\inf }}{\check {f}}(x)={\underset {x_{restric{\check {o}}es}}{\inf }}f(x)$. Esta última condição é trivial, mas nem sempre convenientemente satisfeita para a função característica (ou seja, $Irestric{\check {o}}es(x)=0$para $x$ satisfazendo as restrições e $Irestric{\check {o}}es(x)=\infty$de outra forma). Então estenda ${\tilde {f}}$ para uma função de perturbação $F:X\times Y\rightarrow \mathbb {R} \cup \{+\infty \}$, de tal modo que $F(x,0)={\tilde {f}}(x)$.

A diferença de dualidade é a diferença dos lados direito e esquerdo da desigualdade

${\underset {y^{*}\epsilon Y^{*}}{sup}}-F^{*}(0,y^{*})\leq {\underset {x\epsilon X}{inf}}F(x,0)$,

onde $F^{*}$ é o conjugado convexo nas duas variáveis e $sup$ denota o supremo (menor limite superior).

Diferença de dualidade

Artigo principal: diferença de dualidade

O gap (ou diferença) de dualidade é a diferença entre os valores de quaisquer soluções primárias e quaisquer soluções duplas. Se $d^{*}$ é o valor dual ideal e $p^{*}$ é o valor primal ótimo, então o gap de dualidade é igual a $p^{*}-d^{*}$. Este valor é sempre maior que ou igual a 0. O gap de dualidade é zero se e somente se a dualidade forte for válida. Caso contrário, a lacuna é estritamente positiva e a dualidade é fraca.

Na otimização computacional, outro "gap de dualidade" é frequentemente relatado, que é a diferença de valor entre qualquer solução dual e o valor de uma iteração factível, mas sub-ótima, para o problema primordial. Essa alternativa "gap de dualidade" quantifica a discrepância entre o valor de uma iteração factível, mas sub ótima, para o problema primordial e o valor do problema dual; o valor do problema duplo é, sob condições de regularidade, igual ao valor do relaxamento convexo do problema primário: o relaxamento convexo é o problema que surge substituindo um conjunto viável não convexo por seu casco convexo fechado e com a substituição de uma função não-convexa com o seu fechamento convexo, que é a função que tem a epígrafe que é o casco convexo fechado da função objetivo primitiva original.

Caso linear

Artigo principal: dual linear program

Problemas de programação linear são problemas de otimização nos quais a função objetivo e as restrições são todas lineares. No problema primal, a função objetivo é uma combinação linear de n variáveis. Existem m restrições, cada uma das quais coloca um limite superior em uma combinação linear das n variáveis. O objetivo é maximizar o valor da função objetiva sujeita às restrições. Uma solução é um vetor (uma lista) de n valores que alcança o valor máximo para a função objetivo.

No problema dual, a função objetivo é uma combinação linear dos valores m que são os limites nas restrições m do problema primal. Existem n restrições duplas, cada uma das quais coloca um limite inferior em uma combinação linear de m variáveis duplas.

Relações primais-duais

No caso linear, no problema primal, de cada ponto sub-ótimo que satisfaz todas as restrições, existe uma direção ou subespaço de direções para mover que aumenta a função objetivo. Movendo-se em tal direção é dito para remover a folga entre a solução candidata e uma ou mais restrições. Um valor inviável da solução candidata é aquele que excede uma ou mais das restrições.

No problema dual, o vetor dual multiplica as restrições que determinam as posições das restrições no primal. Variar o vetor dual no problema dual é equivalente a revisar os limites superiores no problema primal. O limite superior mais baixo é procurado. Ou seja, o vetor dual é minimizado para remover a folga entre as posições candidatas das restrições e o ótimo real. Um valor inviável do vetor dual é aquele que é muito baixo. Define as posições candidatas de uma ou mais das restrições em uma posição que exclui o ótimo real.

Esta intuição é formalizada pelas equações em Programação Linear: Dualidade.

Caso não linear

Na programação não linear, as restrições não são necessariamente lineares. No entanto, muitos dos mesmos princípios se aplicam.

Para garantir que o máximo global de um problema não linear possa ser identificado facilmente, a formulação do problema frequentemente requer que as funções sejam convexas e tenham conjuntos de nível mais baixo compactos.

Este é o significado das condições de Karush-Kuhn-Tucker. Eles fornecem condições necessárias para identificar ótimos locais de problemas de programação não linear. Existem condições adicionais (qualificações de restrição) que são necessárias para que seja possível definir a direção para uma solução ótima. Uma solução ótima é aquela que é um ótimo local, mas possivelmente não é um ótimo global.

O princípio Lagrangeano forte: dualidade de Lagrange

Dado um problema de programação não linear na forma padrão

$minimize$ ${\textstyle f_{0}(x)}$

$sujeito$ $a$ ${\textstyle f_{i}(x)}$≤0, $i$∈ {${1,...,m}$}

${\textstyle h_{i}(x)=0,i}$∈ {${1,...,p}$}

com o domínio $D\subset R^{n}$ tendo interior não vazio, a função Lagrangiana $\Lambda :\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\rightarrow \mathbb {R}$

$\Lambda (x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x)$

Os vetores $\lambda$ e $\nu$ são chamados de variáveis dual ou vetores multiplicadores de Lagrange associados ao problema. A função dual de Lagrange $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\rightarrow \mathbb {R}$ é definida como

$g(\lambda ,\nu )={\underset {x\epsilon {\mathcal {D}}}{\inf }}\Lambda (x,\lambda ,\nu )={\underset {x\epsilon {\mathcal {D}}}{\inf }}{\Bigl (}f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{m}\nu _{i}h_{i}(x){\Bigr )}$

A função dual g é côncava, mesmo quando o problema inicial não é convexo, porque é um ponto mínimo de funções afins. A função dupla produz limites inferiores no valor ideal $p^{*}$do problema inicial; para qualquer $\lambda \geq 0$ e qualquer $\nu$ temos $g(\lambda ,\nu )\leq p^{*}$.

Se uma qualificação de restrição, como a condição de Slater, e o problema original é convexo, então temos uma forte dualidade, ou seja,
$d^{*}={\underset {\lambda \geqslant 0,\nu }{max}}g(\lambda ,\nu )=inff_{0}=p^{*}$.

Problemas convexos

Para um problema de minimização convexa com restrições de desigualdade,

${\underset {x}{minimize}}$ $f(x)$

$sujeito$ $a$ $g(x)\leq 0,i=1,...,m$

o problema Lagrangiano dual é

${\underset {u}{maximize}}$ ${\underset {x}{\inf }}{\Bigl (}f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x){\Bigr )}$

$sujeito$ $a$ $u_{i}\geq 0,u=1,...,m$

onde a função objetivo é a função Lagrange dual. Desde que as funções $f$ e $g_{1},...,g_{m}$ são continuamente diferenciáveis, o ínfimo ocorre onde o gradiente é igual a zero. O problema

${\underset {x,u}{maximize}}$ $f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)$

$sujeito$ $a$ $\bigtriangledown f(x)+\sum _{j=1}^{m}u_{j}\bigtriangledown g_{j}(x)=0$

$u_{i}\geq 0,i=1,...,m$

é chamado o problema dual de Wolfe. Este problema pode ser difícil de lidar computacionalmente, porque a função objetivo não é côncava nas variáveis ​​conjuntas $(u,x)$. Além disso, a restrição de igualdade $\bigtriangledown f(x)+\sum _{j=1}^{m}u_{j}\bigtriangledown g_{j}(x)=0$é não-linear em geral, então o problema dual de Wolfe é tipicamente um problema de otimização não-convexo. Em todo caso, a dualidade fraca se mantém.

História

De acordo com George Dantzig, o teorema da dualidade para otimização linear foi conjecturado por John von Neumann, imediatamente após Dantzig apresentar o problema de programação linear. Von Neumann notou que ele estava usando informações de sua teoria dos jogos e conjeturou que o jogo de duas pessoas com soma zero era equivalente a programação linear. Provas rigorosas foram publicadas pela primeira vez em 1948 por Albert W. Tucker e seu grupo. (Prefácio de Dantzig para Nering e Tucker, 1993)

Ver também

• Dualidade
• Relaxamento (aproximação)