Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
Метод Ньютона-Рафсона
Данный метод состоит в многократном использовании Ньютоновского
направленияприоптимизациифункций, неявляющихсяквадратичными.
Основнаяитерационнаяформуламногомернойоптимизации X
k+1
=X
k
+λk+1⋅
используетсявэтомметодепривыборенаправленияоптимизацииизсоотношения
, λk+1 = 1.
РеальнаядлинашагаскрытавненормализованномНьютоновскомнаправлении .
Таккакэтотметоднетребуетзначенияцелевойфункциивтекущейточке, тоегоиногда
называютнепрямымилианалитическимметодомоптимизации. Егоспособность
определятьминимумквадратичнойфункциизаодновычислениевыглядитнапервый
взгляд исключительно привлекательно. Однако это "одно вычисление" требует
значительныхзатрат. Преждевсего, необходимовычислить n частныхпроизводных
первогопорядкаиn(n+1)/2-второго. Крометого, матрицаГесседолжнабыть
инвертирована. Этотребуетужепорядка n
3
вычислительныхопераций. Стемиже
самымизатратамиметодысопряженныхнаправленийилиметодысопряженного
градиентамогутсделатьпорядка n шагов, т.е. достичьпрактическитогожерезультата.
Такимобразом, итерацияметодаНьютона-Рафсонанедаетпреимуществвслучае
квадратичной
функции
.
)()(
1111 ++−+
∇−=
kkk
XfXGS
1+k
S
1+k
S
Еслижефункциянеквадратична, то
- начальноенаправлениеуже, вообщеговоря, неуказываетдействительнуюточку
минимума, азначит, итерациидолжныповторятьсянеоднократно;
- шагединичнойдлиныможетпривестивточкусхудшимзначениемцелевой
функции, апоискможетвыдатьнеправильноенаправление, если, например, гессиан
неявляетсяположительноопределенным;
- гессианможетстатьплохообусловленным, чтосделаетневозможнымего
инвертирование, т.е. определениенаправлениядляследующейитерации.
Самапосебестратегиянеразличает, ккакойименностационарнойточке
(минимума, максимума, седловой) приближаетсяпоиск, авычислениязначений
целевойфункции, покоторымможнобылобыотследить, невозрастаетлифункция,
неделаются. Значит, всезависитоттого, взонепритяжениякакойстационарнойточки
оказываетсястартоваяточкапоиска. СтратегияНьютона-Рафсонаредкоиспользуется
самапосебебезмодификациитогоилииногорода.
Методы Пирсона
Пирсонпредложилнесколькометодовсаппроксимациейобратногогессианабез
явноговычислениявторыхпроизводных, т.е. путемнаблюденийзаизменениями
направленияантиградиента. Приэтомполучаютсясопряженныенаправления. Эти
алгоритмыотличаютсятолькодеталями. Приведемтеизних, которыеполучили
наиболееширокоераспространениевприкладныхобластях.
АлгоритмПирсона№2.
Вэтомалгоритмеобратныйгессианаппроксимируетсяматрицей H
k
, вычисляемой
накаждомшагепоформуле
H
k+1
=H
k
+ .
В качестве начальной матрицы H
0
выбирается произвольная положительно
определеннаясимметрическаяматрица.
ДанныйалгоритмПирсоначастоприводиткситуациям, когдаматрица H
k
становитсяплохообусловленной, аименно - онаначинаетосцилировать, колеблясь
междуположительноопределеннойинеположительноопределенной, приэтом
определительматрицыблизоккнулю. Дляизбежанияэтойситуациинеобходимочерез
каждые n шаговперезадаватьматрицу, приравниваяеекH
0
.
АлгоритмПирсона№3.
Вэтомалгоритмематрица H
k+1
определяетсяизформулы
(
)
( )
( ) ( ( ) ( )) ( )
( ) ( ) ( )
X X H fX fX X X
X X fX fX
k k k k k k kT
k kT k k
+ + +
+ +
− − ⋅∇ −∇ ⋅ −
− ⋅∇ −∇
1 1 1
1 1
(
)
( ) ( )
)()()()(
))()((
11
1
kkk
T
kk
T
kkk
XfXfHXfXf
XfXfH
∇−∇⋅⋅∇−∇
∇−∇⋅
++
+
Траекторияспуска, порождаемаяалгоритмом, аналогичнаповедениюалгоритма
Дэвидона-Флетчера-Пауэлла, ношагинемногокороче. Пирсонтакжепредложил
разновидностьэтогоалгоритмасциклическимперезаданиемматрицы.
ПроективныйалгоритмНьютона-Рафсона.
Пирсонпредложилидеюалгоритма, вкоторомматрицарассчитываетсяиз
соотношения
H
k+1
=H
k
+ ,
H
0
=R
0
, гдематрица R
0
такаяже, какиначальныематрицывпредыдущих
алгоритмах.
Когда k кратночислунезависимыхпеременных n, матрица H
k
заменяетсяна
матрицу R
k+1
, вычисляемуюкаксумма
R
k
+ .
Величина
H
k
⋅
(
∇
f(X
k+1
)
-
∇
f(X
k
))
является
проекцией
вектора
приращения
градиента
(
)
(
)
( ) ( )
H fX fX H fX fX
fX fX H fX fX
k k k k k k
T
k k
T
k k k
⋅∇ −∇ ⋅∇ −∇
∇ −∇ ⋅ ⋅∇ −∇
+ +
+ +
( ( ) ( )) ( ( ) ( ))
( ) ( ) ( ) ( )
1 1
1 1
(
)
(
)
( ) ( )
X X R fX fX H fX fX
fX fX H fX fX
k k k k k k k k
T
k k
T
k k k
+ + +
+ +
− − ⋅∇ −∇ ⋅∇ −∇
∇ −∇ ⋅ ⋅∇ −∇
1 1 1
1 1
( ( ) ( )) ( ( ) ( ))
( ) ( ) ( ) ( )
Метод Дэвидона-Флетчера-Пауэла
Этот метод имеет и другие названия - метод переменной метрики,
квазиньютоновскийметод, т.к. ониспользуетобаэтиподхода.
МетодДэвидона-Флетчера-Пауэла (ДФП) основаннаиспользованииньютоновских
направлений, но не требует вычисления обратного гессиана на каждом шаге.
Направлениепоисканашаге k являетсянаправлением , где H
i
- положительно
определеннаясимметричнаяматрица, котораяобновляетсянакаждомшагеивпределе
становитсяравнойобратномугессиану. Вкачественачальнойматрицы H обычно
выбираютединичную. ИтерационнаяпроцедураДФПможетбытьпредставлена
следующимобразом:
1. Нашаге k имеютсяточка X
k
иположительноопределеннаяматрица H
k
.
2. Вкачественовогонаправленияпоискавыбирается
3. Одномернымпоиском (обычнокубическойинтерполяцией) вдольнаправления
определяется λ
k
, минимизирующеефункцию .
4. Полагается .
5
.
Полагается
.
− ∇H fX
i
i
( )
).(
k
kk
XfHd ∇−=
X d
k
k
+
λ
fX d
k
k
( )
+
λ
V d
k
k
k
=
⋅
λ
X X V
k k
k
+
= +
1
)(
1+k
Xf
∇
+
fX
k
( )
1
∇
+
fX
k
( )
1
7. Полагается U
k
= ∇f(X
k+1
)-∇f(X
k
).
8. Матрица H
k
обновляетсяпоформуле
9. Увеличить k наединицуивернутьсянашаг 2.
Метод эффективен на практике, если ошибка вычислений градиента
невеликаиматрица H
k
нестановитсяплохообусловленной.
Матрица Ak обеспечивает сходимость H
k
к G
-1
, матрица B
k
обеспечивает
положительнуюопределенность H
k+1
навсехэтапахивпределеисключает H
0
.
Вслучаеквадратичнойфункции ,
т.е. алгоритмДФПиспользуетсопряженныенаправления.
kk
T
k
k
T
kkk
k
k
T
k
T
kk
k
kkkk
UHU
HUUH
B
UV
VV
A
BAHH
−==
+
+
=
+
,
,
1
∇
fX
k
( )
H E A B
k i
i
k
i
i
k
+
=
=
= + +
∑ ∑
1
1
0
A G B E
i i
i
n
i
n
= =−
−
=
−
=
−
∑∑
1
0
1
1
1
,
Напрактикеоказалось, чтометодДФПможетдаватьотрицательныешагиили
окончитьсявнестационарнойточке. Этовозможно, когда H
k+1
становитсяплохо
обусловленной. Этогоможноизбежатьпутемувеличениячислаполучаемыхзначимых
цифрилиперезаданиемматрицы H
k+1
ввидеспециальнойдиагональнойматрицы H, где
.
Ошибкиокругленияиособеннонеточностьлинейногопоискаможетпослужить
причинойпотериустойчивостиметодаДФПидажепривестикошибочнымшагам,
когдазначениецелевойфункциинанекоторойитерациивозрастаетвместотого, чтобы
уменьшаться.
ПоклассификацииНьютоновскихметодовданныйалгоритмявляетсяквази-
Ньютоновским, хотяониспользуетвявномвидетолькопервыечастныепроизводные, а
значит, можетрассматриватьсяикакградиентныйметод.
Практическая проверка эффективности алгоритма показала, что он столь же
эффективен, как и метод Флетчера-Ривса.
)(
1
1
k
i
k
i
k
i
k
ii
Xf
XX
H
∇
−
=
+
+
Статистические методы поиска
Статистическиеметоды или методыслучайногопоиска получилидостаточно
широкое распространение при построении оптимальных решений в различных
приложениях. Этообъясняетсявпервуюочередьтем, чтосростомразмерностизадач
резкоснижаетсяэффективностьрегулярныхметодовпоиска (детерминиoрованных), так
называемое “проклятие размерности”. Во-вторых, зачастую информация об
оптимизируемомобъектеслишкоммаладлятого, чтобыможнобылоприменить
детерминированныеметоды. Статистическиеалгоритмычастоиспользуютприпоиске
оптимальногорешениявсистемахуправления, когдаоткликможнополучитьтолько
призаданииуправляющихвоздействий навходахсистемы. Втакихситуациях
статистические алгоритмы могут оказаться значительно эффективнее
детерминированных.
x
Статистическиеметодынаиболееэффективныприрешениизадачбольшой
размерностиилиприпоискеглобальногоэкстремума.
Подслучайнымиилистатистическимиметодамипоискабудемпониматьметоды,
использующиеэлементслучайностилибоосбореинформацииоцелевойфункциипри
пробныхшагах, либодляулучшениязначенийфункцииприрабочемшаге. Случайным
образомможетвыбиратьсянаправлениеспуска, длинашага, величинаштрафапри
нарушенииограничения.
Статистическиеалгоритмыобладаютрядомдостоинств:
• простотареализациииотладкипрограмм;
• надежностьипомехоустойчивость;
• универсальность;
• возможностьвведенияоперацийобучения;
• возможностьвведенияоперацийпрогнозированияоптимальнойточки.
Основными недостатками являются большое количество вычислений
минимизируемойфункции, медленнаясходимостьврайонеэкстремума.
Принятосчитать, чтопреимуществостатистическихметодовпроявляетсяс
ростомразмерностизадач, таккаквычислительныезатратывдетерминированных
методах поиска с ростом размерности растут быстрее, чем в статистических
алгоритмах.
Простой случайный поиск
Пустьнамнеобходиморешитьзадачуминимизациифункции приусловии, что
. Вэтойобластипоравномерномузаконувыбираемслучайнуюточку ивычисляемв
нейзначениефункции . Затемвыбираемтакимжеобразомслучайнуюточку и
вычисляем . Запоминаемминимальноеизэтихзначенийиточку, вкоторой
значение функции минимально. Далее генерируем новую точку. Делаем N
экспериментов, послечеголучшуюточкуберемвкачестверешениязадачи (вкоторой
функцияимеетминимальноезначение) средивсехслучайносгенерированных.
(
)
xf
[
]
BAx ,∈
1
x
(
)
1
1
xfy
=
2
x
(
)
2
2
xfy
=
Пусть n - размерностьвекторапеременных. Объем n-мерногопрямоугольника, в
которомведетсяпоискминимума, .
( )
∏
=
−=
n
i
ii
ABV
1
Еслинеобходимонайтирешениесточностью , , покаждойизпеременных,
томыдолжныпопастьвокрестностьоптимальнойточкисобъемом .
i
ε
ni ,1
=
∏
=
ε
ε=
n
i
i
V
1