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

Существо метода условного градиента состоит в том, что, если известна некоторая точка x^kÎD, то направление возрастания целевой функции может задаваться некоторой внутренней или крайней точкой xÎD, которая ищется в области D в направлении, задаваемом градиентом Ñf(x). Действительно, пусть h_k=1,тогда

x = x^k + r(x^k), или отсюда r(x^k) = x - x^k.

С другой стороны из определения (2.2) дифференцируемости функции в точке x^k

f(x) = f(x^k) + Ñ^тf(x^k)(x - x^k) + o(║x - x^k║)

или

f(x) - f(x^k) > Ñ^тf(x^k)(x - x^k).

Отсюда приращение целевой функции f(x^k_*) - f(x^k) при переходе к следующей точке x^k_* можно максимизировать на основе специального выбора точки, производимого в результате решения следующей задачи

x^k_* = arg max Ñ^тf(x^k)(x - x^k), (7)

xÎD

Таким образом, x^k_* задает направление максимального приращения целевой функции из точки x^k.

Если x^k_* - граничная точка D, то следующую точку, точку x^k+1 целесообразно искать на отрезке, соединяющем x^k и x^k_*, т.е.

x^k+1 = h_k x^k_* + (1-h_k) x^k, где 0 ≤ h_k ≤ 1,

или

x^k+1 = x^k + h_k (x^k_* - x^k) = x^k + h_k r(x^k), где 0 ≤ h_k ≤ 1.

Величину шага h_k следует выбирать из условия максимизации значения целевой функции в точке x^k+1, т.е.

h_k = m a x f(x^k+h(x^k_* - x^k)) (8)

0≤h≤1

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

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