Condições Karush – Kuhn – Tucker

Na otimização matemática , as condições de Karush–Kuhn–Tucker ( KKT ) , também conhecidas como condições de Kuhn–Tucker , são testes de primeira derivada (às vezes chamadas de condições necessárias de primeira ordem ) para que uma solução em programação não linear seja ótima , desde que alguns as condições de regularidade são satisfeitas.

Permitindo restrições de desigualdade, a abordagem KKT para programação não linear generaliza o método dos multiplicadores de Lagrange , que permite apenas restrições de igualdade. Semelhante à abordagem de Lagrange, o problema de maximização (minimização) restrita é reescrito como uma função de Lagrange cujo ponto ótimo é um máximo ou mínimo global sobre o domínio das variáveis ​​de escolha e um mínimo (máximo) global sobre os multiplicadores. O teorema de Karush-Kuhn-Tucker é às vezes referido como teorema do ponto de sela. [1]

As condições KKT foram originalmente nomeadas em homenagem a Harold W. Kuhn e Albert W. Tucker , que publicaram as condições pela primeira vez em 1951. [2] Estudiosos posteriores descobriram que as condições necessárias para este problema foram declaradas por William Karush em sua tese de mestrado em 1939. [ 3] [4]

Problema de otimização não linear

Considere o seguinte problema de otimização não linear na forma padrão :

minimizar
sujeito a

onde é a variável de otimização escolhida de um subconjunto convexo de , é a função objetivo ou utilidade , são as funções de restrição de desigualdade e são as funções de restrição de igualdade. Os números de desigualdades e igualdades são denotados por e respectivamente. Correspondendo ao problema de otimização restrita pode-se formar a função Lagrangiana

onde

O teorema de Karush – Kuhn – Tucker afirma o seguinte.

Teorema  -  (suficiência) Se for um ponto de sela em , então é um vetor ideal para o problema de otimização acima .

(necessidade) Suponha que e ,,, sejam convexos e que exista tal que (isto é, a condição de Slater seja válida). Então, com um vetor ótimo para o problema de otimização acima, está associado um vetor que satisfaz tal que é um ponto de sela de . [5]

Como a ideia desta abordagem é encontrar um hiperplano de suporte no conjunto viável , a prova do teorema de Karush-Kuhn-Tucker faz uso do teorema da separação de hiperplanos . [6]

O sistema de equações e desigualdades correspondentes às condições KKT geralmente não é resolvido diretamente, exceto nos poucos casos especiais em que uma solução de forma fechada pode ser derivada analiticamente. Em geral, muitos algoritmos de otimização podem ser interpretados como métodos para resolver numericamente o sistema de equações e desigualdades KKT. [7]

Condições necessárias

Suponha que a função objetivo e a restrição funcionem e tenham subderivadas em um ponto . Se é um ótimo local e o problema de otimização satisfaz algumas condições de regularidade (veja abaixo), então existem constantes e , chamadas multiplicadores KKT, tais que os seguintes quatro grupos de condições são válidos: [8]

Diagrama de restrições de desigualdade para problemas de otimização
Estacionaridade
Para minimizar :
Para maximizar :
Viabilidade primária
Viabilidade dupla
Frouxidão complementar

A última condição às vezes é escrita na forma equivalente:

No caso particular , ou seja, quando não há restrições de desigualdade, as condições KKT transformam-se em condições de Lagrange, e os multiplicadores KKT são chamados de multiplicadores de Lagrange .

Prova

Teorema  -  (suficiência) Se existe uma solução para o problema primal, uma solução para o problema dual, tal que juntos eles satisfaçam as condições KKT, então o par de problemas tem dualidade forte e é um par de soluções para os problemas primal e dual .

(necessidade) Se o par problemático tiver dualidade forte, então para qualquer solução do problema primal e qualquer solução do problema dual, o par deve satisfazer as condições KKT. [9]

Prova

Primeiro, satisfazer as condições KKT é equivalente a elas serem um equilíbrio de Nash .

Fixe e varie : o equilíbrio é equivalente à estacionariedade primal.

Fixar e variar : o equilíbrio é equivalente à viabilidade primal e à negligência complementar.

Suficiência: o par de soluções satisfaz as condições KKT, portanto é um equilíbrio de Nash e, portanto, fecha a lacuna de dualidade.

