Безусловная оптимизация. Метод наискорейшего спуска

Метод наискорейшего спуска является градиентным методом с переменным шагом. На каждой итерации величина шага k выбирается из условия минимума функции f(x) в направлении спуска, т.е.

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

()=f (x (k) -f (x (k)))

Воспользуемся для этого методом золотого сечения.

Алгоритм метода наискорейшего спуска состоит в следующем.

Задаются координаты начальной точки x (0) .

В точке x (k) , k = 0, 1, 2, …, вычисляется значение градиентаf (x (k)).

Определяется величина шага k путем одномерной минимизации по функции

()=f (x (k) -f (x (k))).

Определяются координаты точки x (k) :

x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.

Проверяется условие останова итерационного процесса:

||f (x (k +1))|| .

Если оно выполняется, то вычисления прекращаются. В противном случае осуществляется переход к п. 1. Геометрическая интерпретация метода наискорейшего спуска представлена на рис. 1.

Рис. 2.1. Блок схема метода наискорейшего спуска.

Реализация метода в программе:

Метод наискорейшего спуска.

Рис. 2.2. Реализация метода наискорейшего спуска.

Вывод: В нашем случае метод сошёлся за 7 итераций. Точка А7 (0,6641; -1,3313) является точкой экстремума. Метод сопряженных направлений. Для квадратичных функций можно создать градиентный метод, при котором время сходимости будет конечным и равно числу переменных n.

Назовем некоторое направление исопряженными по отношению к некоторой положительно определенной матрице ГессаH, если выполняется:

Тогда т.е.. Значит при единичнойH, сопряженное направление означает их перпендикуляр. В общем же случае H неединичная. В общем случае сопряженность - это применение матрицы Гесса к вектору - означает поворот этого вектора на некоторый уголи его растяжение или сжатие.

А теперь вектору векторортогонален т. е. сопряженность это не ортогональность векторови, а ортогональность повернутого векторат.е.и.

Рис. 2.3. Блок-схема метода сопряженных направлений.

Реализация метода в программе: Метод сопряженных направлений.

Рис. 2.4. Реализация метода сопряженных направлений.

Рис. 2.5. График метода сопряженных направлений.

Вывод: Точка А3 (0,6666; -1,3333), была найдена за 3 итерации и является точкой экстремума.

3. Анализ методов определения минимального, максимального значения функции при наличии ограничений

Напомним, что общая задача условной оптимизациивыглядит так

f(x) ® min, x Î W,

где W - собственное подмножество R m . Подкласс задач с ограничениями типа равенств выделяется тем, что множество  задается ограничениями вида

f i (x) = 0, где f i: R m ®R (i = 1, …, k).

Таким образом,W = {x Î R m: f i (x) = 0, i = 1, …, k}.

Нам будет удобно писать у функции f индекс "0". Таким образом, задача оптимизации с ограничениями типа равенств записывается в виде

f 0 (x) ® min, (3.1)

f i (x) = 0, i = 1, …, k. (3.2)

Если обозначить теперь через f функцию на R m со значениями в R k , координатная запись которой имеет вид f(x) = (f 1 (x), …, f k (x)), то (3.1)–(3.2)можно также записать в виде

f 0 (x) ® min, f(x) = Q.

Геометрически задача с ограничениями типа равенств - это задача о поиске наинизшей точки графика функции f 0 над многообразием  (см. рис. 3.1).

Точки, удовлетворяющие всем ограничениям (т. е. точки множества ), обычно называют допустимыми. Допустимая точка x* называется условным минимумом функции f 0 при ограничениях f i (x) = 0, i = 1, ..., k (или решением задачи (3.1)–(3.2)), если при всех допустимых точкахx f 0 (x*)  f 0 (x). (3.3)

Если (3.3)выполняется только для допустимыхx, лежащих в некоторой окрестности V x * точки x*, то говорят о локальном условном минимуме. Естественным образом определяются понятия условных строгих локального и глобального минимумов.

Пример 6.8.3-1. Найти минимум функции Q(x,y) методом ГДШ.

