Основи системного аналізу Пошук екстремуму цільових функцій. Умови оптимальності

1. Лекція 10. Основи системного аналізу Пошук екстремуму цільових функцій. Умови оптимальності

Алгоритмічні методи, які підлягають розгляду в розділі відносяться до
рекурентних ітеративних процедур. На протязі розділу вважається, що в
наявності є достатньо апріорної інформації.
При достатній апріорній інформації критерій оптимальності - функціонал
та обмеження визначені в явній формі.
Якщо функціонал J (c) допускає диференціювання, то він досягає екстремуму
c (c1, , cN )
тільки при таких значеннях
, для яких N похідних
dJ (c)
(v 1, 2, , N )
dcv
одночасно обертаються в нуль, чи для яких градієнт функціонала
dJ (c)
dJ (c)
J (c)
, ,
dc1
dcv
обертається в нуль.
При цьому вектори мають задовольняти умові
(2.1)
J (c) 0

2. Регулярний ітеративний метод

2
Регулярний ітеративний метод
Ці умови оптимальності дозволяють виділяти лише локальні
екстремуми, та якщо їх багато, задача знаходження глобального екстремуму стає
складною.
Спочатку будемо вважати, що оптимальне значення
вектору
єдине
та що екстремальне значення функціонала являє собою
c
мінімум.
Важливим підходом для вирішення проблеми оптимальності є
підхід, спрямований на пошук оптимального вектору
c c
на основі послідовних наближень
c[n] c[n 1] γ[n] J (c[n 1]),
Значення γ[n
номеру кроку.
визначає величину чергового кроку і може залежати від

3. Різновиди алгоритмів оптимізації

3
• У тих випадках, коли поверхні J (c) const мають різко виражені
«яри» і швидкість переміщення до оптимальної c мала, замість
скаляра γ[n
вводять матрицю
[n] γ vμ [n]
(v, μ 1, 2, , N )
• В цьому випадку величини кроків по різним змінним різні і можуть
залежати один від одного.
• Таким чином, якщо [n] - постійна матриця, яка не залежить
від n, тоді алгоритм оптимізації буде с постійним кроком.
• Якщо [n залежить від n, алгоритм оптимізації буде зі змінним
кроком, та інші.

4. Різновиди алгоритмів оптимізації 4

• У загальному випадку [n] може залежати від c[m] (m n 1, n 2, )
• Ці алгоритми мають назву алгоритми оптимізації з нелінійним
кроком.
• До цих алгоритмів відносять алгоритми релаксаційного типу, в яких
на кожному кроці [n]
обирають так, щоб зменшувалась яка
небудь функція помилки c[n] c
.
• Релаксаційні алгоритми підрозділяють на координатні,
• в яких матриці гама на кожному кроці змінюються так, що на
кожному кроці змінюються одна чи кілька компонент вектору c[n] , та
градієнтні, в яких
[n] Iγ[n],
(2.12)

5. Різновиди алгоритмів оптимізації 5

Різновиди алгоритмів оптимізації
[n] Iγ[n],
У
5
(2.12)
I
- одинична матриця, а γ[n] - скаляр, який залежить
також від координат вектору с.
• Так, до алгоритмів з нелінійним кроком можна віднести відомий
алгоритм Ньютона
c[n 1] [ 2 J (c[n 1])] 1 J (c[n 1]).
• де
[n] [ 2 J (c[n 1])] 1
– До релаксаційних алгоритмів відносять відомий алгоритм
найшвидшого спуску
c[n 1] γ[n] J (c[n 1])

6. Різновиди алгоритмів оптимізації 6 Пошукові алгоритм оптимізації

• Не завжди можна вичислити в явній формі градієнт функціонала (2.1),
а тому і не завжди можна використовувати вказані вище алгоритми
оптимізації.
• Така ситуація виникає, коли функціонал розривний, або не підлягає
диференціюванню, коли його залежність від с виражена у неявній
формі, або сформульована з допомогою логічних операцій.
• У таких умовах використовують пошукові способи визначення
екстремуму. При пошукових способах здійснюють вимірювання
величин, завдяки чому з’являється можливість оцінювати градієнт.

7. Різновиди алгоритмів оптимізації 7 Пошукові алгоритм оптимізації

Різновиди алгоритмів оптимізації
Пошукові алгоритм оптимізації
• Компонентами векторів значень функціоналу при зміні значень
векторів с:
J (c, a) ( J (c ae1), , J (c aeN )),
J (c, a) ( J (c ae1 ), , J (c ae N )).
• Тут a - скаляр,
• Наприклад
eν
- базисні вектори.
c1 (1, 0, , 0); c2 (0, 1, , 0); ; c N (0, 0, , 1).
7

8. Різновиди алгоритмів оптимізації 8 Пошукові алгоритм оптимізації

• Тоді градієнт можна приблизно оцінювати по формулі
J (c, a) J (c, a) ~
J (c, a)
c
2a
(2.20)
• яка визначає так звану роздільну різність. Якщо замінити у
наведеному раніше загальнім алгоритмі оптимізації (2.4)
градієнт функціоналу його наближеним значенням (2.20),
можна отримати пошуковий алгоритм оптимізації
~
c[n] c[n 1] γ[n] J (c[n 1], a[n]).
c

9. Різновиди алгоритмів оптимізації 9 Методи випадкового пошуку

• В усіх регулярних методах пошуку мінімуму J (c) для отримання
поточної оцінки параметра c[n
робиться невипадковий крок,
який однозначно визначений
або значенням J (c
градієнта при c c[n]
,
• або значенням функції J (c)
• В методах випадкового пошуку при переході від c c[n 1] до c[n
• здійснюється випадковий крок γξ
де
ξ
- одиничний випадковий вектор, який частіше за все
рівномірно розташований у n-мірній одиничній сфері;
величина кроку. В цьому випадку
c[n] c[n 1]
γξ[n], ÿêùî J (c[n 1] γξ[n]) J (c[n 1]),
J (c[n 1] γξ[n]) J (c[n 1]).
0, ÿêùî
γ
-
(2.45)

10. Різновиди алгоритмів оптимізації 10 Методи випадкового пошуку

• Існують різноманітні модифікації алгоритму (2.45).
• В цьому алгоритмі випадковий крок здійснюють тільки в тому
випадку, коли J (c[n]) J (c[n 1]) в протилежному випадку система
залишається в попередньому стані.
• В інших алгоритмах, наприклад, «з карою випадковістю»,
випадковий крок проводять тільки тоді, коли попередній крок був
невдалим, і таке інше.
• Наприклад, якщо в регулярному градієнтному алгоритмі
• величину
зробити випадковою, то також отримаємо
γc
алгоритм випадкового пошуку:
c[n] c[n 1] γ c [n]J (c[n 1])
(2.46)
Треба підкреслити, що випадковий крок, який не залежить від
абсолютного значення градієнта функції чи самої функції, допомагає
оминути хоча б деякі неглибокі локальні екстремуми функції.

11. Різновиди алгоритмів оптимізації Обговорення 11

• Алгоритмічні методи визначення екстремуму можна пояснити на
прикладі спелеолога, який досліджує печеру, з метою досягнути її
найглибшого місця.
• Спелеолог може дослідити характер місцевості лише в околі свого
місцезнаходження. Ймовірно, він обере напрямок найбільш крутого
нахилу (тобто в напрямку вздовж градієнта). Він буде рухатись в цьому
напрямку, поки цей рух буде приводити до спуску, та, можливо, він
зупиниться тоді, коли будь-який напрямок буде вести до підйому. Місця
зупинок – це і є локальні мінімуми.
• Якщо наявні обмеження у вигляді рівностей – вузькі проходи, - то
спелеолог йде вздовж цих вузьких проходів, поки не досягне найнижчого
місця. Якщо наявні обмеження у вигляді нерівностей – тобто якщо
спелеолог натикається на стіну, то йому треба йти вздовж неї, поки він не
досягне місця, звідки вже всі напрями ведуть вгору. Але спелеолог, який
досяг будь-якого низького місця в печері, не може бути впевнений, що
воно найнижче. Тому методи, які розглянуті, носять локальний характер.
Крім того, треба відмітити, що для використання цих алгоритмів
потрібний значний обсяг апріорної інформації, якого може не бути в
наявності.