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

 

Градиент обобщенного лагранжиана равен нулю.
 

Все ограничения на 
x
и на множители ККТ удовлетворяются.
 

Ограничения типа неравенств обладают свойством «дополняющей нежестко-
сти»: 
α
⊙
h
(
x
) = 
0
.
Дополнительные сведения о методе ККТ см. в работе Nocedal and Wright (2006).
4.5. Пример: линейный метод 
наименьших квадратов
Требуется найти значение 
x
, минимизирующее функцию
f
(
x
) = 
1
/
2
||
Ax
– 
b
||
2
2
. 
(4.21)
В линейной алгебре рассматриваются специализированные алгоритмы для эффек-
тивного решения этой задачи, но мы покажем, как решить ее методами градиентной 
оптимизации.
Сначала получим выражение для градиента:
∇
x
f
(
x
) = 
A
⏉
(
Ax
– 
b
) = 
A
⏉
Ax
– 
A
⏉
b
.
 
(4.22)
Затем будем небольшими шагами спускаться вдоль направления градиента. Дета-
ли описаны в алгоритме 4.1.
Алгоритм 4.1. 
Алгоритм минимизации 
f
(
x
) = 
1
/
2
||
Ax
– 
b
||
2
2
относительно 
x
методом 
градиентного спуска, начиная с произвольного значения 
x
Взять в качестве величины шага (
ε
) и допуска (
δ
) небольшие положительные 
числа.