Пусть Q(x,y) = x 2 +2y 2 ; x 0 = 2;y 0 = 1.

Проверим достаточные условия существования минимума:

Проделаем одну итерацию согласно алгоритму.

1. Q(x 0 ,y 0) = 6.

2. При х = x 0 и y = y 0 ,

3. Шаг l k = l 0 = 0,5

Таким образом, 4 < 8, следовательно, условие сходимости не выполняется и требуется, уменьшив шаг (l=l /2), повторять п.п.3-4 до выполнения условия сходимости. То есть, полученный шаг используется для нахождения следующей точки траектории спуска.

Суть метода состоит в следующем. Из выбранной точки (x 0 ,y 0) спуск осуществляют в направлении антиградиента до тех пор, пока не будет достигнуто минимальное значение целевой функции Q(x, y) вдоль луча (рис. 6.8.4-1). В найденной точке луч касается линии уровня. Затем из этой точки спуск проводится в направлении антиградиента (перпендикулярном линии уровня) до тех пор, пока соответствующий луч не коснется в новой точке проходящей через нее линии уровня, и т.д.

Выразим целевую функцию Q(x, y) через шаг l. При этом представим целевую функцию на определенном шаге как функцию одной переменной, т.е. величины шага

Величина шага на каждой итерации определяется из условия минимума :

Min( (l)) l k = l*(x k , y k), l >0.

Таким образом, на каждой итерации выбор шага l k предполагает решение задачи одномерной оптимизации. По способу решения этой задачи различают:

· аналитический метод (НСА);

· численный метод (НСЧ).

В методе НСА значение шага получают из условия , а в методе НСЧ величину l k находят на отрезке c заданной точностью, используя один из методов одномерной оптимизации.

Пример 6.8.4-1. Найти минимум функции Q(x,y)=x 2 + 2y 2 с точностью e=0.1, при начальных условиях: x 0 =2; y 0 =1.

Проделаем одну итерацию методом НСА .

=(x-2lx) 2 +2(y-4ly) 2 = x 2 -4lx 2 +4l 2 x 2 +2y 2 -16ly 2 +32l 2 y 2 .

Из условия ¢(l)=0 найдем значение l*:

Полученная функция l=l(x,y) позволяет найти значение l. При x=2 и y=1 имеем l=0.3333.

Вычислим значения координат следующей точки:

Проверим выполнение критерия окончания итераций при k=1:

Поскольку |2*0.6666|>0.1 и |-0.3333*4|>0.1 , то условия окончания процесса итераций не выполнены, т.е. минимум не найден. Поэтому следует вычислить новое значение l при x=x 1 и y=y 1 и получить координаты следующей точки спуска. Вычисления продолжаются до тех пор, пока не выполнятся условия окончания спуска.

Отличие численного метода НС от аналитического состоит в том, что поиск значения l на каждой итерации происходит одним из численных методов одномерной оптимизации (например, методом дихотомии или методом золотого сечения). При этом в качестве интервала неопределенности служит диапазон допустимых значений l - .

Аннотация: В данной лекции широко освещены такие методы многопараметрической оптимизации как метод наискорейшего спуска и метод Давидона – Флетчера – Пауэлла. Кроме того, проводится сравнительный анализ вышеперечисленных методов с целью определения наиболее действенного, выявляются их преимущества и недостатки; а также рассматриваются проблемы многомерной оптимизации, такие как метод оврагов и метод многоэкстремальности.

1. Метод наискорейшего спуска

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

Предположим, что осуществляется перемещение из точки x в следующую точку х + hd , где d - некоторое направление, a h - шаг некоторой длины. Следовательно, перемещение производится из точки (x 1 , х 2 , ..., х n) в точку (x 1 + zx 1 , x 2 + zх 2 , ..., х n + zх n) , где

Изменение значений функции определяется соотношениями

(1.3)

С точностью до первого порядка zx i , причем частные производные вычисляются в точке x . Как следует выбрать направления d i , удовлетворяющие уравнению (1.2), чтобы получить наибольшее значение изменения функции df ? Здесь возникает задача максимизации с ограничением. Применим метод множителей Лагранжа, с помощью которого определим функцию

