Введение
Концепция математической оптимизации В математической оптимизации условия Каруша-Кун-Таккера (KKT), также известные как условия Куна-Таккера, являются первыми производными тестами (иногда называемыми необходимыми условиями первого порядка) для решения в нелинейном программировании, чтобы быть оптимальными, при условии, что некоторые условия регулярности удовлетворены. Допуская неравенство ограничений, подход KKT к нелинейному программированию обобщает метод множителей Лагранжа, который допускает только ограничения равенства. Подобно подходу Лагранжа, задача ограниченного максимизации (минимизации) переписывается как функция Лагранжа, оптимальная точка которой является глобальным максимумом или минимумом над доменом переменных выбора и глобальным минимумом (максимумом) над множителями. Теорему Каруша-Кун-Такера иногда называют теоремой седловой точки. Условия KKT были первоначально названы в честь Гарольда В. Куна и Альберта В. Таккера, которые впервые опубликовали условия в 1951 году. Позже ученые обнаружили, что необходимые условия для этой проблемы были изложены Уильямом Карушем в его магистерской диссертации в 1939 году.
In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests (sometimes called first order necessary conditions) for a solution in nonlinear programming to be optimal, provided that some regularity conditions are satisfied. Allowing inequality constraints, the KKT approach to nonlinear programming generalizes the method of Lagrange multipliers, which allows only equality constraints. Similar to the Lagrange approach, the constrained maximization (minimization) problem is rewritten as a Lagrange function whose optimal point is a global maximum or minimum over the domain of the choice variables and a global minimum (maximum) over the multipliers. The Karush–Kuhn–Tucker theorem is sometimes referred to as the saddle point theorem. The KKT conditions were originally named after Harold W. Kuhn and Albert W. Tucker, who first published the conditions in 1951. Later scholars discovered that the necessary conditions for this problem had been stated by William Karush in his master's thesis in 1939.
Достаточные условия
В некоторых случаях необходимые условия также достаточны для оптимальности. В целом, необходимые условия не являются достаточными для достижения оптимальности, и требуется дополнительная информация, такая как условия достаточного уровня второго порядка (SOSC). Для плавных функций SOSC включают в себя вторую производную, что объясняет его название. Необходимых условий достаточно для оптимальности, если объективная функция проблемы максимизации является дифференцируемой комодной функцией, ограничения неравенства являются дифференцируемыми выпуклыми функциями, ограничения равенства являются аффинными функциями, и условие Слейтера имеет значение. Аналогичным образом, если объективная функция задачи минимизации является дифференцируемой выпуклой функцией, необходимых условий также достаточно для оптимальности. Мартин в 1985 году показал, что более широкий класс функций, в которых условия KKT гарантируют глобальную оптимальность, являются так называемыми функциями инвекса типа 1.