|
Содержание работы или список заданий
|
Численные методы поиска экстремума функции нескольких переменных.
Методы первого порядка. Градиентные методы.
К методам первого порядка относятся алгоритмы, в которых в процессе поиска кроме информации о самой функции используется информация о производных первого порядка. К группе таких методов относятся различные градиентные методы.
Градиент функции – вектор, направленный в сторону наискорейшего локального возрастания функции , а его компонентами являются частные производные функции. Поэтому при поиске минимума , следует двигаться в направлении противоположном направлению градиента в данной точке, то есть в направлении наискорейшего спуска.
Общая итерационная формула любого градиентного метода имеет вид:
, при k =1,2,3…
Очевидно, что в зависимости от выбора параметра λ траектории спуска будут существенно различаться.
Существуют функции, у которых линии уровня вытянуты вдоль одной образующей. Такие функции называют плохо обусловленными или овражными. Для таких функций градиентный метод сходится медленно.
Но даже для хорошо обусловленных функций проблема выбора шага нетривиальна в силу отсутствия априорной информации о минимизируемой функции. Если шаг выбирается малым (чтобы гарантировать сходимость), то метод сходится медленно. Увеличение же шага (с целью ускорения сходимости) может привести к расходимости метода. Ниже описаны два алгоритма автоматического выбора шага, позволяющие частично обойти указанные трудности.
1. Градиентный метод с постоянным шагом (с дроблением шага).
В общем случае число λ в формуле , может на каждом шаге (т. е. для каждого k) выбираться заново. Такие методы называются градиентными с переменным шагом. Если λk = λ при всех k, то получающийся метод называется градиентным методом с постоянным шагом (с шагом λ.)
Поясним геометрическую суть градиентного метода. Для этого мы выберем способ изображения функции с помощью линий уровня функции f (изолиний).
Рис. 1.
Геометрическая интерпретация градиентного метода с постоянным шагом изображена на рис. 2.
На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в λ раз" до пересечения с минимизируемой функцией. Находим координаты точки пресечения и снова строим вектор антиградиента.
Рис. 2.
При использовании метода градиента с постоянным шагом необходимо на каждом шаге проверять монотонность убывания функции:
.
Если данное условие перестало выполняться, то необходимо раздробить шаг λ в 2, 3,…, n – раз, т.е.
если , то .
Повторяем процедуру поиска минимума до тех пор, пока не выполнится условие остановки итерационного процесса:
для быстро возрастающей функции
для медленно возрастающей функции ,
где ε и δ – точность нахождения точки минимума.
2. Градиентный метод с оптимальным шагом: метод наискорейшего спуска.
При использовании алгоритма наискорейшего спуска введем функцию φk(λ), где λ – шаг
, λ > 0.
Будем выбирать λk на каждой итерации из условия на этой итерации, решая одномерную задачу минимизации с использованием какого-либо одномерного метода (метод дихотомии, золотого сечения, Ньютона). В этом случае итерационная процедура не требует проверки, т. к. шаг на каждой итерации будет оптимальным.
Важной особенностью метода наискорейшего спуска является то, что при его применении каждое новое направление ортогонально предыдущему . Это объясняется тем, что движение в одном направлении производится до тех пор, пока направление движения не окажется касательным к какой-либо линии постоянного уровня.
Рис. 3.
Процедура наискорейшего спуска может закончиться в стационарной точке любого типа, в которой . Поэтому следует проверять, не завершился ли алгоритм в седловой точке.
Основным достоинством данного метода является быстродействие на регулярных участках рельефа целевой функции.
К основным недостаткам метода наискорейшего спуска можно отнести то, что этим методом находится тот минимум, в область притяжения которого попадёт начальная точка. Этот минимум может и не быть глобальным. Другим недостатком метода является его чувствительность к форме окрестности минимума. Низкая эффективность в "оврагах".
Достоинства и недостатки методов.
Достоинства:
Градиентные методы сходятся гораздо быстрее, чем методы нулевого порядка минимизации функции.
Недостатки:
1. Все градиентные методы плохо сходятся для овражных функций.
2. Градиентные методы тормозятся вблизи точки минимума, т. к. градиент приближается к нулю.
Сравнение метода наискорейшего спуска и метода с постоянным шагом.
В сопоставлении с методом градиента метод наискорейшего спуска оказывается более выгодным с точки зрения сокращения количества итераций.
Метод наискорейшего спуска в отличие от градиентного метода имеет более целеустремлённый характер, производит более крупные шаги, и градиент функции вычисляется в меньшем числе точек, но на каждом шаге метод требует решения задачи одномерной оптимизации.
Пример работы алгоритмов градиентных методов.
F=2x12+x22+x1x2+x1+x2;
X0={4,4} – начальное приближение.
Х={-0.14259, -0.42923} – точка минимума
Fmin= -0.2857 – минимум функции.
ε= 10-6 – точность решения.
График зависимости изменения погрешности от номера итерации для метода с дроблением шага.
Для решения потребовалось 14 итераций.
На начальных шагах относительная погрешность имеет очень большие значения. Погрешность начинает убывать лишь с 4-го шага
График зависимости изменения погрешности от номера итерации для метода наискорейшего спуска.
Для решения потребовалось всего7 итераций. Необходимо отметить , что погешность начинает убывать с первой итерации, т.е. изначально шаги выполняются в оптимальном направлении. При данном решении погрешность убывает по геометрической прогрессии.
Зависимость погрешности от шага итерации. Логарифмическая зависимость погрешности.
Работа алгоритмов градиентных методов на примере овражной функции.
F=x12+10x22-3x1x2+5x1-3x2;
X0={4,4} – начальное приближение.
Х={-2.9379, -0.29072} – точка минимума
Fmin= -6.9032– минимум функции.
ε= 10-6 – точность решения
График зависимости изменения погрешности от номера итерации для метода с дроблением шага для овражной функции.
Для решения потребовалось 57 итераций, что иллюстрирует неэффективность градиентных методов для овражной функции.
На начальных шагах относительная погрешность имеет очень большие значения. Погрешность начинает убывать лишь с 6-го шага
График зависимости изменения погрешности от номера итерации для метода наискорейшего спуска для овражной функции.
Для решения потребовалось всего12 итераций. Погешность начинает убывать с первой итерации. При данном решении погрешность убывает по геометрической прогрессии.
Подводя итог вышесказанному, получаем , что метод градиента с наискорейшим спуском требует меньшего количества итераций, чем метод с дроблением шага, как для простых, так и для овражных функций. Однако, следует помнить, что для поиска оптимального шага на каждой итерации производится решение задачи одномерной оптимизации, требующее определённых вычислительных затрат.
Зависимость погрешности от шага итерации. Логарифмическая зависимость погрешности.
|