b'\n_START_ARTICLE_\nDualidade (otimiza\xc3\xa7\xc3\xa3o)\n_START_SECTION_\nProblema dual\n_START_PARAGRAPH_\nGeralmente, o termo "problema dual" refere-se ao problema dual de Lagrange, mas outros problemas duais s\xc3\xa3o usados \xe2\x80\x8b\xe2\x80\x8b- por exemplo, o problema dual de Wolfe e o problema dual de Fenchel. O problema dual de Lagrange \xc3\xa9 obtido pela forma\xc3\xa7\xc3\xa3o do Lagrangeano de um problema de minimiza\xc3\xa7\xc3\xa3o usando multiplicadores de Lagrange n\xc3\xa3o-negativos para adicionar as restri\xc3\xa7\xc3\xb5es \xc3\xa0 fun\xc3\xa7\xc3\xa3o objetivo e, em seguida, resolvendo os valores prim\xc3\xa1rios das vari\xc3\xa1veis \xe2\x80\x8b\xe2\x80\x8bque minimizam a fun\xc3\xa7\xc3\xa3o objetivo original. Essa solu\xc3\xa7\xc3\xa3o fornece as vari\xc3\xa1veis \xe2\x80\x8b\xe2\x80\x8bprim\xc3\xa1rias como fun\xc3\xa7\xc3\xb5es dos multiplicadores de Lagrange, que s\xc3\xa3o chamadas de vari\xc3\xa1veis \xe2\x80\x8b\xe2\x80\x8bduais, de modo que o novo problema \xc3\xa9 maximizar a fun\xc3\xa7\xc3\xa3o objetivo com rela\xc3\xa7\xc3\xa3o \xc3\xa0s vari\xc3\xa1veis \xe2\x80\x8b\xe2\x80\x8bduais sob as restri\xc3\xa7\xc3\xb5es derivadas nas vari\xc3\xa1veis \xe2\x80\x8b\xe2\x80\x8bduais (incluindo pelo menos a n\xc3\xa3o-negatividade restri\xc3\xa7\xc3\xb5es)._NEWLINE_Em geral, dados dois pares duplos de espa\xc3\xa7os locais convexos separados e e a fun\xc3\xa7\xc3\xa3o ,\xc2\xa0podemos definir o problema primordial como encontrar de tal modo que . Em outras palavras, se  existe, \xc2\xa0\xc3\xa9 o m\xc3\xadnimo da fun\xc3\xa7\xc3\xa3o \xc2\xa0e o \xc3\xadnfimo (maior limite inferior) da fun\xc3\xa7\xc3\xa3o \xc3\xa9 atingido._NEWLINE_Se houver condi\xc3\xa7\xc3\xb5es de restri\xc3\xa7\xc3\xa3o, elas podem ser incorporadas na fun\xc3\xa7\xc3\xa3o \xc2\xa0deixando  onde \xc2\xa0\xc3\xa9 uma fun\xc3\xa7\xc3\xa3o adequada em que tem um m\xc3\xadnimo de 0 sobre as restri\xc3\xa7\xc3\xb5es, e para o qual se pode provar que . Esta \xc3\xbaltima condi\xc3\xa7\xc3\xa3o \xc3\xa9 trivial, mas nem sempre convenientemente satisfeita para a fun\xc3\xa7\xc3\xa3o caracter\xc3\xadstica (ou seja, para  satisfazendo as restri\xc3\xa7\xc3\xb5es e de outra forma). Ent\xc3\xa3o estenda  para uma fun\xc3\xa7\xc3\xa3o de perturba\xc3\xa7\xc3\xa3o , de tal modo que ._NEWLINE_A diferen\xc3\xa7a de dualidade \xc3\xa9 a diferen\xc3\xa7a dos lados direito e esquerdo da desigualdade_NEWLINE_,_NEWLINE_onde  \xc3\xa9 o conjugado convexo nas duas vari\xc3\xa1veis e  denota o supremo (menor limite superior).\n_START_SECTION_\nDiferen\xc3\xa7a de dualidade\n_START_PARAGRAPH_\nO gap (ou diferen\xc3\xa7a) de dualidade \xc3\xa9 a diferen\xc3\xa7a entre os valores de quaisquer solu\xc3\xa7\xc3\xb5es prim\xc3\xa1rias e quaisquer solu\xc3\xa7\xc3\xb5es duplas. Se  \xc3\xa9 o valor dual ideal e  \xc3\xa9 o valor primal \xc3\xb3timo, ent\xc3\xa3o o gap de dualidade \xc3\xa9 igual a . Este valor \xc3\xa9 sempre maior que ou igual a 0. O gap de dualidade \xc3\xa9 zero se e somente se a dualidade forte for v\xc3\xa1lida. Caso contr\xc3\xa1rio, a lacuna \xc3\xa9 estritamente positiva e a dualidade \xc3\xa9 fraca._NEWLINE_Na otimiza\xc3\xa7\xc3\xa3o computacional, outro "gap de dualidade" \xc3\xa9 frequentemente relatado, que \xc3\xa9 a diferen\xc3\xa7a de valor entre qualquer solu\xc3\xa7\xc3\xa3o dual e o valor de uma itera\xc3\xa7\xc3\xa3o fact\xc3\xadvel, mas sub-\xc3\xb3tima, para o problema primordial. Essa alternativa "gap de dualidade" quantifica a discrep\xc3\xa2ncia entre o valor de uma itera\xc3\xa7\xc3\xa3o fact\xc3\xadvel, mas sub \xc3\xb3tima, para o problema primordial e o valor do problema dual; o valor do problema duplo \xc3\xa9, sob condi\xc3\xa7\xc3\xb5es de regularidade, igual ao valor do relaxamento convexo do problema prim\xc3\xa1rio: o relaxamento convexo \xc3\xa9 o problema que surge substituindo um conjunto vi\xc3\xa1vel n\xc3\xa3o convexo por seu casco convexo fechado e com a substitui\xc3\xa7\xc3\xa3o de uma fun\xc3\xa7\xc3\xa3o n\xc3\xa3o-convexa com o seu fechamento convexo, que \xc3\xa9 a fun\xc3\xa7\xc3\xa3o que tem a ep\xc3\xadgrafe que \xc3\xa9 o casco convexo fechado da fun\xc3\xa7\xc3\xa3o objetivo primitiva original.\n_START_SECTION_\nCaso linear\n_START_PARAGRAPH_\nProblemas de programa\xc3\xa7\xc3\xa3o linear s\xc3\xa3o problemas de otimiza\xc3\xa7\xc3\xa3o nos quais a fun\xc3\xa7\xc3\xa3o objetivo e as restri\xc3\xa7\xc3\xb5es s\xc3\xa3o todas lineares. No problema primal, a fun\xc3\xa7\xc3\xa3o objetivo \xc3\xa9 uma combina\xc3\xa7\xc3\xa3o linear de n vari\xc3\xa1veis. Existem m restri\xc3\xa7\xc3\xb5es, cada uma das quais coloca um limite superior em uma combina\xc3\xa7\xc3\xa3o linear das n vari\xc3\xa1veis. O objetivo \xc3\xa9 maximizar o valor da fun\xc3\xa7\xc3\xa3o objetiva sujeita \xc3\xa0s restri\xc3\xa7\xc3\xb5es. Uma solu\xc3\xa7\xc3\xa3o \xc3\xa9 um vetor (uma lista) de n valores que alcan\xc3\xa7a o valor m\xc3\xa1ximo para a fun\xc3\xa7\xc3\xa3o objetivo._NEWLINE_No problema dual, a fun\xc3\xa7\xc3\xa3o objetivo \xc3\xa9 uma combina\xc3\xa7\xc3\xa3o linear dos valores m que s\xc3\xa3o os limites nas restri\xc3\xa7\xc3\xb5es m do problema primal. Existem n restri\xc3\xa7\xc3\xb5es duplas, cada uma das quais coloca um limite inferior em uma combina\xc3\xa7\xc3\xa3o linear de m vari\xc3\xa1veis duplas.\n_START_SECTION_\nRela\xc3\xa7\xc3\xb5es primais-duais\n_START_PARAGRAPH_\nNo caso linear, no problema primal, de cada ponto sub-\xc3\xb3timo que satisfaz todas as restri\xc3\xa7\xc3\xb5es, existe uma dire\xc3\xa7\xc3\xa3o ou subespa\xc3\xa7o de dire\xc3\xa7\xc3\xb5es para mover que aumenta a fun\xc3\xa7\xc3\xa3o objetivo. Movendo-se em tal dire\xc3\xa7\xc3\xa3o \xc3\xa9 dito para remover a folga entre a solu\xc3\xa7\xc3\xa3o candidata e uma ou mais restri\xc3\xa7\xc3\xb5es. Um valor invi\xc3\xa1vel da solu\xc3\xa7\xc3\xa3o candidata \xc3\xa9 aquele que excede uma ou mais das restri\xc3\xa7\xc3\xb5es._NEWLINE_No problema dual, o vetor dual multiplica as restri\xc3\xa7\xc3\xb5es que determinam as posi\xc3\xa7\xc3\xb5es das restri\xc3\xa7\xc3\xb5es no primal. Variar o vetor dual no problema dual \xc3\xa9 equivalente a revisar os limites superiores no problema primal. O limite superior mais baixo \xc3\xa9 procurado. Ou seja, o vetor dual \xc3\xa9 minimizado para remover a folga entre as posi\xc3\xa7\xc3\xb5es candidatas das restri\xc3\xa7\xc3\xb5es e o \xc3\xb3timo real. Um valor invi\xc3\xa1vel do vetor dual \xc3\xa9 aquele que \xc3\xa9 muito baixo. Define as posi\xc3\xa7\xc3\xb5es candidatas de uma ou mais das restri\xc3\xa7\xc3\xb5es em uma posi\xc3\xa7\xc3\xa3o que exclui o \xc3\xb3timo real._NEWLINE_Esta intui\xc3\xa7\xc3\xa3o \xc3\xa9 formalizada pelas equa\xc3\xa7\xc3\xb5es em Programa\xc3\xa7\xc3\xa3o Linear: Dualidade.\n_START_SECTION_\nCaso n\xc3\xa3o linear\n_START_PARAGRAPH_\nNa programa\xc3\xa7\xc3\xa3o n\xc3\xa3o linear, as restri\xc3\xa7\xc3\xb5es n\xc3\xa3o s\xc3\xa3o necessariamente lineares. No entanto, muitos dos mesmos princ\xc3\xadpios se aplicam._NEWLINE_Para garantir que o m\xc3\xa1ximo global de um problema n\xc3\xa3o linear possa ser identificado facilmente, a formula\xc3\xa7\xc3\xa3o do problema frequentemente requer que as fun\xc3\xa7\xc3\xb5es sejam convexas e tenham conjuntos de n\xc3\xadvel mais baixo compactos._NEWLINE_Este \xc3\xa9 o significado das condi\xc3\xa7\xc3\xb5es de Karush-Kuhn-Tucker. Eles fornecem condi\xc3\xa7\xc3\xb5es necess\xc3\xa1rias para identificar \xc3\xb3timos locais de problemas de programa\xc3\xa7\xc3\xa3o n\xc3\xa3o linear. Existem condi\xc3\xa7\xc3\xb5es adicionais (qualifica\xc3\xa7\xc3\xb5es de restri\xc3\xa7\xc3\xa3o) que s\xc3\xa3o necess\xc3\xa1rias para que seja poss\xc3\xadvel definir a dire\xc3\xa7\xc3\xa3o para uma solu\xc3\xa7\xc3\xa3o \xc3\xb3tima. Uma solu\xc3\xa7\xc3\xa3o \xc3\xb3tima \xc3\xa9 aquela que \xc3\xa9 um \xc3\xb3timo local, mas possivelmente n\xc3\xa3o \xc3\xa9 um \xc3\xb3timo global.\n_START_SECTION_\nO princ\xc3\xadpio Lagrangeano forte: dualidade de Lagrange\n_START_PARAGRAPH_\nDado um problema de programa\xc3\xa7\xc3\xa3o n\xc3\xa3o linear na forma padr\xc3\xa3o_NEWLINE_        _NEWLINE_       \xe2\x89\xa40, \xe2\x88\x88 {}_NEWLINE_\xe2\x88\x88 {}_NEWLINE_com o dom\xc3\xadnio  tendo interior n\xc3\xa3o vazio, a fun\xc3\xa7\xc3\xa3o Lagrangiana _NEWLINE_Os vetores  e  s\xc3\xa3o chamados de vari\xc3\xa1veis dual ou vetores multiplicadores de Lagrange associados ao problema. A fun\xc3\xa7\xc3\xa3o dual de Lagrange \xc2\xa0\xc3\xa9 definida como_NEWLINE_A fun\xc3\xa7\xc3\xa3o dual g \xc3\xa9 c\xc3\xb4ncava, mesmo quando o problema inicial n\xc3\xa3o \xc3\xa9 convexo, porque \xc3\xa9 um ponto m\xc3\xadnimo de fun\xc3\xa7\xc3\xb5es afins. A fun\xc3\xa7\xc3\xa3o dupla produz limites inferiores no valor ideal do problema inicial; para qualquer \xc2\xa0e qualquer \xc2\xa0temos ._NEWLINE_Se uma qualifica\xc3\xa7\xc3\xa3o de restri\xc3\xa7\xc3\xa3o, como a condi\xc3\xa7\xc3\xa3o de Slater, e o problema original \xc3\xa9 convexo, ent\xc3\xa3o temos uma forte dualidade, ou seja,_NEWLINE_.\n_START_SECTION_\nProblemas convexos\n_START_PARAGRAPH_\nPara um problema de minimiza\xc3\xa7\xc3\xa3o convexa com restri\xc3\xa7\xc3\xb5es de desigualdade,_NEWLINE_       _NEWLINE_         _NEWLINE_o problema Lagrangiano dual \xc3\xa9_NEWLINE_       _NEWLINE_         _NEWLINE_onde a fun\xc3\xa7\xc3\xa3o objetivo \xc3\xa9 a fun\xc3\xa7\xc3\xa3o Lagrange dual. Desde que as fun\xc3\xa7\xc3\xb5es \xc2\xa0e \xc2\xa0s\xc3\xa3o continuamente diferenci\xc3\xa1veis, o \xc3\xadnfimo ocorre onde o gradiente \xc3\xa9 igual a zero. O problema _NEWLINE_       _NEWLINE_        _NEWLINE_  _NEWLINE_\xc3\xa9 chamado o problema dual de Wolfe. Este problema pode ser dif\xc3\xadcil de lidar computacionalmente, porque a fun\xc3\xa7\xc3\xa3o objetivo n\xc3\xa3o \xc3\xa9 c\xc3\xb4ncava nas vari\xc3\xa1veis \xe2\x80\x8b\xe2\x80\x8bconjuntas . Al\xc3\xa9m disso, a restri\xc3\xa7\xc3\xa3o de igualdade \xc3\xa9 n\xc3\xa3o-linear em geral, ent\xc3\xa3o o problema dual de Wolfe \xc3\xa9 tipicamente um problema de otimiza\xc3\xa7\xc3\xa3o n\xc3\xa3o-convexo. Em todo caso, a dualidade fraca se mant\xc3\xa9m.\n_START_SECTION_\nHist\xc3\xb3ria\n_START_PARAGRAPH_\nDe acordo com George Dantzig, o teorema da dualidade para otimiza\xc3\xa7\xc3\xa3o linear foi conjecturado por John von Neumann, imediatamente ap\xc3\xb3s Dantzig apresentar o problema de programa\xc3\xa7\xc3\xa3o linear. Von Neumann notou que ele estava usando informa\xc3\xa7\xc3\xb5es de sua teoria dos jogos e conjeturou que o jogo de duas pessoas com soma zero era equivalente a programa\xc3\xa7\xc3\xa3o linear. Provas rigorosas foram publicadas pela primeira vez em 1948 por Albert W. Tucker e seu grupo. (Pref\xc3\xa1cio de Dantzig para Nering e Tucker, 1993)'