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

Градиент дает направление, в котором функция возрастает с наибольшей скоростью. Однако при условной оптимизации оно, как правило, не является возможным направлением. Поэтому используют не сам градиент (антиградиент), а его проекцию на поверхность ограничений, точнее, на плоскость, аппроксимирующую эту поверхность в текущей точке. Очевидно, что проекция градиента определяет направление наискорейшего изменения функции на поверхности ограничений. Метод применим, если целевая функция и все функции ограничений дифференцируемы. Пусть ограничения заданы в виде (5). Найдем возможное направление l, на кот. скорость изм-я целевой ф-и макс. (1):

В допустимой области D функции y_j постоянны. Поэтому искомое направление должно удовлетворять системе равенств (2):

Из связи направления с координатами: или (3)

Для нахождения наилучшего возможного направления необходимо решить задачу оптимизации (1) – (3). Т.к условия имеют вид =, а ф-и дифференцируемы, для решения этой вспомогательной задачи воспользуемся методом Лагранжа. Функция Лагранжа:

. Неизвестные - векторы и L. Возьмем и приравняем к 0:

Отсюда выразим компоненты искомого вектора:

->

-> ↓

Так как направление ищется в конкретной точке, то все производные в последней формуле (4) – известные константы. Поэтому система уравнений (4) является линейной системой относительно l_j. Ее решение не вызывает затруднений (при условии, что матрица системы не является особенной). Найдя значения l_j, получаем компоненты проекции градиента. Движение осуществляется в направлении, противоположном проекции. Аналогично градиентному методу новая точка вычисляется по формуле (6):

Алгоритм.

1. Задать начальную точку, удовлетворяющую системе (5), начальное значение h⁰ и точность по величине проекции градиента e.

2. В текущей точке вычислить градиенты всех функций (f и y_j) и решить систему (4).

3. Вычислить проекцию градиента.

4. Проверить: если завершить поиск.

5. Вычислить новую точку по формуле (6).

6. Проверить: если значение целевой функции улучшилось, перейти на шаг 2, иначе уменьшить h^k в два раза и перейти на шаг 5.

Качественный характер работы алгоритма иллюстрирует рис. Здесь функции зависят от 2-х переменных, поэтому в каждой точке на линии ограничения может быть всего 2 направления, лучшее из которых определяет проекция градиента. В многомерной задаче таких направлений бесконечное множество. При ли­ней­ных ограни­чениях могут возник­ать проб­лемы поиска лишь при очень малых значе­ниях градиен­тов функций ограничений и совпадении их направлений, так как это приводит к вырожденности матрицы системы (4).