Величина df , удовлетворяющая ограничению (1.2), достигает максимума, когда функция

Достигает максимума. Ее производная

Следовательно,

(1.6)

Тогда di ~ df/dx i и направление d параллельно направлению V/(x) в точке х .

Таким образом, наибольшее локальное возрастание функции для заданного малого шага h имеет место, когда d есть направление Vf(x) или g(х) . Поэтому направлением наискорейшего спуска является направление

В более простом виде уравнение (1.3) можно записать так:

Где - угол между векторами Vf(x) и dx . Для заданной величины dx мы минимизируем df , выбирая , чтобы направление dx совпадало с направлением -Vf(x) .

Замечание . Направление градиента перпендикулярно в любой точке линии постоянного уровня, поскольку вдоль этой линии функция постоянна. Таким образом, если (d 1 , d 2 , ..., d n) - малый шаг вдоль линии уровня, то

И, следовательно,

(1.8)

Градиентом дифференцируемой функции f(x) в точке х называется n -мерный вектор f(x ) , компоненты которого являются частными производными функции f(х), вычисленными в точке х , т. е.

f"(x) = (дf(х )/дх 1 , …, дf(х )/дх n) T .

Этот вектор перпендикулярен к плоскости, проведенной через точку х , и касательной к поверхности уровня функции f(x), проходящей через точку х .В каждой точке такой поверхности функция f(x) принимает одинаковое значение. Приравнивая функцию различным постоянным величинам С 0 , С 1 , ... , получим серию поверхностей, характеризующих ее топологию (Рис. 2.8).

Рис. 2.8. Градиент

Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор, противоположный градиенту (-f’(х )) , называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентным и методами минимизации. Использование этих методов в общем случае позволяет определить точку локального минимума функции.

Очевидно, что если нет дополнительной информации, то из начальной точки х разумно перейти в точку х , лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска р [k ] антиградиент -f’(х [k]) в точке х [k ], получаем итерационный процесс вида

х[k+ 1] = x [k ]-a k f"(x [k]) , а k > 0; k =0, 1, 2, ...

В координатной форме этот процесс записывается следующим образом:

x i [k +1]=х i [k ] - a k f(x [k]) /x i

i = 1, ..., n ; k = 0, 1, 2,...

В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента || x [k +l] - x [k ] || <= e , либо выполнение условия малости градиента

|| f’(x [k +l]) || <= g ,

Здесь e и g - заданные малые величины.

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

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

f(х[k +1]) = f(x [k] – a k f’(x [k])) < f(x [k]) .

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

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

