Прямые методы условной оптимизации

Лемма 3. Рассмотрим задачу минимизации  при условиях . Пусть x - допустимая точка, в которой , где . Вектор x является точкой Куна-Таккера тогда и только тогда, когда оптимальное значение целевой функции в задачах, P₁, P₂, P₃ равно нулю.
Доказательство. Как следует из теоремы Куна-Таккера, x будет точкой Куна-Таккера тогда и только тогда, когда существуют векторы  такие, что
 . (13)
Согласно следствию из леммы Фаркаша система (13) разрешима тогда и только тогда, когда система неравенств  не имеет решений, т.е. когда оптимальное значение целевой функции в задачах, P₁, P₂, P₃ равно нулю.
Итак, мы показали, как найти возможное направление спуска.
Пусть теперь  - текущая точка;  - возможное направление спуска. В качестве следующей точки  выбирается , где длина шага  определяется из решения следующей задачи одномерной оптимизации:
Минимизировать  по (14)
при условиях , (15)
. (16)
Предположим, что . Тогда задачу (14)-(16) можно упростить следующим образом. Заметим, что . Значит, ограничение (16) излишне. Так как , то  для всех . Итак, остается только одно ограничение , и задача оптимизации (14)-(16) приводится к следующей задаче одномерной оптимизации:
минимизировать  по (17)
где  , (18)
(19)
 . (20)