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

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

Різновиди алгоритмів оптимізації
У тих випадках, коли поверхні мають різко виражені «яри» і швидкість переміщення до оптимальної мала, замість скаляра вводять матрицю
В цьому випадку величини кроків по різним змінним різні і можуть залежати один від одного.
Таким чином, якщо - постійна матриця, яка не залежить від n, тоді алгоритм оптимізації буде с постійним кроком.
Якщо залежить від n, алгоритм оптимізації буде зі змінним кроком, та інші.
3

Різновиди алгоритмів оптимізації 4
У загальному випадку може залежати від
Ці алгоритми мають назву алгоритми оптимізації з нелінійним кроком.
До цих алгоритмів відносять алгоритми релаксаційного типу, в яких на кожному кроці обирають так, щоб зменшувалась яка-небудь функція помилки .
Релаксаційні алгоритми підрозділяють на координатні,
в яких матриці гама на кожному кроці змінюються так, що на кожному кроці змінюються одна чи кілька компонент вектору , та градієнтні, в яких
(2.12)

Різновиди алгоритмів оптимізації 5
У
- одинична матриця, а - скаляр, який залежить також від координат вектору с.
Так, до алгоритмів з нелінійним кроком можна віднести відомий алгоритм Ньютона
де
До релаксаційних алгоритмів відносять відомий алгоритм найшвидшого спуску
(2.12)

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

Різновиди алгоритмів оптимізації 7
Пошукові алгоритм оптимізації
Компонентами векторів значень функціоналу при зміні значень векторів с:
Тут - скаляр, - базисні вектори.
Наприклад

Різновиди алгоритмів оптимізації 8
Пошукові алгоритм оптимізації
Тоді градієнт можна приблизно оцінювати по формулі
яка визначає так звану роздільну різність. Якщо замінити у наведеному раніше загальнім алгоритмі оптимізації (2.4) градієнт функціоналу його наближеним значенням (2.20), можна отримати пошуковий алгоритм оптимізації
(2.20)

Різновиди алгоритмів оптимізації 9
Методи випадкового пошуку
В усіх регулярних методах пошуку мінімуму для отримання поточної оцінки параметра робиться невипадковий крок, який однозначно визначений або значенням градієнта при ,
або значенням функції
В методах випадкового пошуку при переході від до
здійснюється випадковий крок
де - одиничний випадковий вектор, який частіше за все рівномірно розташований у n-мірній одиничній сфері; - величина кроку. В цьому випадку
(2.45)

Різновиди алгоритмів оптимізації 10
Методи випадкового пошуку
Існують різноманітні модифікації алгоритму (2.45).
В цьому алгоритмі випадковий крок здійснюють тільки в тому випадку, коли в протилежному випадку система залишається в попередньому стані.
В інших алгоритмах, наприклад, «з карою випадковістю», випадковий крок проводять тільки тоді, коли попередній крок був невдалим, і таке інше.
Наприклад, якщо в регулярному градієнтному алгоритмі
величину зробити випадковою, то також отримаємо алгоритм випадкового пошуку:
(2.46)
Тут
- реалізація випадкової величини
Треба підкреслити, що випадковий крок, який не залежить від абсолютного значення градієнта функції чи самої функції, допомагає оминути хоча б деякі неглибокі локальні екстремуми функції.