Метод условного градиента.
Метод проекции градиенты.
Этот метод является обобщением градиентного метода. Так как возможен выход за пределы допустимого множества, то вводится операция проектирования на X (поиск ближайшей точки на X).
xk+1= px (xk- gÑf(xk)), где px проекция на X.
Пример:
Если X- круг, то проекция точки на X есть точка пересечения окружности и прямой, соединяющей центр и проектирующую точку. Чем сложнее область X, тем сложнее операция проектирования.
Метод обладает теми же свойствами, что и градиентный метод с постоянным шагом.
Движение в направлении -Ñf(x0), находим минимум по этому направлению (). Произвольно выбираем x1 и вновь движение в соответствующем градиентном направлении и так далее.
В очередной точке xk линеаризуют функцию f(x) (в этом «условность» метода, то есть линеаризация и есть «условие» в названии). Затем решают задачу min линейной функции на X и найденную точку используют для выбора направления движения.
При этом предполагается:
1. Задача мин. линейной функции на X имеет решение.
2. Это решение может быть найдено достаточно просто, лучше всего в явной форме.
3. Нужно указать правило выбора gk. Можно gk определить из условия наискорейшего спуска :
При определенных условиях : f(x*)- f* = o(1/k), где f* = min f(x) на X.