Dualidade (otimização) - Duality (optimization)

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

Problema duplo

Normalmente, o termo "problema duplo" se refere ao problema dual de Lagrange, mas outros problemas duais são usados ​​- por exemplo, o problema duplo de Wolfe e o problema duplo de Fenchel . O problema dual de Lagrange é obtido formando o Lagrangiano de um problema de minimização usando multiplicadores de Lagrange não negativos para adicionar as restrições à função objetivo, e então resolvendo para os valores das variáveis ​​primárias que minimizam a função objetivo original. Esta solução dá as variáveis ​​primais como funções dos multiplicadores de Lagrange, que são chamados de variáveis ​​duais, de modo que o novo problema é maximizar a função objetivo com respeito às variáveis ​​duais sob as restrições derivadas nas variáveis ​​duais (incluindo pelo menos a não negatividade restrições).

Em geral dado dois pares de duplas de separados espaços localmente convexos e e a função , podemos definir o problema primal como encontrar de tal forma que em outras palavras, se existe, é o mínimo da função eo ínfimo (maior limite inferior) da função é alcançado.

Se houver condições de restrição, elas podem ser incorporadas à função , deixando onde está uma função adequada com um mínimo de 0 nas restrições e para a qual se pode provar isso . A última condição é trivialmente, mas nem sempre convenientemente, satisfeita para a função característica (isto é, para satisfazer as restrições e de outra forma). Em seguida, estenda a uma função de perturbação tal que .

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

onde é o conjugado convexo em ambas as variáveis ​​e denota o supremo (menor limite superior).

Lacuna de dualidade

A lacuna de dualidade é a diferença entre os valores de quaisquer soluções primárias e quaisquer soluções duais. Se é o valor dual ideal e é o valor primal ideal, então a lacuna de dualidade é igual a . Este valor é sempre maior ou igual a 0. A lacuna de dualidade é zero se e somente se a dualidade forte for mantida . Caso contrário, a lacuna é estritamente positiva e a dualidade fraca se mantém.

Na otimização computacional, outra "lacuna de dualidade" é freqüentemente relatada, que é a diferença de valor entre qualquer solução dual e o valor de uma iteração viável, mas subótima, para o problema primordial. Essa "lacuna de dualidade" alternativa quantifica a discrepância entre o valor de uma iteração atual viável, mas subótima, para o problema primordial e o valor do problema dual; o valor do problema dual é, em condições de regularidade, igual ao valor da relaxação convexa do problema primordial: A relaxação convexa é o problema que surge substituindo um conjunto viável não convexo por seu casco convexo fechado e substituindo um não função convexa com seu fechamento convexo , que é a função que tem a epígrafe que é o casco convexo fechado da função objetivo primordial original.

Caso linear

Problemas de programação linear são problemas de otimização em que a função objetivo e as restrições são todas lineares . No problema primário, 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 objetivo sujeito às restrições. Uma solução é um vetor (uma lista) de n valores que atinge o valor máximo para a função objetivo.

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

Relação entre o problema primordial e o problema dual

No caso linear, no problema primordial, de cada ponto sub-ótimo que satisfaça todas as restrições, há uma direção ou subespaço de direções para mover que aumenta a função objetivo. Diz-se que mover em qualquer uma dessas direções remove 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 do problema primal. O limite superior mais baixo é procurado. Ou seja, o vetor dual é minimizado a fim de 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. Ele define as posições candidatas de uma ou mais restrições em uma posição que exclui o ótimo real.

Esta intuição é formalizada pelas equações da 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 freqüentemente requer que as funções sejam convexas e tenham conjuntos compactos de nível inferior.

Este é o significado das condições Karush – Kuhn – Tucker . Eles fornecem as 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 Lagrangiano forte: dualidade de Lagrange

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

com o domínio tendo um interior não vazio, a função Lagrangiana é definida como

Os vetores e são chamados de variáveis ​​duais ou vetores multiplicadores de Lagrange associados ao problema. A função dupla de Lagrange é definida como

A função dual g é côncava, mesmo quando o problema inicial não é convexo, porque é um ínfimo ponto-a-ponto de funções afins. A função dual produz limites inferiores no valor ótimo do problema inicial; para qualquer e qualquer que tenhamos .

Se uma qualificação restrição , como condição de Slater detém e o problema original é convexo, então temos forte dualidade , ou seja .

Problemas convexos

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

o problema duplo de Lagrange é

onde a função objetivo é a função dupla de Lagrange. Desde que as funções e sejam continuamente diferenciáveis, o ínfimo ocorre onde o gradiente é igual a zero. O problema

é chamado de problema duplo de Wolfe. Este problema pode ser difícil de lidar computacionalmente, porque a função objetivo não é côncava nas variáveis ​​conjuntas . Além disso, a restrição de igualdade em geral não é linear, de modo que o problema duplo de Wolfe é normalmente um problema de otimização não convexa. Em qualquer 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 observou que estava usando informações de sua teoria dos jogos e conjeturou que o jogo de matriz de soma zero de duas pessoas era equivalente à 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)

Veja também

Notas

Referências

Livros

Artigos