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

Построение возможных направлений спуска

Пусть задана текущая допустимая точка x. Как показано в лемме 2, ненулевой вектор  будет возможным направлением спуска, если . Естественный подход к построению такого направления заключается в минимизации линейной по S функции  при условиях: . Однако, если существует такой вектор S*, что , и выполняются условия а) и б), то оптимальное значение целевой функции сформулированной задачи равно -  , так как ограничениям этой задачи удовлетворяет любой вектор S*, где  - любое большое число.
Следовательно, в задачу должно быть включено условие, которое бы ограничивало вектор S,. Такое ограничение называют нормирующим. Возможны различные формы нормирующего ограничения. Ниже приведены три задачи отыскания (наилучшего) направления спуска, в каждой из которых используются различные условия нормировки.
Задача P₁: минимизировать
при условиях
 
Задача P₂: минимизировать при условиях:

Задача P₃: минимизировать при условиях:

Задачи P₁ и P₃ являются задачами ЛП и, следовательно, их можно решить симплекс-методом.
Так как S=0 является допустимой точкой в каждой из приведенных выше задач, а значение целевой функции в этой точке равно 0, то ее оптимальное значение в задачах P₁, P₂, P₃ не может быть положительным. Если минимальное значение целевой функции в задачах, P₁, P₂, P₃ отрицательно, то по лемме 2 нами построено возможное направление спуска. С другой стороны, если минимальное значение целевой функции равно нулю, то, как будет показано ниже, точка x является точкой Куна-Таккера.