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
- Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Fluxos de rede: teoria, algoritmos e aplicações . Prentice Hall. ISBN 0-13-617549-X.
- Bertsekas, Dimitri; Nedic, Angelia; Ozdaglar, Asuman (2003). Análise e otimização convexa . Athena Scientific. ISBN 1-886529-45-0.
- Bertsekas, Dimitri P. (1999). Programação não linear (2ª ed.). Athena Scientific. ISBN 1-886529-00-0.
- Bertsekas, Dimitri P. (2009). Teoria da Otimização Convexa . Athena Scientific. ISBN 978-1-886529-31-1.
- Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Otimização numérica: Aspectos teóricos e práticos . Universitext (segunda edição revisada da tradução da edição francesa de 1997). Berlim: Springer-Verlag. pp. xiv + 490. doi : 10.1007 / 978-3-540-35447-5 . ISBN 3-540-35445-X. MR 2265882 .
- Cook, William J .; Cunningham, William H .; Pulleyblank, William R .; Schrijver, Alexander (12 de novembro de 1997). Otimização combinatória (1ª ed.). John Wiley & Sons. ISBN 0-471-55894-X.
- Dantzig, George B. (1963). Programação linear e extensões . Princeton, NJ: Princeton University Press.
- Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Análise convexa e algoritmos de minimização, Volume I: Fundamentos . Grundlehren der Mathematischen Wissenschaften [Princípios Fundamentais das Ciências Matemáticas]. 305 . Berlim: Springer-Verlag. pp. xviii + 417. ISBN 3-540-56850-6. MR 1261420 .
- Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "14 Dualidade para praticantes". Análise convexa e algoritmos de minimização, Volume II: Teoria avançada e métodos de pacote . Grundlehren der Mathematischen Wissenschaften [Princípios Fundamentais das Ciências Matemáticas]. 306 . Berlim: Springer-Verlag. pp. xviii + 346. ISBN 3-540-56852-2. MR 1295240 .
- Lasdon, Leon S. (2002) [Reimpressão do Macmillan 1970]. Teoria de otimização para grandes sistemas . Mineola, Nova York: Dover Publications, Inc. pp. Xiii + 523. ISBN 978-0-486-41999-2. MR 1888251 .
- Lawler, Eugene (2001). "4.5. Implicações combinatórias do teorema de corte mínimo de fluxo máximo, 4.6. Interpretação de programação linear do teorema de corte mínimo de fluxo máximo". Otimização Combinatória: Redes e Matroids . Dover. pp. 117-120. ISBN 0-486-41453-1.
- Lemaréchal, Claude (2001). “Relaxamento Lagrangiano”. Em Jünger, Michael; Naddef, Denis (eds.). Otimização combinatória computacional: Artigos da Spring School realizada em Schloß Dagstuhl, de 15 a 19 de maio de 2000 . Notas de aula em Ciência da Computação (LNCS). 2241 . Berlim: Springer-Verlag. pp. 112–156. doi : 10.1007 / 3-540-45586-8_4 . ISBN 3-540-42877-1. MR 1900016 .
- Minoux, Michel (1986). Programação matemática: teoria e algoritmos . Egon Balas (avançado); Steven Vajda (trad.) From the (1983 Paris: Dunod) French. Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. pp. Xxviii + 489. ISBN 0-471-90170-9. MR 0868279 . (2008 Second ed., Em francês: Programmation mathématique: Théorie et algoritmes , Éditions Tec & Doc, Paris, 2008. xxx + 711 pp.)).
- Nering, Evar D .; Tucker, Albert W. (1993). Programação linear e problemas relacionados . Boston, MA: Academic Press. ISBN 978-0-12-515440-6.
- Papadimitriou, Christos H .; Steiglitz, Kenneth (julho de 1998). Otimização combinatória: algoritmos e complexidade (edição não abreviada). Dover. ISBN 0-486-40258-4.
- Ruszczyński, Andrzej (2006). Otimização não linear . Princeton, NJ: Princeton University Press . pp. xii + 454. ISBN 978-0691119151. MR 2199043 .
Artigos
- Everett, Hugh, III (1963). "Método do multiplicador de Lagrange generalizado para resolver problemas de alocação ótima de recursos" . Pesquisa Operacional . 11 (3): 399–417. doi : 10.1287 / opre.11.3.399 . JSTOR 168028 . MR 0152360 . Arquivado do original em 24/07/2011.
- Kiwiel, Krzysztof C .; Larsson, Torbjörn; Lindberg, P. O. (agosto de 2007). "Relaxamento Lagrangiano via métodos do subgradiente ballstep" . Matemática da Pesquisa Operacional . 32 (3): 669–686. doi : 10.1287 / moor.1070.0261 . MR 2348241 .
- Dualidade em programação linear Gary D. Knott