Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
Таккак h
2
>0 всегда, топри и всегдавыполняется
, тоесть x
0
- точкаминимума, апри ,
(h - любое) и x
0
- точкамаксимума. Следовательно, этодостаточныеусловия.
Еслиже , торассуждения, аналогичныепроведеннымдляпервой
производной, можноповторитьдля итакдалее.
Этопозволяетсформулироватьследующееправило:
Теорема 1(необходимоеидостаточноеусловиесуществованияэкстремума
функцийоднойпеременной).
Еслифункция f(x) иеепроизводныенепрерывны, тоточка x
0
являетсяточкой
экстремума (максимумаилиминимума) тогдаитолькотогда, когдапорядок k ее
первой, необращающейсявнольвточке x
0
производнойестьчетноечисло. Приэтом,
если , то x
0
- точкамаксимума, если , то x
0
- точкаминимума.
Такимобразом, приклассическомподходедляпоискаминимумафункцииодной
переменнойнеобходиморешитьуравнение и установить знак в
полученныхточках. Аналитическоерешениетакогоуравнениявобщемслучае
невозможно, поэтомуиспользуютсяметодыприближенногорешенияуравнения
, известныеизматематическогоанализа (методыНьютона, бисекций, ит.д.).
(
)
′
=f x
0
0
(
)
0
0
>
′
′
xf
(
)
(
)
0
00
>−+ xfhxf
(
)
′′
+ <f x h
0
0
(
)
(
)
fx h fx
0 0
0+ − <
(
)
0
0
=
′
′
xf
(
)
0
xf
′
′
′
(
)
(
)
f x
k
0
0<
(
)
(
)
f x
k
0
0>
(
)
′
=f X 0
(
)
′′
f X
(
)
FX=0
Рассмотримфункцию n действительныхпеременных. Введем
матричныеобозначениядляточкивn-мерномпространстве, градиента (вектора
частныхпроизводныхпервогопорядкафункции f) игессиана (матрицычастных
производныхвторогопорядка):
- точкавn-мерномпространстве, - градиент,
- гессиан (матрицаГессе).
- элемент G(x) - частнаяпроизводнаявторогопорядка.
Напомним, что G(x) - симметрическаяматрица.
Определение 3. Функция f(X) имеетлокальныйминимумвточке X
0
, если
существует
окрестность
точки
X
0
,
такая,
что
f(X)>f(X
0
)
во
всех
точках
этой
(
)
(
)
fX fxx x
n
=
1 2
, ,...,
X
x
x
x
n
=
1
2
..
( )
∇ =
fX
f
x
f
x
f
x
n
∂
∂
∂
∂
∂
∂
1
2
...
( )
=
2
2
2
2
1
2
1
2
21
2
2
1
2
...
....
...
nnn
n
x
f
xx
f
xx
f
xx
f
xx
f
x
f
XG
∂
∂
∂∂
∂
∂∂
∂
∂∂
∂
∂∂
∂
∂
∂
ji
ij
xx
f
G
∂∂
∂
2
=
Следовательно, необходимоеусловиесуществованияминимумавточке :
.
Тогдазнакразности f(X
0
+H)-f(X
0
) определяетсячленом , который
положителен для всех H, если матрица G(X
0
) положительно определена, и
отрицателенприотрицательноопределенномгессиане.
Достаточноеусловиеминимума:
- положительноопределена.
Достаточноеусловиемаксимума:
- отрицательноопределена.
производная должна обращаться в ноль в точке X
0
, иначе соответствующим
выбором H можно будет добиться того, что разность f(X
0
+H)-f(X
0
) будет отрицательна.
Предполагаянепрерывность f(X) ивсехеечастныхпроизводных, можно
обобщитьклассическийподходнаслучай n≥2.
ЗапишемразложениефункцииврядТейлора:
= .H=(h
1
,h
2
,...,h
n
)
T
.
Тогда, если X
0
- точкаминимумафункции f(X), токаждаяперваячастная
( ) ( ) ( )
∑ ∑∑
= = =
=++=+
n
i
n
i
n
j
n
ji
jin
i
i
xxx
xx
f
hhxxx
x
f
hHXf
1 1 1
21
2
210
...,...,,
!2
1
,...,,
∂∂
∂
∂
∂
( ) ( )
...
2
1
00
++∇
ΤΤ
HXGHXfH
( )
ni
x
f
i
,...,1, =
∂
∂
(
)
∇ =fX
0
0
( )
∂
∂
f
x
X i n
i
0
0 1= =
, ,...,
( )
HXGH
0
2
1
Τ
(
)
(
)
00
,0 XGXf =∇
(
)
(
)
00
,0 XGXf =∇
Пример:
, тогда
положительноопределенаприлюбомХ,
поэтомуточка (2,4,6) являетсяточкой локального минимума, атаккак
это единственная стационарная точка, то она же является и точкой
глобального минимума.
Такимобразом, длярешениязадачиоптимизацииклассическимметодом
необходиморешитьсистемууравнений , чтоневозможносделать
аналитическизаисключениемоченьузкогоклассатакихсистем (например,
системалинейныхуравненийневысокогопорядка). Затемпридетсяеще
устанавливать
определенность
гессиана,
что
тоже
является
совсем
(
)
1001284
321
2
3
2
2
2
1
+−−−++= xxxxxxxf
( )
0
122
82
42
3
2
1
=
−
−
−
=∇
x
x
x
Xf
.6,4,2
321
=== xxx
( )
GX=
2 0 0
0 2 0
0 0 2
(
)
∇ =fX 0
Итерационные методы оптимизации функций одной переменной
Методы деления интервала
Спомощьючисленных (итерационных) методовможно, например, определять
минимумфункциивнекотороминтервале a<x<b,вкотором, какпредполагается,
лежитточкаминимума. Приэтомможетвычислятьсятолькозначениефункциив
выбранныхточкахданногоинтервала (тоестьнеиспользуетсяпроизводная). Такой
подходимеетважныеприложениянапрактике, когдаможетбыть, например,
неизвестенявныйвидфункции. Методамипоискаопределяетсядостаточномалый
интервал, в котором находится минимум, осуществляя при этом наименьшее
количествовычисленийфункции (таккакзатратынавычислениямогутбытьвесьма
велики).
Длявсехметодов, приводимыхниже, предполагается, чтофункцияунимодальна
навыделенноминтервале, тоестьимееттолькооднуточкуминимума. Прежде, чем
применятьэтиметоды, необходимовыделитьинтервал, содержащийискомуюточку
минимума, иубедиться, чтоонатамединственная. Впротивномслучаепредлагаемые
методыбудутопределятьтолькоодинлокальныйминимум.
Дляопределенияинтервала, содержащеготочкуминимума, обычноиспользуют
следующуюпроцедуру. Выбираютдвестартовыеточки x и у такие, что y=x+s.
Затем, если f(x)>f(y), определяютследующиеточки
x
k+1
= x
k
+ s
дотехпор, поканебудетполучено
f(x
k
) < f(x
k+1
).
Еслиже f(x)<f(y), товыбираетсяпротивоположноенаправление. Точкистроятсяпо
правилу
x
k+1
=x
k
-s
дотехпор, поканебудетполучено
f(x
k
)<f(x
k+1
).
Основнойпроблемойприпримененииописаннойпроцедурыявляетсяправильный
выборвеличины s. Вомногихприкладныхзадачахпеременнаяизменяетсявпределах
многихстепенейдесятки (например, от 0,001 до 10000). Тогдапринеправильномвыборе
величины s минимизацияможетпотребоватьслишкомбольшихзатрат (приоченьмалом
s-на "накрытие" точкиминимума, априбольшом - напоследующееза "накрытием"
сужениеотрезкадотребуемойточности).
Длятогочтобыпреодолетьэтупроблему, былпредложенподходсудвоениемшага.
Вэтомслучаеопределениеверхнейграницыинтервалаосуществляетсяпоправилу
x
k+1
=x
0
+2
k
s.
Послетого, какточкаминимумабыланакрыта, нижняяграницаинтервала
определяетсятемжесамымпроцессом, носизменениемзнакаперед s ивобратном
направлении. Иногдатакойпроцессиспользуютнетолькодля "накрытия" точки
минимума, ноидляееотыскания.
И
последнее,
что
следует
здесь
учесть
-
это
возможность
того,
что
целевая
функция
Метод бисекций
Этотметодпозволяетнакаждомшагеуменьшатьвдвоедлинуинтервала,
содержащегоминимум, причемзначенияцелевойфункциивычисляютсясэтойцельюв
двухопределенныхточках. Есливыполнено n вычисленийцелевойфункции, тодлину
интерваламожноуменьшитьв2
(n-3)/2
раза.
Сначаларазбиваетсяисходныйинтервал (a
0
,b
0
).
Беретсясерединаинтервала
с
0
=(a
0
+b
0
)/2,
затемдветочки
e
0
=(a
0
+c
0
)/2 и d
0
=(c
0
+b
0
)/2,
чтодаетпятьточек, удаленныхдруготдруганаодноитожерасстояние
δ
0
=(b
0
-a
0
)/4.
Сучетомунимодальностилегковидеть, чтовсегдаможноисключитьдваиз
четырехподынтервалов (посколькуточкаминимуманеможетвнихсодержаться) ичто
остаютсятолькодвасмежныхподынтервала (a
1
,c
1
) и (c
1
,b
1
).
Такимобразом, всесводитсяктойжезадаче, ноуженаотрезке (a
1
,b
1
), длина
котороговдваразаменьше, чемуисходного.
Наследующемшагепонадобитсятолькодвадополнительныхвычисленияцелевой
функции
в
точках
e
1
=(a
1
+c
1
)/
2
и
d
1
=(c
1
+b
1
)/
2
и
т
.
д
.
Поиск методом Фибоначчи
Пустьнужноопределитьминимумснаименьшимвозможныминтервалом
неопределенности (точность), ноприэтомможновыполнитьтолько n вычислений
функции. Какследуетвыбратьточки, вкоторыхвычисляетсяфункция?
Очевидно, чтонадосделатьтак, чтобызначенияфункции, полученныев
предыдущихэкспериментах, определялиположениепоследующихточек.
Предположим, что имеется интервал неопределенности (x
1
,x
3
) и известно
значениефункции f(x
2
) внутриэтогоинтервала. Еслиможновычислитьзначение
функциивсегоодинразвточке x
4
, тогдеследуетпоместитьточку x
4
, чтобыполучить
наименьшийвозможныйинтервалнеопределенности?
Пусть x
2
-x
1
=L, x
3
-x
2
=R, L>R. Этизначенияфиксированы, еслиизвестны x
1
,x
2
,x
3
.
Если x
4
находитсявинтервале (x
1
,x
2
), то:
1) если f(x
4
)<f(x
2
) , тоновыминтерваломнеопределенностибудет (x
1
,x
2
) длиной
x
2
-x
1
=L;
2) если f(x
4
)>f(x
2
) , тоновыминтерваломнеопределенностибудет (x
4
,x
3
) длиной
x
3
-x
4
.
Посколькунеизвестно, какаяизэтихситуацийбудетиметьместо, выберем x
4
такимобразом, чтобыминимизироватьнаибольшуюиздлин x
3
-x
4
и x
2
-x
1
. Достигается
этотем, что x
4
помещаетсяв(x
1
,x
3
) симметричноотносительно x
4
. Вэтомслучае x
3
-x
4
= x
2
-x
1
. Влюбомдругомслучаеразмещения x
4
можетбытьтак, чтополученный
интервал
будет
больше
L
.
Еслиокажется, чтоможновыполнитьещеодновычисление, тоследует
применитьописаннуюпроцедурукинтервалу (x
1
,x
2
) или (x
3
,x
4
). Последовательное
применениетакойпроцедурыиобразуетитерационныйпроцессприближениякточке
минимума, называемыйпоискомФибоначчи.
ЧислаФибоначчиопределяютсяследующимобразом:
, тоесть
Еслиначальныйинтервал (a,b) имеетдлину L=(b-a), - точностьвычисления
значенияфункции, токонечныйинтервалнеопределенностибудетравен
,
тоестьуменьшитсявF
n
раз (пренебрегая ) иэтонаилучшийгарантированный
результат.
Отметим, чтовначалепоиска, когдаизвестнытолько a и b, необходимо
правильноустановитьпервуювнутреннююточку. Онаразмещаетсянарасстоянии L
2
отлюбогоконцаинтервала
,
F
F
F
F
F
k
k
k
0
1
1
2
1
1
=
=
=
+
−
−
,
,
,
k
=
2
3
,
,
.
.
.
(
)
,...21,13,8,5,3,2,1,1
ε
L
L
F
F
F
n
n
n
n
= +
−1 2
ε
ε
( )
L
F
F
L
F
n
n
n
n
2
1
1
1
= +
−
−
ε
Поиск методом "золотого сечения"
Невсегдаможнозаранееопределить, сколькоразпридетсявычислятьфункцию.
ВметодеФибоначчиэтонужнознатьдляопределенияположенияначальнойточки.
Метод "золотогосечения" почтистольжеэффективен, какиметодФибоначчи,
однако при этом не требуется знать n - количество вычислений функции,
определяемоевначале. Вэтомметодеинтервалнеопределенностинакаждомшаге
делитсянадвечаститак, чтоотношениецелогокбольшейчастиравноотношению
большейчастикменьшей, тоестьравнотакназываемому "золотомусечению"
Поиск методом "золотого сечения" является предельным случаем поиска
Фибоначчиипридостаточнобольших n даетрезультат, лишьна 17% худший. Затоне
требуетначальногозаданияколичествавычисленийфункции.
(
)
τ=
+
≈
1 5
2
1618033989. .
Интерполяционные методы
Рассмотренныевышеметодыпозволялинайтималыйинтервал, вкотором
находитсяминимумфункции, причемотсамойфункциималочтозависело, ее
свойствавообщенепринималисьвовнимание. Этовыглядитдовольностранным, что
иприводиткидееотом, чтовозможенидругойподход: используетсянесколько
значенийфункциивопределенныхточкахдляаппроксимациифункцииобычным
полиномом, покрайнеймеревнебольшойобласти. Затемположениеминимума
функцииаппроксимируетсяположениемминимумаполинома, посколькупоследний
вычислить проще. При этом характер поведения оптимизируемой функции
учитываетсяпривыборевидаполиномаиприегопостроении, вчемисостоит
отличиеотметодовделенияинтервала.