Necessidade: qualquer par de soluções deve fechar a lacuna de dualidade, portanto, deve constituir um equilíbrio de Nash (já que nenhum dos lados poderia fazer melhor), portanto, satisfaz as condições KKT.

Interpretação: Condições KKT como equilíbrio de forças de restrição no espaço de estados

O problema primordial pode ser interpretado como mover uma partícula no espaço de e submetê-la a três tipos de campos de força:

  • é um campo potencial que a partícula está minimizando. A força gerada por é .
  • são superfícies de restrição unilaterais. A partícula pode se mover para dentro , mas sempre que toca , é empurrada para dentro.
  • são superfícies de restrição de dois lados. A partícula só pode se mover na superfície .

A estacionariedade primal afirma que a "força" de é exatamente equilibrada por uma soma linear de forças e .

A viabilidade dupla afirma adicionalmente que todas as forças devem ser unilaterais, apontando para dentro do conjunto viável para .

A frouxidão dupla afirma que se , então a força deve ser zero, uma vez que a partícula não está no limite, a força de restrição unilateral não pode ser ativada.

Representação matricial

As condições necessárias podem ser escritas com matrizes Jacobianas das funções de restrição. Seja definido como e seja definido como . Deixe e . Então as condições necessárias podem ser escritas como:

Estacionaridade
Para maximizar :
Para minimizar :
Viabilidade primária
Viabilidade dupla
Frouxidão complementar

Condições de regularidade (ou qualificações de restrição)

Pode-se perguntar se um ponto minimizador do problema de otimização original e restrito (assumindo que exista) deve satisfazer as condições KKT acima. Isto é semelhante a perguntar sob quais condições o minimizador de uma função em um problema irrestrito deve satisfazer a condição . Para o caso restrito, a situação é mais complicada, e pode-se afirmar uma variedade de condições de "regularidade" (cada vez mais complicadas) sob as quais um minimizador restrito também satisfaz as condições KKT. Alguns exemplos comuns de condições que garantem isso são tabulados a seguir, sendo o LICQ o mais utilizado:

Limitação Acrônimo Declaração
Qualificação de restrição de linearidade LCDQ Se e são funções afins , nenhuma outra condição é necessária.
Qualificação de restrição de independência linear LICQ Os gradientes das restrições de desigualdade ativas e os gradientes das restrições de igualdade são linearmente independentes em .
Qualificação de restrição Mangasarian-Fromovitz MFCQ Os gradientes das restrições de igualdade são linearmente independentes e existe um vetor tal que para todas as restrições de desigualdade ativas e para todas as restrições de igualdade. [10]
Qualificação de restrição de classificação constante CRCQ Para cada subconjunto dos gradientes das restrições de desigualdade ativas e dos gradientes das restrições de igualdade, a classificação na vizinhança de é constante.
Qualificação de restrição de dependência linear positiva constante CPLD Para cada subconjunto de gradientes de restrições de desigualdade ativas e gradientes de restrições de igualdade, se o subconjunto de vetores for linearmente dependente de escalares não negativos associados às restrições de desigualdade, então ele permanece linearmente dependente em uma vizinhança de .
Qualificação de restrição de quase normalidade QNCQ Se os gradientes das restrições de desigualdade ativas e os gradientes das restrições de igualdade são linearmente dependentes de multiplicadores associados para igualdades e para desigualdades, então não há sequência tal que e
A condição de Slater SC Para um problema convexo (ou seja, assumindo minimização, são convexos e afins), existe um ponto tal que e

As implicações estritas podem ser mostradas

LICQ ⇒ MFCQ ⇒ CPLD ⇒ QNCQ

e

LICQ ⇒ CRCQ ⇒ CPLD ⇒ QNCQ

Na prática, são preferidas qualificações de restrições mais fracas, uma vez que se aplicam a uma seleção mais ampla de problemas.

Condições suficientes

Em alguns casos, as condições necessárias também são suficientes para a otimização. Em geral, as condições necessárias não são suficientes para a otimização e são necessárias informações adicionais, como as Condições Suficientes de Segunda Ordem (SOSC). Para funções suaves, SOSC envolve as segundas derivadas, o que explica seu nome.

As condições necessárias são suficientes para a otimalidade se a função objetivo de um problema de maximização for uma função côncava diferenciável , as restrições de desigualdade forem funções convexas diferenciáveis , as restrições de igualdade forem funções afins e a condição de Slater for válida. [11] Da mesma forma, se a função objetivo de um problema de minimização for uma função convexa diferenciável , as condições necessárias também são suficientes para a otimalidade.

Foi demonstrado por Martin em 1985 que a classe mais ampla de funções nas quais as condições KKT garantem a otimalidade global são as chamadas funções invexas do Tipo 1 . [12] [13]

Condições suficientes de segunda ordem

Para problemas de otimização suaves e não lineares , uma condição suficiente de segunda ordem é dada como segue.

A solução encontrada na seção acima é um mínimo local restrito se para o Lagrangiano,

então,

onde é um vetor que satisfaz o seguinte,

onde apenas as restrições de desigualdade ativa correspondentes à complementaridade estrita (ou seja, onde ) são aplicadas. A solução é um mínimo local estritamente restrito caso a desigualdade também seja estrita.

Se , a expansão Taylor de terceira ordem do Lagrangiano deve ser usada para verificar se é um mínimo local. A minimização de é um bom contra-exemplo, veja também superfície de Peano .

Economia

Muitas vezes, na economia matemática, a abordagem KKT é utilizada em modelos teóricos para obter resultados qualitativos. Por exemplo, [14] considere uma empresa que maximiza a sua receita de vendas sujeita a uma restrição de lucro mínimo. Sejam a quantidade de produção produzida (a ser escolhida), sejam as receitas de vendas com primeira derivada positiva e com valor zero na produção zero, sejam os custos de produção com primeira derivada positiva e com valor não negativo na produção zero, e for o nível de lucro mínimo aceitável positivo , então o problema será significativo se a função de receita se estabilizar e, eventualmente, for menos acentuada do que a função de custo. O problema expresso na forma de minimização dada anteriormente é

Minimizar
sujeito a

e as condições KKT são

Como violaria a restrição de lucro mínimo, temos e, portanto, a terceira condição implica que a primeira condição é válida com igualdade. Resolver que a igualdade dá

Porque foi dado que e são estritamente positivos, esta desigualdade, juntamente com a condição de não negatividade nas garantias, é positiva e, portanto, a empresa que maximiza a receita opera num nível de produção em que a receita marginal é menor que o custo marginal - um resultado que é interessante porque contrasta com o comportamento de uma empresa que maximiza o lucro , que opera em um nível em que são iguais.

Função de valor

Se reconsiderarmos o problema de otimização como um problema de maximização com restrições de desigualdade constante:

A função de valor é definida como

então o domínio de é

Dada esta definição, cada coeficiente é a taxa na qual a função de valor aumenta à medida que aumenta. Assim, se cada um for interpretado como uma restrição de recursos, os coeficientes informam quanto o aumento de um recurso aumentará o valor ideal da nossa função . Esta interpretação é especialmente importante em economia e é utilizada, por exemplo, em problemas de maximização de utilidade .

Generalizações

Com um multiplicador extra , que pode ser zero (desde que ), na frente do KKT as condições de estacionariedade se transformam em

que são chamadas de condições de Fritz John . Estas condições de otimalidade são válidas sem qualificações de restrição e são equivalentes à condição de otimalidade KKT ou (não-MFCQ) .

As condições KKT pertencem a uma classe mais ampla de condições necessárias de primeira ordem (FONC), que permitem funções não suaves usando subderivadas .

Veja também

