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 (por vezes denominados condições necessárias de primeira ordem) para que uma solução em programação não linear seja ótima, desde que determinadas condições de regularidade sejam satisfeitas.
Ao admitir restrições de desigualdade, a abordagem de KKT na programação não linear generaliza o método clássico dos multiplicadores de Lagrange, que contempla apenas restrições de igualdade. De modo análogo ao método de Lagrange, o problema de maximização (ou minimização) com restrições é reescrito por meio de uma função lagrangiana cujo ponto ótimo é um ponto de sela — correspondendo a um máximo (ou mínimo) global sobre o domínio das variáveis de escolha e a um mínimo (ou máximo) global sobre os multiplicadores. O teorema de Karush–Kuhn–Tucker é frequentemente denominado teorema do ponto de sela.
As condições KKT foram originalmente nomeadas em homenagem a Harold W. Kuhn e Albert W. Tucker, que publicaram essas condições pela primeira vez em 1951. Posteriormente, historiadores e matemáticos constataram que as condições necessárias para esse problema haviam sido formuladas na dissertação de mestrado (não publicada na época) de William Karush em 1939.
Problema de otimização não linear
Considere o seguinte problema de otimização não linear expresso na forma padrão:
minimizar sujeito a
onde é a variável de otimização pertencente a um conjunto convexo de , é a função objetivo (ou função utilidade), são as funções de restrição de desigualdade e são as funções de restrição de igualdade. A quantidade de desigualdades e igualdades é indicada por e , respectivamente. Associada a esse problema de otimização com restrições, define-se a função lagrangiana:
onde
O teorema de Karush–Kuhn–Tucker estabelece o seguinte:
Como a ideia central desse método consiste em encontrar um hiperplano de suporte sobre o conjunto viável , a demonstração do teorema de Karush–Kuhn–Tucker baseia-se diretamente no teorema da separação do hiperplano.
O sistema de equações e inequações correspondente às condições KKT geralmente não é resolvido de forma analítica direta, exceto em casos particulares nos quais uma solução em forma fechada pode ser derivada simbolicamente. Na prática, diversos algoritmos computacionais de otimização são estruturados como métodos de análise numérica projetados para convergir a soluções do sistema KKT.
Condições necessárias
Suponha que a função objetivo e as funções de restrição e admitam subgradientes em um ponto . Se for um ótimo local e o problema de otimização satisfizer condições de regularidade (ver abaixo), então existem constantes e , denominadas multiplicadores KKT, tais que os quatro grupos de condições a seguir são satisfeitos:
thumb|upright=2|Diagrama de restrições de desigualdade em problemas de otimização.
Estacionariedade Para a minimização de : Para a maximização de :
Viabilidade primal
Viabilidade dual
Folga complementar
A última condição é frequentemente expressa na forma equivalente: , para todo .
No caso particular em que , isto é, na ausência de restrições de desigualdade, as condições KKT reduzem-se exatamente às condições de Lagrange, e os multiplicadores KKT coincidem com os multiplicadores de Lagrange.
Interpretação: condições KKT como forças de restrição de equilíbrio no espaço de estados O problema primal pode ser interpretado fisicamente como o deslocamento de uma partícula no espaço de coordenadas , submetida a três naturezas distintas de campos de força:
atua como um campo potencial que a partícula busca minimizar. A força gerada por é dada por . definem superfícies de restrição unilaterais. A partícula tem liberdade para se mover na região interior ; contudo, ao atingir a fronteira , sofre uma força de repulsão direcionada para o interior do conjunto viável. definem superfícies de restrição bilaterais. A partícula é compelida a se mover estritamente sobre a superfície hipersuperficial determinada por .
A condição de estacionariedade primal expressa que a "força" motriz é equilibrada com exatidão pela combinação linear das forças de restrição e .
A viabilidade dual estabelece, adicionalmente, que todas as forças associadas a devem atuar de maneira unilateral, apontando exclusivamente para o interior da região viável de .
A folga complementar estabelece que, se , a força associada a deve ser necessariamente nula, ou seja, ; como a partícula se encontra estritamente no interior do conjunto e não em sua fronteira, a força de restrição unilateral correspondente não entra em ação.
Representação matricial
As condições necessárias podem ser compactadas matricialmente por meio das matrizes jacobianas das funções de restrição. Sejam as funções vetoriais dada por e dada por . Definindo e , as condições necessárias podem ser expressas como:
Estacionariedade Para a maximização de : Para a minimização de :
Viabilidade primal
Viabilidade dual
Folga complementar
Condições de regularidade (ou qualificações de restrições) Coloca-se a questão de se um ponto de mínimo do problema de otimização com restrições original (assumindo sua existência) satisfaz obrigatoriamente as condições KKT apresentadas. Essa indagação assemelha-se à identificação das hipóteses sob as quais um minimizador de uma função em otimização irrestrita satisfaz a condição . No caso restrito, a análise requer critérios estruturais adicionais sobre as restrições, expressos por meio de condições de "regularidade" (ou qualificações de restrições). As condições mais empregadas na literatura estão sintetizadas na tabela a seguir, destacando-se a LICQ como a mais recorrente:
Restrição Sigla Enunciado Qualificação de restrições de linearidade (Linearity constraint qualification) LCQ Se todas as funções e forem funções afins, nenhuma condição adicional é requerida. Qualificação de restrições de independência linear (Linear independence constraint qualification) LICQ Os gradientes das restrições ativas de desigualdade e os gradientes das restrições de igualdade são linearmente independentes em . Qualificação de restrições de Mangasarian–Fromovitz (Mangasarian–Fromovitz constraint qualification) MFCQ Os gradientes das restrições de igualdade são linearmente independentes em e existe um vetor tal que para todas as restrições ativas de desigualdade e para todas as restrições de igualdade. Qualificação de restrições de posto constante (Constant rank constraint qualification) CRCQ Para cada subconjunto dos gradientes das restrições ativas de desigualdade e dos gradientes das restrições de igualdade, o posto da matriz correspondente permanece constante em uma vizinhança de . Qualificação de restrições de dependência linear positiva constante (Constant positive linear dependence constraint qualification) CPLD Para cada subconjunto de gradientes de restrições ativas de desigualdade e gradientes de igualdade, se o conjunto de vetores for linearmente dependente em com 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ções de quase-normalidade (Quasi-normality constraint qualification) QNCQ Se os gradientes das restrições ativas de desigualdade e das restrições de igualdade forem linearmente dependentes em com multiplicadores associados para igualdades e para desigualdades, então não existe sequência tal que e . Condição de Slater (Slater's condition) SC Para um problema convexo (no caso de minimização, e são convexas e são afins), existe um ponto viável tal que e para todo .
Verificam-se as seguintes cadeias estritas de implicação:
e
Na prática computacional, qualificações de restrições mais brandas são preferíveis, visto que ampliam a classe de problemas aos quais as condições necessárias se aplicam.
Condições suficientes
Em determinados problemas, as condições necessárias tornam-se igualmente suficientes para a otimização global. Em linhas gerais, contudo, as condições necessárias de primeira ordem não garantem por si sós a otimalidade, exigindo critérios complementares, a exemplo das condições suficientes de segunda ordem (SOSC, do inglês Second Order Sufficient Conditions). Em funções diferenciáveis suaves, as SOSC envolvem a matriz hessiana de segundas derivadas.
As condições necessárias KKT são suficientes para a otimalidade global 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 satisfeita. De maneira recíproca, se a função objetivo de um problema de minimização for uma função convexa diferenciável sob as mesmas hipóteses para as restrições, as condições KKT constituem critérios suficientes de otimalidade.
Martin demonstrou em 1985 que a classe mais abrangente de funções para as quais as condições KKT asseguram otimalidade global coincide com as denominadas funções invexas do Tipo 1.
Condições suficientes de segunda ordem
Para problemas de programação não linear suaves, a condição suficiente de segunda ordem é formulada da seguinte forma:
O ponto obtido pelas condições de primeira ordem configura um mínimo local restrito se a função lagrangiana,
satisfizer:
para todo vetor não nulo que atenda a:
onde são consideradas apenas as restrições ativas de desigualdade associadas à complementaridade estrita (isto é, nas quais ). A solução corresponderá a um mínimo local estrito se a desigualdade quadrática acima for estrita para todo .
Caso , termos de terceira ordem da expansão de Taylor do lagrangiano devem ser avaliados para atestar se constitui um mínimo local. A minimização da função fornece um contraexemplo clássico para essa condição (ver também superfície de Peano).
Economia
Na economia matemática, o método KKT é amplamente empregado na derivação de modelos teóricos para a obtenção de resultados qualitativos de equilíbrio. Como exemplo,Alpha C. Chiang, Fundamental Methods of Mathematical Economics, 3.ª edição, 1984, pp. 750–752. considere uma empresa que maximiza sua receita de vendas sujeita a uma restrição de lucro operacional mínimo aceitável. Definindo como a quantidade produzida (variável de escolha), como a receita de vendas (com primeira derivada estritamente positiva e valor nulo para produção zero), como os custos de produção (com primeira derivada estritamente positiva e valor não negativo para produção zero) e como o nível mínimo de lucro exigido, o problema possui formulação econômica significativa se a curva de receita estabilizar-se de tal forma que sua inclinação torne-se inferior à curva de custo marginal para valores elevados de produção. O problema na forma padrão de minimização escreve-se como:
Minimizar sujeito a
e as condições KKT assumem a forma:
Como o nível de produção violaria a restrição de lucro mínimo, deduz-se que ; assim, a terceira condição impõe que a primeira desigualdade seja satisfeita com igualdade estrita. Isolando a derivada da receita, obtém-se:
Sendo e por hipótese, essa igualdade combinada à não negatividade de assegura que o multiplicador é estritamente positivo. Como o fator , conclui-se que a firma maximizadora de receitas opera em um nível de produto no qual a receita marginal é estritamente inferior ao custo marginal — resultado que contrasta com o comportamento da empresa sob maximização de lucros irrestrita, na qual a receita marginal iguala o custo marginal.
Função de valor Reescrevendo o problema de otimização como uma maximização parametrizada por constantes nas restrições de desigualdade:
Maximizar sujeito a
A função de valor é definida por:
sujeito a
cujo domínio corresponde a .