Метод условного градиента

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

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

Сформулируем вспомогательную задачу

. (1)

Легко увидеть, что при сделанных выше предположениях задача (1) имеет решение, обозначим его . Далее, положим .

Если , то согласно определению точки имеем . Таким образом, в точке выполняется необходимое условие условного минимума функции на множестве . Если, кроме того, функция – выпуклая на множестве , то это условие также и достаточно ([1], 2.6, теорема 5).

Будем считать, что Это означает, что процесс построения последовательности приближений бесконечен, ни одна точка не является точкой условного минимума. Тогда является условно релаксационным направлением для функции в точке относительно множества , значит, можно сделать положительный шаг в этом направлении, не нарушив ограничений и уменьшив значение функции. Например, такой шаговый множитель можно определить следующим образом: и найти следующее приближение .

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