Referências

  1. ^ Tabak, Daniel; Kuo, Benjamin C. (1971). Controle Ótimo por Programação Matemática . Englewood Cliffs, NJ: Prentice-Hall. pp. 19–20. ISBN 0-13-638106-5.
  2. ^ Kuhn, HW ; Tucker, AW (1951). “Programação não linear”. Anais do 2º Simpósio de Berkeley . Berkeley: University of California Press. páginas 481–492. MR  0047303.
  3. ^ W. Karush (1939). Mínimos de funções de diversas variáveis ​​com desigualdades como restrições laterais (tese de mestrado). Departamento de Matemática, Univ. de Chicago, Chicago, Illinois.
  4. ^ Kjeldsen, Tinne Hoff (2000). "Uma análise histórica contextualizada do teorema de Kuhn-Tucker na programação não linear: o impacto da Segunda Guerra Mundial". História Matemática . 27 (4): 331–361. doi : 10.1006/hmat.2000.2289 . MR  1800317.
  5. ^ Walsh, GR (1975). "Propriedade do ponto de sela da função Lagrangiana". Métodos de Otimização . Nova York: John Wiley & Sons. págs. 39–44. ISBN 0-471-91922-5.
  6. ^ Kemp, Murray C.; Kimura, Yoshio (1978). Introdução à Economia Matemática. Nova York: Springer. págs. 38–44. ISBN 0-387-90304-6.
  7. ^ Boyd, Stephen; Vandenberghe, Lieven (2004). Otimização Convexa . Cambridge: Cambridge University Press . pág. 244. ISBN 0-521-83378-7. SENHOR  2061575.
  8. ^ Ruszczyński, Andrzej (2006). Otimização Não Linear . Princeton, NJ: Princeton University Press . ISBN  978-0691119151. MR  2199043.
  9. ^ Geoff Gordon e Ryan Tibshirani. "Condições Karush-Kuhn-Tucker, Otimização 10-725/36-725" (PDF) . Arquivado do original (PDF) em 17/06/2022.
  10. ^ Dimitri Bertsekas (1999). Programação Não Linear (2 ed.). Atenas Científica. págs. 329–330. ISBN 9781886529007.
  11. ^ Boyd, Stephen; Vandenberghe, Lieven (2004). Otimização Convexa . Cambridge: Cambridge University Press . pág. 244. ISBN 0-521-83378-7. SENHOR  2061575.
  12. ^ Martin, AO (1985). “A Essência da Invexidade”. J. Ótimo. Teoria Apl . 47 (1): 65–76. doi :10.1007/BF00941316. S2CID122906371  .
  13. ^ Hanson, miliampère (1999). "Invexidade e o Teorema de Kuhn-Tucker". J. Matemática. Anal. Apl . 236 (2): 594–604. doi : 10.1006/jmaa.1999.6484 .
  14. ^ Chiang, Alpha C. Métodos Fundamentais de Economia Matemática , 3ª edição, 1984, pp.

Leitura adicional

  • Andreani, R.; Martínez, JM; Schuverdt, M.L. (2005). “Sobre a relação entre condição de dependência linear positiva constante e qualificação de restrição de quasenormalidade”. Jornal de Teoria e Aplicações de Otimização . 125 (2): 473–485. doi :10.1007/s10957-004-1861-9. S2CID122212394  .
  • Avriel, Mordecai (2003). Programação Não Linear: Análise e Métodos . Dover. ISBN 0-486-43227-0.
  • Boltyanski, V.; Martini, H.; Soltan, V. (1998). "O Teorema de Kuhn-Tucker". Métodos Geométricos e Problemas de Otimização . Nova York: Springer. pp. 78–92. ISBN 0-7923-5454-0.
  • Boyd, S.; Vandenberghe, L. (2004). "Condições de otimização" (PDF) . Otimização Convexa . Cambridge University Press. páginas 241–249. ISBN 0-521-83378-7.
  • Kemp, Murray C.; Kimura, Yoshio (1978). Introdução à Economia Matemática. Nova York: Springer. págs. 38–73. ISBN 0-387-90304-6.
  • Rau, Nicholas (1981). "Multiplicadores de Lagrange". Matrizes e Programação Matemática . Londres: Macmillan. pp. 156–174. ISBN 0-333-27768-6.
  • Nocedal, J.; Wright, SJ (2006). Otimização Numérica . Nova York: Springer. ISBN 978-0-387-30303-1.
  • Sundaram, Rangarajan K. (1996). "Restrições de desigualdade e o teorema de Kuhn e Tucker". Um primeiro curso em teoria da otimização . Nova York: Cambridge University Press. páginas 145–171. ISBN 0-521-49770-1.

links externos

  • Condições de Karush – Kuhn – Tucker com derivação e exemplos
  • Exemplos e tutoriais sobre as condições KKT
Retrieved from "https://en.wikipedia.org/w/index.php?title=Karush–Kuhn–Tucker_conditions&oldid=1216669927"