При использовании метода наискорейшего спуска на каждой итерации величина шага а k выбирается из условия минимума функции f(x) в направлении спуска, т. е.
f(x [k ] –a k f’(x [k ])) = f(x [k] – af"(x [k ])) .

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции
j (a) = f(x [k ] - af"(x [k ])) .

Алгоритм метода наискорейшего спуска состоит в следующем.

1. Задаются координаты начальной точки х .

2. В точке х [k ], k = 0, 1, 2, ... вычисляется значение градиента f’(x [k ]) .

3. Определяется величина шага a k , путем одномерной минимизации по а функции j (a) = f(x [k ] - af"(x [k ])).

4. Определяются координаты точки х [k+ 1]:

х i [k+ 1] = x i [k ] – а k f’ i (х [k ]), i = 1 ,..., п.

5. Проверяются условия останова стерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.

В рассматриваемом методе направление движения из точки х [k ] касается линии уровня в точке x [k+ 1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a k выбирается путем минимизации по а функции?(a) = f(x [k] - af"(x [k ])) . Необходимое условие минимума функции d j (a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

dj (a)/da = -f’(x [k+ 1]f’(x [k ]) = 0.

Рис. 2.9. Геометрическая интерпретация метода наискорейшего спуска

Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе)

мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями l i , i =1, …, n , матрицы являются корни характеристического уравнения

Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 2.10), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 2.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

Рис. 2.10. Овражная функция

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

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

f(x) = (х, Нх) + (b, х) + а

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

По определению, два n -мерных вектора х и у называют сопряженными по отношению к матрице H (или H -сопряженными), если скалярное произведение (x , Ну) = 0. Здесь Н - симметрическая положительно определенная матрица размером п хп.

Одной из наиболее существенных проблем в методах сопряженных градиентов является проблема эффективного построения направлений. Метод Флетчера-Ривса решает эту проблему путем преобразования на каждом шаге антиградиента -f(x [k ]) в направление p [k ], H -сопряженное с ранее найденными направлениями р , р , ..., р [k -1]. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции.

Направления р [k ] вычисляют по формулам:

p[k ] = -f’(x [k ]) +b k-1 p [k -l], k >= 1;

p = -f ’(x ) .

Величины b k -1 выбираются так, чтобы направления p [k ], р [k -1] были H -сопряженными:

(p [k ], Hp [k- 1])= 0.

В результате для квадратичной функции

итерационный процесс минимизации имеет вид

x[k +l] =x [k ] +a k p [k ],

где р [k ] - направление спуска на k- м шаге; а k - величина шага. Последняя выбирается из условия минимума функции f(х) по а в направлении движения, т. е. в результате решения задачи одномерной минимизации:

f(х[k ] + а k р [k ]) = f(x [k ] + ар [k ]) .

Для квадратичной функции

Алгоритм метода сопряженных градиентов Флетчера-Ривса состоит в следующем.

1. В точке х вычисляется p = -f’(x ) .

2. На k- м шаге по приведенным выше формулам определяются шаг а k . и точка х [k+ 1].

3. Вычисляются величины f(x [k +1]) и f’(x [k +1]) .

4. Если f’(x ) = 0, то точка х [k +1] является точкой минимума функции f(х). В противном случае определяется новое направление p [k +l] из соотношения

и осуществляется переход к следующей итерации. Эта процедура найдет минимум квадратичной функции не более чем за п шагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после (п+ 1)-й итерации процедуры 1-4 циклически повторяются с заменой х на х [п +1] , а вычисления заканчиваются при , где - заданное число. При этом применяют следующую модификацию метода:

x[k +l] = x [k ] +a k p [k ],

p[k ] = -f’(x [k ])+ b k- 1 p [k -l], k >= 1;

p = -f’(x );

f(х[k ] + a k p [k ]) = f(x [k ] + ap [k ];

Здесь I - множество индексов: I = {0, n, 2п, Зп, ...} , т. е. обновление метода происходит через каждые п шагов.

Геометрический смысл метода сопряженных градиентов состоит в следующем (Рис. 2.11). Из заданной начальной точки х осуществляется спуск в направлении р = -f"(x ). В точке х определяется вектор-градиент f"(x ). Поскольку х является точкой минимума функции в направлении р , то f’(х ) ортогонален вектору р . Затем отыскивается вектор р , H -сопряженный к р . Далее отыскивается минимум функции вдоль направления р и т. д.

Рис. 2.11. Траектория спуска в методе сопряженных градиентов

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

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

f(x [k ] -a k f"(x [k ])) = f(x [k] - af"(x [k ])) .

j(a) = f(x [k ] - af"(x [k ])) .

Алгоритм метода наискорейшего спуска состоит в следующем.

1. Задаются координаты начальной точки х .
2. В точке х [k ], k = 0, 1, 2, ... вычисляется значение градиента f"(x [k ]) .
3. Определяется величина шага a k , путем одномерной минимизации по а функции j(a) = f(x [k ] - af"(x [k ])).
4. Определяются координаты точки х [k+ 1]:

х i [k+ 1] = x i [k ] - а k f" i (х [k ]), i = 1 ,..., п.

В рассматриваемом методе направление движения из точки х [k ] касается линии уровня в точке x [k+ 1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a k выбирается путем минимизации по а функции?(a) = f(x [k] - af"(x [k ])) . Необходимое условие минимума функции d j(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках: