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

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

Приведем один из вариантов метода проектирования градиента сначала для задачи с ограничениями-равенствами, а затем для общего случая. Метод применим, если целевая функция и все функции ограничений дифференцируемы.

Пусть ограничения заданы в виде

(8.55)

Найдем возможное направление l, на котором скорость изменения целевой функции максимальна:

(8.56)

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

(8.57)

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

что перепишем в виде

(8.58)

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

Запишем функцию Лагранжа:

. (8.59)

Неизвестными в ней являются векторы и L. Взяв производные и приравняв их нулю, получаем

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

(8.60)

Подставив (8.60) в (8.58), находим:

С учетом этого выражения формула (8.60) принимает вид

(8.61)

Для определения неизвестных множителей lj воспользуемся системой (8.57). Подставив в нее (8.61), получаем:

После раскрытия скобок окончательно имеем:

(8.62)

Так как направление ищется в конкретной точке, то все производные в (8.62) – известные константы. Поэтому система уравнений (8.62) является линейной системой относительно lj. Ее решение не вызывает затруднений (при условии, что матрица системы не является особенной). Найдя значения lj и подставив их в (8.61), получаем компоненты проекции градиента (в знаменателе (8.61) имеем длину проекции градиента). Движение осуществляется в направлении, противоположном проекции.

Аналогично градиентному методу новая точка вычисляется по формуле

. (8.63)

Алгоритм.

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

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

3. Вычислить проекцию градиента по формуле (8.61).

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

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

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

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

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

В случае нелинейных ограничений движение на основе линейной аппроксимации нарушает равенства. Поэтому в алгоритм необходимо внести изменения, обеспечивающие выполнение равенств с необходимой точностью ey. С этой целью алгоритм дополняется проверкой величины невязки, которая выполняется в каждой новой точке. Если, то включается процедура коррекции, заключающаяся в минимизации невязки:

(8.64)

Для решения задачи (8.64) можно применить любой метод безусловной оптимизации, но в данном контексте целесообразен метод градиентов. При этом значения (n-m) переменных фиксируются, так как для выполнения равенств достаточно m переменных. Понятно, что при частых коррекциях трудоемкость алгоритма значительно возрастает.

Теперь рассмотрим случай, когда ограничения заданы в виде неравенств jj(x)£0. Поиск начинается из точки, в которой удовлетворяются все ограничения. Пока они выполняются как строгие, движение осуществляется по градиентному методу. Когда достигается граница допустимого множества, одно или несколько ограничений обращаются в равенства. Такие ограничения называют активными. В точках с активными ограничениями направление движения определяется по проекции градиента на поверхность этих ограничений, то есть применяется вышеприведенный алгоритм. Пример поиска минимума при двух линейных неравенствах показан на рис. 8.40. Очевидно, что при смешанных и нелинейных ограничениях алгоритм весьма существенно усложняется и требует большого объема вычислений. Поэтому метод проектирования градиентов целесообразно применять при линейных ограничениях.

8.9.2. Метод штрафных функций

Совершенно иной подход используется в методах штрафных и барьерных функций. Ограничения задачи специальным образом отражаются в критерии, в результате чего критерий модифицируется, а исходная задача на условный экстремум сводится к задаче на безусловный экстремум.

В методе штрафных функций в критерий вводится штраф при нарушении условий задачи. Пусть в общем случае имеем задачу

f(x) à min; (8.65)

ji(x) £ 0,; (8.66)

yi(x) = 0,. (8.67)

Тогда можно построить вспомогательную функцию

Q(x) = f(x) + a×H(x), (8.68)

где H(x)–функция штрафа, a — параметр штрафа.

Вспомогательная функция играет роль модифицированного критерия, который при выполнении всех ограничений должен совпадать с исходным. Поэтому необходимо, чтобы в допустимой области Н(х) равнялась нулю, а вне ее была положительной. Для задачи (8.65)-(8.67) функция штрафа включает две составляющие Н(х) =Нj(x) + Нy(x), учитывающие ограничения-неравенства и ограничения-равенства соответственно и удовлетворяющие условиям

(8.69)

Возможны разные конструкции функций, обладающих указанными свойствами. Типичные представители составляющих штрафной функции имеют вид

где р – натуральное число. Для дифференцируемости функций берут четные значения р, обычнор = 2.

Чем больше a, тем сильнее влияет функция штрафа и, значит, тем точнее выполняются условия задачи.

Пример 8.8. Дана задача

f(x) = x à min;

j(x)=3 – x £ 0.

Ответ очевиден: x*=3. Теперь сведем эту задачу к определению безусловного экстремума вспомогательной функции. Построим штрафную функцию в соответствии с (8.69): H = [max (0, 3-x)]2. Тогда приходим к задаче

Q=x+a[max (0, 3-x)]2® min.

На рис. 8.41 и 8.42 показаны функции aH и Q для двух значений a. Видно, что точки минимума вспомогательной функции с увеличением a приближаются к точке условного минимума исходной задачи. Такой же вывод следует из аналитического решения. Действительно, при x<3 вспомогательная функция имеет вид

Находим минимум этой функции:

Отсюда получаем

Пример 8.9. Рассмотрим влияние параметра шага в задаче

Здесь и На рис. 8.43 построены линии уровня функции q для разных значений a и линия ограничения y. При a=0 имеем q=f, и минимум q достигается в точке безусловного минимума f: x1=x2=1. С увеличением a меняется форма линий уровня q и положение минимума. При a=1 минимум q смещается к линии ограничения, а при a=1000 он практически точно совпадает с условным минимумом задачи.

В обоих примерах с увеличением a генерируемые точки приближаются к оптимальному решению извне допустимого множества. Поэтому ряд авторов называют рассматриваемый метод методом внешних штрафов.

Таким образом, чтобы безусловный минимум вспомогательной функции был близок к условному минимуму решаемой задачи, необходимо брать очень большое значение a, теоретически бесконечное. Однако при больших a возникают серьезные трудности при поиске минимума вспомогательной функции. Поэтому предлагается решать последовательность задач минимизации Q с возрастающими значениями a. При этом в качестве начальной точки следующей задачи берется оптимальная точка предыдущей. Такой прием использован в следующем алгоритме штрафных функций.

Алгоритм.

1. Задать: начальную точку x0, точность e, начальное значение a0 и число b > 1.

2. Минимизировать Q(x) одним из методов безусловной оптимизации, в результате чего определяется .

3. Проверить: если, то остановиться, приняв за оптимальное решение задачи.

4. Положить, за начальную точку принять и вернуться на шаг 2.▲

Рекомендуется выбирать значения параметров алгоритма из диапазонов: a0Î(0,1], bÎ(1,10]. Начальную точку следует задавать в недопустимой области.

Пример 8.10. Алгоритмом штрафных функций решить задачу

Возьмем начальную точку x0=(-5;5), a0=0,21, b=5 и e=0,0001. Применяя для минимизации Q метод Ньютона, получаем результаты, представленные в табл. 8.4.

Таблица 8.4

Как следует из таблицы, решение с заданной высокой точностью получено за 11 итераций алгоритма. Заметим, что несмотря на увеличение a значение aH сходится к нулю, обеспечивая сходимость алго­ритма. Траектория поиска и линии уровня функции f изображены на рис. 8.44.▲

Другой пример поиска методом штрафных функций приведен на рис. 8.45 для задачи

Поиск проведен из начальной точки (-2;-7) с параметрами a0=0,1 и b=2. Здесь, как и в предыдущем примере, на первой итерации алгоритма движение направлено в сторону безусловного минимума целевой функции. Это объясняется небольшим начальным значением параметра штрафа, при котором основное влияние на направление оказывает целевая функция. С возрастанием a направление поиска ориентируется на условный экстремум.

Еще один пример поиска показан на рис. 8.46 для задачи

Здесь поиск производился при a0=1 и b=10. Такие параметры обусловили другой характер движения к условному минимуму: первая итерация уже не приводит в окрестность безусловного экстремума и траектория не имеет резких изменений направ­ления поиска.

Таким образом, выбор параметров поиска имеет существенное влияние на эффективность алгоритма.