Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
Теорема 1.3. Если, начиная из X
0
, после использования p сопряженных
направлений (p<n) определяетсяточка X
a
иесли, начинаяиз X
1
, послеиспользования
этихженаправленийопределяетсяточка X
b
, функция f минимизируетсянакаждом
шаге, товектор X
b
-X
a
сопряженковсем p направлениям.
Утверждение 1.2. Пусть 1, 2,..., n - некоторые направления
оптимизирующего поиска функции f в R
n
, A - матрица, столбцы которой
есть 1, 2,…, n. Тогдаопределительматрицы A принимаетмаксимальноезначение
тогдаитолькотогда, когда 1, 2,..., nсопряженыотносительноматрицыГессе
функции f.
ИдеяалгоритмаПауэлласостоитвтом, чтонакаждомэтапепоискаопределяется
минимумквадратичнойфункции, которойаппроксимируетсяцелеваяфункция, вдоль
каждогоизсопряженныхковсемпредыдущим (см. теоремы 1.2 и 1.3). Затем
выбираетсяноваясистеманаправленийсиспользованиемрезультатовпоискаи
утверждения 1.2.
S
S
S
S
S
S
S
S
S
АлгоритмПауэлла
Шаг 1. Начинаяиз X
0
, спомощьюкакого-либоодномерногопоискаопределяется
λ1 так, чтобызначение f(X
0
+λ1 1) принималоминимальноезначение. Полагается
X
1
=X
0
+λ1 1.Начинаяиз X
1
осуществляетсяодномерныйпоисквнаправлении 2 и
определяется X
2
=X
1
+λ22.Поискпродолжаетсяпоследовательновкаждомнаправлении
1, 2,..., n, всегданачинаяизсамойпоследнейточки, поканебудутполученывсе λ
i
,
i=1,...,n.
S
S
S
S
S
S
S
Шаг 2. Поиск, осуществляемыйвсоответствиисшагом 1, можетпривестик
линейно-зависимым направлениям (если в одном из направлений невозможно
продвижение, тооднаизкомпонент j становитсянулемимогутпоявиться
коллинеарные направления). Поэтому после выполнения шага 1 проводится
дополнительныйшагвеличиной (X
n
-X
0
), соответствующийполномуперемещению
нашаге 1 иприводящийвточку (2⋅X
n
-X
0
).
Затемпроводитсятест (шаг 3), чтобыубедиться, уменьшаетсялиопределитель
матрицынаправленийпоискапослевключенияновогонаправленияиотбрасывания
старого.
Шаг 3. Пусть ∆ - наибольшееуменьшениевкаком-либонаправлениипоискана
шаге 1. .
Направлениепоиска, соответствующее ∆, обозначимчерез m.
Если f(2⋅X
n
-X
0
)≥f(X
1
) или
(f(X
1
)-2⋅f(X
n
)+f(2⋅X
n
-X
0
))⋅(f(X
1
)-f(X
n
)-∆)≤∆⋅(f(X
0
)–f(2⋅X
n
-X
0
))
2
,
топерейтикшагу 1, причемстемижесамыминаправлениями 1, 2,..., n,
начинаяпоискизточки X
n
илиизточки (2⋅X
n
-X
0
), взависимостиоттого, вкакойточке
функцияпринимаетнаименьшеезначение.
Шаг 4. Еслитестнашаге 3 неудовлетворен, тоопределяетсяминимумв
направлении =X
n
-X
0
,точкаэтогоминимумавыбираетсявкачественовойначальной
точки
(X
0
)
для
шага
1
.
Система
направлений
изменяется
следующим
образом
:
{
}
)()(
1
,...,1
max
ii
ni
XfXf −=∆
−
=
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
Шаг 5. Проверкакритерияостанова: изменениепокаждойнезависимой
переменнойменьше, чемзаданнаяточность ε
i
, i =1,…,n или .
Можетпоказатьсянерациональнымотбрасываниесамогоудачногонаправления
текущейитерациииустановкановогоперспективногонаправлениянапоследнее
место, вместопервого. Однакоженетрудновидеть, чтосамоеудачноенаправление,
скореевсегоисчерпалосебя, ановоеперспективноенаправлениетолькочтобыло
использованодляодномернойоптимизацииииспользоватьегосразуженетникакого
смысла, т.к. продвиженияпростонебудет.
Доказано, чтопроцедураПауэлласходитсякточке, вкоторойградиентравен
нулю, если f(X) - строго выпуклая функция. Эта точка является локальным
экстремумом. Метод очень чувствителен к способу построения сопряженных
направленияипоэтомузависитотточностииспользуемогоодномерногопоиска.
Пауэллпредложилиспользоватьпоследовательностьквадратичныхинтерполяцийсо
специальнойпроцедуройнастройкипараметровэтоголинейногопоиска. Темне
менее, численныеисследованияпоказали, чтометодсопряженныхнаправлений
Пауэлланеследуетиспользоватьприразмерностисвыше 20.
X X
n
− ≤
0
01, ε
Градиентные методы
Градиентные методы безусловной оптимизации используют только первые
производныецелевойфункциииявляютсяметодамилинейнойаппроксимациина
каждом шаге, т.е. целевая функция на каждом шаге заменяется касательной
гиперплоскостьюкееграфикувтекущейточке.
На k-мэтапеградиентныхметодовпереходизточки X
k
вточку X
k+1
описывается
соотношением:
X
k+1
=X
k
+λ
k
⋅S
k
, (1.2)
где λ
k
- величина шага,
k
- вектор в направлении X
k+1
-X
k
.
S
Методы наискорейшего спуска
ВпервыетакойметодрассмотрелиприменилещеО.КошивXVIII в. Идеяего
проста: градиентцелевойфункции f(X) влюбойточкеестьвекторвнаправлении
наибольшего возрастания значения функции. Следовательно, антиградиент будет
направленвсторонунаибольшегоубыванияфункциииявляетсянаправлением
наискорейшегоспуска. Антиградиент (иградиент) ортогоналенповерхностиуровня
f(X) вточке X. Еслив(1.2) ввестинаправление
,
тоэтобудетнаправлениенаискорейшегоспускавточке X
k
.
Получаемформулупереходаиз X
k
в X
k+1
:
)(
)(
k
k
k
Xf
Xf
S
∇
∇
−=
)(
)(
)(
1 kk
k
k
kkk
XfX
Xf
Xf
XX ∇−=
∇
∇
−=
+
µλ
Антиградиентдаеттольконаправлениеспуска, ноневеличинушага. Вобщем
случаеодиншагнедаетточкуминимума, поэтомупроцедураспускадолжна
применятьсянесколькораз. Вточкеминимумавсекомпонентыградиентаравнынулю.
Всеградиентныеметодыиспользуютизложеннуюидеюиотличаютсядругот
другатехническимидеталями: вычислениепроизводныхпоаналитическойформуле
иликонечно-разностнойаппроксимации; величинашагаможетбытьпостоянной,
меняться по каким-либо правилам или выбираться после применения методов
одномернойоптимизациивнаправленииантиградиентаит.д.ит.п.
Останавливатьсяподробномынебудем, т.к. методнаискорейшегоспускане
рекомендуетсяобычновкачествесерьезнойоптимизационнойпроцедуры.
Однимизнедостатковэтогометодаявляетсято, чтоонсходитсяклюбой
стационарнойточке, втомчислеиседловой, котораянеможетбытьрешением.
Носамоеглавное - оченьмедленнаясходимостьнаискорейшегоспускавобщем
случае. Деловтом, чтоспускявляется "наискорейшим" влокальномсмысле. Если
гиперпространствопоискасильновытянуто ("овраг"), тоантиградиентнаправленпочти
ортогональнодну "оврага", т.е. наилучшемунаправлениюдостиженияминимума. В
этомсмыслепрямойпереводанглийскоготермина "steepestdescent", т.е. спускпо
наиболее крутому склону более соответствует положению дел, чем термин
"наискорейший",
принятый
в
русскоязычной
специальной
литературе
.
Одним
из
Метод сопряженного градиента Флетчера-Ривса
Вметодесопряженногоградиентастроитсяпоследовательностьнаправлений
поиска , являющихсялинейнымикомбинациями , текущегонаправления
наискорейшегоспуска, и , предыдущихнаправленийпоиска, т.е.
,
причемкоэффициентывыбираютсятак, чтобысделатьнаправленияпоиска
сопряженными. Доказано, что
иэтооченьценныйрезультат, позволяющийстроитьбыстрыйиэффективный
алгоритмоптимизации.
АлгоритмФлетчера-Ривса.
1. В X
0
вычисляется .
2. На k-омшагеспомощьодномерногопоискавнаправлении находитсяминимум
f(X), которыйиопределяетточку X
k+1
.
3. Вычисляются f(X
k+1
) и .
4
.
Направление
определяется
из
соотношения
:
−∇fX
k
( )
S S S
k0 1 1
, ,...,
−
∑
=
+
=+−∇=
k
i
i
i
kk
kSXfS
1
1
,...2,1,)( α
2
1
2
121
)(
)(
,0...
−
−
∇
∇
=====
k
k
kk
Xf
Xf
αααα
S fX
0 0
=
−
∇
( )
S
k
∇
+
fX
k
( )
1
S
k
+
1
)()(
)()(
)(
11
11
kkT
kkT
kkk
XfXf
XfXf
SXfS
∇∇
∇∇
+−∇=
+
+
++
S
5. После (n+1)-йитерации (т.е. при k=n) производитсярестарт: полагается X
0
=X
n+1
иосуществляетсяпереходкшагу 1.
6. Алгоритмостанавливается, когда , где ε - произвольнаяконстанта.
ПреимуществомалгоритмаФлетчера-Ривсаявляетсято, чтооннетребует
обращенияматрицыиэкономитпамятьЭВМ, таккакемуненужныматрицы,
используемыевНьютоновскихметодах, новтожевремяпочтистольжеэффективен
какквази-Ньютоновскиеалгоритмы. Т.к. направленияпоискавзаимносопряжены, то
квадратичнаяфункциябудетминимизировананеболее, чемза n шагов. Вобщемслучае
используетсярестарт, которыйпозволяетполучатьрезультат.
АлгоритмФлетчера-Ривсачувствителенкточностиодномерногопоиска, поэтому
приегоиспользованиинеобходимоустранятьлюбыеошибкиокругления, которые
могутвозникнуть. Крометого, алгоритмможетотказатьвситуациях, гдеГессиан
становитсяплохообусловленным. Гарантиисходимостивсегдаивездеуалгоритманет,
хотяпрактикапоказывает, чтопочтивсегдаалгоритмдаетрезультат.
S
k
<ε
Ньютоновские методы
Направлениепоиска, соответствующеенаискорейшемуспуску, связанослинейной
аппроксимацией целевой функции. Методы, использующие вторые производные,
возниклиизквадратичнойаппроксимациицелевойфункции, т. е. приразложении
функцииврядТейлораотбрасываютсячленытретьегоиболеевысокихпорядков.
,
где - матрицаГессе.
Минимумправойчасти (еслионсуществует) достигаетсятамже, гдеиминимум
квадратичнойформы. Запишемформулудляопределениянаправленияпоиска :
.
Минимумдостигаетсяпри .
Алгоритмоптимизации, вкоторомнаправлениепоискаопределяетсяизэтого
соотношения, называется методом Ньютона, а направление - ньютоновским
направлением.
В
задачах
поиска
минимума
произвольной
квадратичной
функции
с
fx fX fX X X X X GX X X
k T k k k T k k
() ( ) ( )( ) ( ) ( )( )≈ +∇ − + − −
1
2
GX
k
( )
S
fX S fX fX S SGX S
k k T k T k
( ) ( ) ( ) ( )+ = +∇ −
1
2
))()(( ),()(
1 kkkk
XfXGSXfSXG ∇−=−∇=
−
S
Классификация Ньютоновских методов
СобственнометодНьютонасостоитводнократномпримененииНьютоновского
направлениядляоптимизацииквадратичнойфункции. Еслижефункциянеявляется
квадратичной, товернаследующаятеорема.
Теорема. ЕслиматрицаГессенелинейнойфункции f общеговидавточке
минимума X
*
положительноопределена, начальнаяточка X
0
выбранадостаточноблизко
к X
*
идлинышаговподобраныверно, тометодНьютонасходитсякX
*
сквадратичной
скоростью.
МетодНьютонасчитаетсяэталонным, снимсравниваютвсеразрабатываемые
оптимизационныепроцедуры. ОднакометодНьютонаработоспособентолькопри
положительноопределеннойихорошообусловленнойматрицейГессе (определительее
долженбытьсущественнобольшенуля, точнееотношениенаибольшегоинаименьшего
собственныхчиселдолжнобытьблизкокединице). Дляустраненияэтогонедостатка
используют модифицированные методы Ньютона, использующие ньютоновские
направленияпомеревозможностииуклоняющиесяотнихтолькотогда, когдаэто
необходимо.
ОбщийпринципмодификацийметодаНьютонасостоитвследующем: накаждой
итерациисначаластроитсянекоторая "связанная" с G(X
k
) положительноопределенная
матрица , азатем вычисляетсяпоформуле .
Таккак положительноопределена, то - обязательнобудетнаправлением
спуска. Процедурупостроения организуюттак, чтобыонасовпадаласматрицей
Гессе, еслионаявляетсяположительноопределенной. Этипроцедурыстроятсяна
основе
некоторых
матричных
разложений
.
GS fX
k
k
=−∇ ( )
G
k
S
G
k
S
G
k
Другаягруппаметодов, практическинеуступающихпобыстродействиюметоду
Ньютона, основананааппроксимацииматрицыГессеспомощьюконечныхразностей,
т.к. необязательнодляоптимизациииспользоватьточныезначенияпроизводных. Эти
методыполезны, когдааналитическоевычислениепроизводныхзатруднительноили
простоневозможно. Такиеметодыназываются дискретнымиметодами Ньютона.
Залогомэффективностиметодовньютоновскоготипаявляетсяучетинформациио
кривизнеминимизируемойфункции, содержащейсявматрицеГессеипозволяющей
строитьлокальноточныеквадратичныемоделицелевойфункции. Новедьвозможно
информациюокривизнефункциисобиратьинакапливатьнаосновенаблюденияза
изменением градиента во время итераций спуска. Соответствующие методы,
опирающиесянавозможностьаппроксимациикривизнынелинейнойфункциибез
явногоформированияеематрицыГессе, называют квази-Ньютоновскимиметодами.
Отметим, чтоприпостроенииоптимизационнойпроцедурыньютоновскоготипа (в
томчислеиквази-Ньютоновской) необходимоучитыватьвозможностьпоявления
седловойточки. Вэтомслучаевекторнаилучшегонаправленияпоискабудетвсевремя
направленкседловойточке, вместотого, чтобыуходитьотнеевнаправлении "вниз".