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\to ℝ\cup \{+\mathrm{\infty }\}$, podemos definir o problema primordial como encontrar $\hat{x}$de tal modo que $f(\hat{x})=\underset{xϵX}{\inf }f(x)$. Em outras palavras, se $\hat{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ϵ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)=\mathrm{\infty }$de outra forma). Então estenda $\tilde{f}$ para uma função de perturbação $F:X\times Y\to ℝ\cup \{+\mathrm{\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^{*}ϵY^{*}}{sup}-F^{*}(0,y^{*})\le \underset{xϵ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$ $f_0(x)$

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

$h_i(x)=0,i$∈ {$1,...,p$}

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

$\mathrm{\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:{ℝ}^m\times {ℝ}^p\to ℝ$ é definida como

$g(\lambda ,\nu )=\underset{xϵ𝒟}{\inf }\mathrm{\Lambda }(x,\lambda ,\nu )=\underset{xϵ𝒟}{\inf }(f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^m{\nu }_i{h}_i(x))$

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 \ge 0$ e qualquer $\nu$ temos $g(\lambda ,\nu )\le 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 ⩾0,\nu }{max}g(\lambda ,\nu )=inf{f}_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)\le 0,i=1,...,m$

o problema Lagrangiano dual é

$\underset{u}{maximize}$ $\underset{x}{\inf }(f(x)+\sum _{j=1}^m{u}_j{g}_j(x))$

$sujeito$ $a$ $u_i\ge 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$ $▽f(x)+\sum _{j=1}^m{u}_j▽g_j(x)=0$

$u_i\ge 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 $▽f(x)+\sum _{j=1}^m{u}_j▽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)