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

Антиградиент дает только направление минимизации, но не длину шага. Направление проекции антиградиента является локально наилучшим направлением движения к условному минимуму целевой функции. При поиске условного максимума используют проекцию градиента. Вместе с градиентом можно определить вектор антиградиента, равный по модулю вектору градиента, но противоположный по направлению. Он указывает сторону наибольшего убывания функции в данной точке. Все проективные методы предполагают реализацию на каждом k-ом этапе указанной ниже последовательности шагов:

1) алгоритм начинает работу в допустимой точке х;

2) определяется допустимое направление s;

3) в допустимом направлении выбирается шаг длиной , минимизирующий ѓ(х), но в то же время сохраняющий вектор х=х+s допустимым.

Целевая функция метода проекции антиградиента имеет вид . И задача оптимизации задана следующим образом . Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задается антпградиентом :

(2)

Где выбирается

· постоянной, в этом случае метод может расходиться;

· дробным шагом, то есть длина шага в процессе спуска делится на некое число;

· наискорейшим спуском.

Алгоритм:

1) вычислить .

2) если , то вычислить по формуле и закончить вычисления. В противном случае - продолжить вычисления, переходя к пункту 3.

3) определить максимальную длину шага:

4) решить задачу одномерного поиска:

5) положить .

Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях. Некоторые из них:

1.

2.

Здеcь - значение, полученное после -го шага оптимизации. - наперед заданное положительное число

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

Рисунок 1

Геометрическая интерпретация метода градиентного спуска с постоянным шагом. На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в раз".

Линейные ограничения типа равенства. Пусть в задаче оптимизации допустимое множество ? определено ограничениями типа равенства, то есть имеет вид

?={x Є R? : (ai;x) = bi, i=} (3)

а целевая функция ѓ(х) дифференцируема в R?. Предположим, что известна точка х?. Рассмотрим функцию (у)=ѓ(х+P*y), yR? где матрица P определена соотношением

P= А (АА) А (4)

Для этой функции в силу правила дифференцирования сложной функции и симметричной матрицы Р справедливо равенство

grad (y)=P* grad ѓ(x) (5)

Прежде всего убедимся, что х*?. Используя представление

х*=х+Р*у* (6)

и условие х?, заключаем, что (а,х*)=( а,х)+( а,Р*у*)=( а,х)=b, i=. Поскольку вектор Р*у* ортогонален каждому вектору линейного подпространства ?, в том числе и векторам а. Следовательно, х* ?.

Так как у* является стационарной точкой функции (у), то grad (y*)=0, и поэтому, учитывая grad (y)=P* grad ѓ(x) и P= А (АА) А при х=х* и у=у*, находим

Р* grad ѓ(x*)= grad ѓ(x*)- А (АА) grad ѓ(x*)= grad ѓ(x*)+ А= grad ѓ(x*)+а=0, (7)

где = -(АА)А grad ѓ(x*), а - координаты вектора R?. Представив ограничения (3) в виде ѓ(х)=(а,х)-b=0, i=,и учитывая равенства gradѓ(x*)=а, заключаем, что точка х* является стационарной точкой функции Лагранжа

L(x,)=ѓ(x)+((a,x)-b) (8)

то есть удовлетворяет необходимому условию минимума целевой функции ѓ(х) на множестве ?.

Стационарные точки целевой функции ѓ(х) на допустимом множестве можно определять, решая задачу безусловной минимизации функции (у). В общем случае функция (у) может иметь несколько стационарных точек, причем каждой ее стационарной точке у* будет соответствовать стационарная точка (6) функции Лагранжа (8). Через минимизацию функции (у) можно найти все стационарные точки целевой функции. Однако, если целевая функция является выпуклой функцией на выпуклом множестве ?, то для решения задачи минимизации такой функции достаточно найти хотя бы одну стационарную точку целевой функции в ?, поскольку в любой стационарной точке выпуклая функция достигает наименьшего значения. Строго выпуклая функция может иметь лишь одну стационарную точку, так как она может достигать наименьшего значения на выпуклом множестве только в одной точке.

Нелинейные ограничения. Если среди ограничений в задаче оптимизации есть нелинейные, то поиск минимума целевой функции ѓ(х) на допустимом множестве усложняется. Пусть для определенности ?={хR?: g(x)?0, i=}, где g(x)- дифференцируемые функции на k-ой итерации известна точка х?, для которой активными являются ограничения с индексами i={iN: g(x)=0}. Составим матрицу , строками которой являются матрицы-строки (grad g(x)), i, предполагая, что они линейно независимы. Тогда проекционная матрица =I- () спроектирует антиградиент w= -grad ѓ(x) целевой функции в точке x на направление, ортогональное градиентам всех функций g(x), i, задающих в этой точке активные ограничения. Но в общем случае может оказаться, что это направление будет направлением спуска, поскольку оно может лишь касаться в точке x? границы ? множества ?.

2.1 Задача