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

Метод проекции градиенты.

Этот метод является обобщением градиентного метода. Так как возможен выход за пределы допустимого множества, то вводится операция проектирования на X (поиск ближайшей точки на X).

x^k+1= p_x (x^k- gÑf(x^k)), где p_x проекция на X.

Пример:

Если X- круг, то проекция точки на X есть точка пересечения окружности и прямой, соединяющей центр и проектирующую точку. Чем сложнее область X, тем сложнее операция проектирования.

Метод обладает теми же свойствами, что и градиентный метод с постоянным шагом.

Движение в направлении -Ñf(x⁰), находим минимум по этому направлению (). Произвольно выбираем x¹ и вновь движение в соответствующем градиентном направлении и так далее.

В очередной точке x^k линеаризуют функцию f(x) (в этом «условность» метода, то есть линеаризация и есть «условие» в названии). Затем решают задачу min линейной функции на X и найденную точку используют для выбора направления движения.

При этом предполагается:

1. Задача мин. линейной функции на X имеет решение.

2. Это решение может быть найдено достаточно просто, лучше всего в явной форме.

3. Нужно указать правило выбора g_k. Можно g_k определить из условия наискорейшего спуска:

При определенных условиях: f(x*)- f* = o(1/k), где f* = min f(x) на X.