Найшвидший підйом з використанням одномірного пошуку
В деяких методах пошуку інформація про градієнт використовується для ведення одномірного пошуку в напрямку найшвидшого підйому або спуску, причому використовується співвідношення
,
(3)
де
-
величина кроку, значення якого визначаються
в напрямку градієнта.
Отримавши одномірний оптимум в напрямку даного градієнта, знаходять новий градієнт і повторюють процес до тих пір, поки наступні обчислення дозволяють покращувати отриманий результат. Головна перевага цього метода полягає в тому, що параметр можна використовувати в якості незалежної змінної для пошуку за методом Фібоначчі, і це забезпечує високу ефективність метода. Інша важлива перевага методів, які розглядаються, полягає в тому, що вони дозволяють відходити від сідловин точок поверхні, яка описується цільовою функцією (рис. 1).
Рисунок 1 - Бімодальна цільова функція
Відмітимо, однак, що, як видно з рисунку, для мультимодальних функцій градієнтні методи дозволяють знайти лише локальний оптимум. Тому, якщо характер поверхні недостатньо добре відомий, то слід випробувати декілька початкових точок і переконатися, що в усіх випадках отримується одне й те ж оптимальне рішення. Іншою причиною, яка знижує ефективність градієнтних методів, являються злами ліній рівня цільової функції. Так як такі точки відповідають розриву в нахилі лінії контура, то тут можливі помилки в визначенні напрямку подальшого пошуку. Тому пошук може уповільнитися і іти зигзагами поперек лінії зламу, а час необхідний для отримання рішення, буде на стільки великим, що рахунок прийдеться припинити. В дійсності більшість досліджуємих поверхонь має одну або більше ліній зламу, які нерідко проходять через точку оптимуму. Тому, наткнувшись на лінію зламу, слід в подальшому рухатися вздовж неї.
Метод найшвидшого спуску
Даний метод заснований на використанні ітераційної формули
,
де
,
причому усі похідні обчислюються при
;
- величина кроку, значення якого змінюється (зменшується або обчислюється) методом половинного ділення.
Алгоритм методу найшвидшого спуску:
1.
Обираємо початкові значення координат
вектора
і
початкові значення кроку ітераційного
процесу
,
які звичайно обираються з умов розв’язуємої
конкретної задачі. Хоча загальних правил
вибору
немає,
однак якщо є додаткова інформація про
область розташування мінімуму цільової
функції, то
обираємо
в цій області.
2. Задаємо номер ітерації к = 1.
3. Обчислюємо значення цільової функції в точці з координатами .
4.
Обчислюємо значення градієнта
.
5. Обчислюємо норму вектора градієнта NG.
6. Якщо
|NG| < заданої
,
то ітераційний процес закінчується і
оптимум знайдений.
7. Якщо
умова |NG| <
не
виконується, то визначаються нові
координати вектора
,
які отримуються при русі до мінімуму
цільової функції з кроком
(рис.
14.5).
8.
Порівнюємо два значення цільової функції
в двох точках з координатами векторів
і
за
формулою
,
(4)
Рисунок 2– Послідовність руху до мінімуму з заданим кроком
9. Якщо
умова не виконується, то крок був вибраний
невірно, тобто з цим кроком перескочили
через оптимум і крок потрібно зменшити,
наприклад в два рази
і
переходимо до пункту 7 (рис. 2).
10. Якщо умова (4) виконується, то запам’ятовуємо координати вектора і переходимо до пункту 4.
Схема алгоритму описаного методу представлена на рис. 3.