Condições de Karush-Kuhn-Tucker (KKT) em Otimização

Anotacoes

Gisele Tessari Santos, D.Sc. Aula 15 – Otimização Restrita – As condições de Karush-Kuhn-Tucker (KKT) Introdução Como reconhecer uma solução ótima para um problema de programação não linear (com funções diferenciáveis)? Quais são as condições necessárias e (talvez) suficientes que uma solução destas tem de satisfazer? Condições de Karush-Kuhn-Tucker (KKT) Teorema. Suponha que f(x), g 1 (x), g 2 (x), ..., g m (x) sejam funções diferenciáveis que satisfazem certas condições de regularidade. Então: pode ser uma solução ótima para o problema de programação não linear somente se existirem m números u 1 , u 2 , ..., u m tais que todas as condições KKT a seguir sejam satisfeitas: Condição 1: em x = x*, para j = 1, 2, ..., n. • u i surgem na derivação matemática como multiplicadores de Lagrange! Condição 2: • Garantem a viabilidade da solução! Condições 3 e 4: • g i (x*) - b i ≤ 0, para i = 1, 2, ..., m • u i [g i (x*) - b i ] = 0, para i = 1, 2, ..., m. • Para serem iguais a zero → pelo menos um dos termos de cada equação deve ser zero! Condições 5 e 6: • x j * ≥ 0, para j = 1, 2, ..., n. • u i ≥ 0, para i = 1, 2, ..., m. Condições de Karush-Kuhn-Tucker (KKT) Portanto, a condição 4 pode s...