§ 2.10. Методы возможных направлений

В предыдущих параграфах были рассмотрены алгоритмы, позволяющие определять минимальное значение вектора  при наличии дополнительных ограничений в виде равенств и неравенств. В этих методах, основанных на решении соответствующей задачи Лагранжа, наряду с оптимальным значением вектора  определялась и оптимальная величина множителя Лагранжа . Можно непосредственно использовать для решения задач на условный экстремум идею движения вдоль градиента. Эти методы получили название методов возможных направлений.

Суть этих методов состоит в следующем.

Выбирается произвольная точка , удовлетворяющая ограничениям (1.14). В этой точке определяется такое направление , двигаясь вдоль которого можно сделать шаг конечной длины  и уменьшить значение функционала, не выходя при этом за пределы допустимого множества.

Затем определяется длина шага  и, следовательно, новое значение вектора :

.                              (2.32)

Значение функционала в новой точке  должно быть меньше, чем в предыдущей:

.                                             (2.33)

Таким образом, на каждом шаге задача определения нового значения вектора состоит из двух этапов: выбора направления и выбора длины шага при движении по этому направлению.

Для того чтобы неравенство (2.33) выполнялось, вектор  должен составлять с градиентом функционала в этой точке острый угол, т. е.

.                                    (2.34)

Направление, удовлетворяющее неравенству (2.34), получило название возможного. Отсюда и название всех методов такого рода.

Величина шага  определяется так же, как и в методе наискорейшего спуска, т. е.

.                   (2.35)

При этом, конечно, не должны нарушаться ограничения (1.14).

Для частных задач методы возможных направлений могут обеспечить нахождение экстремума за конечное число шагов.

Нужно отметить, что многие эффективные алгоритмы математического программирования (например, симплекс- метод в линейном программировании) можно трактовать как специальные случаи методов возможных направлений.