Я. Гудфеллоу, И. Бенджио, А. Курвилль

Метод Каруша–Куна–Таккера
(ККТ)
1
предлагает очень общий подход к реше-
нию задач оптимизации. Вводится новая функция, называемая 
обобщенным лагран-
жианом
, или 
обобщенной функцией Лагранжа
.
1
Метод ККТ является обобщением метода 
множителей Лагранжа
, который допускает толь-
ко ограничения типа равенств.

---

Оптимизация с ограничениями 

93
Чтобы определить лагранжиан, мы сначала должны описать 
𝕊
с помощью равенств 
и неравенств, т. е. 
m
функций 
g
(
i
)
и 
n
функций 
h
(
j
)
– таких, что 
𝕊
= {
x
| 
∀
i
, 
g
(
i
)
(
x
) = 0
и 
∀
j
, 
h
(
j
)
(
x
) 
≤
0}. Условия, содержащие функции 
g
(
i
)
, называются 
ограничениями типа 
равенств
, а содержащие функции 
h
(
i
)
– 
ограничениями типа неравенств
.
Для каждого ограничения вводятся новые переменные 
λ
i
и 
α
j
, называемые множи-
телями ККТ. Обобщенный лагранжиан записывается в виде:
. 
(4.14)
Теперь задачу минимизации с ограничениями можно решить, подвергнув обоб-
щенный лагранжиан оптимизации без ограничений. Если существует хотя бы одна 
допустимая точка и 
f
(
x
) не может принимать значение 1, то
(4.15)
обладает такой же целевой функцией и множеством оптимальных точек 
x
, что и
(4.16)
Это следует из того, что если ограничения удовлетворяются, то
, 
(4.17)
а если некоторое ограничение нарушается, то
(4.18)
Эти свойства гарантируют, что никакая недопустимая точка не может быть опти-
мальной, а величина оптимума на множестве допустимых точек не изменяется.
Чтобы выполнить максимизацию с ограничениями, мы можем построить обоб-
щенный лагранжиан –
f
(
x
), который приводит к такой задаче оптимизации:
(4.19)
Можно также свести задачу к задаче максимизации во внешнем цикле:
(4.20)
Знак члена, содержащего ограничения типа равенств, не имеет значения; можно 
выбрать как плюс, так и минус, потому что алгоритм оптимизации волен выбирать 
любые знаки коэффициентов 
λ
i
.
Ограничения типа неравенств особенно интересны. Мы говорим, что ограничение 
h
(
i
)
(