14.3.1 Найшвидший підйом з використанням одномірного пошуку

В деяких методах пошуку інформація про градієнт використовується для ведення одномірного пошуку в напрямку найшвидшого підйому або спуску, причому використовується співвідношення

     ,     (14.18)

де - величина кроку, значення якого визначаються в напрямку градієнта.

Отримавши одномірний оптимум в напрямку даного градієнта, знаходять новий градієнт і повторюють процес до тих пір, поки наступні обчислення дозволяють покращувати отриманий результат. Головна перевага цього метода полягає в тому, що параметр можна використовувати в якості незалежної змінної для пошуку за методом Фібоначчі, і це забезпечує високу ефективність метода. Інша важлива перевага методів, які розглядаються, полягає в тому, що вони дозволяють відходити від сідловин точок поверхні, яка описується цільовою функцією (рис. 14.4).

    

     Рисунок 14.4 - Бімодальна цільова функція

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

14.3.2 Метод найшвидшого спуску

Даний метод заснований на використанні ітераційної формули

,

де , причому усі похідні обчислюються при ;

- величина кроку, значення якого змінюється (зменшується або обчислюється) методом половинного ділення.

Алгоритм методу найшвидшого спуску:

1. Обираємо початкові значення координат вектора і початкові значення кроку ітераційного процесу , які звичайно обираються з умов розв’язуємої конкретної задачі. Хоча загальних правил вибору немає, однак якщо є додаткова інформація про область розташування мінімуму цільової функції, то обираємо в цій області.

2. Задаємо номер ітерації к = 1.

3. Обчислюємо значення цільової функції в точці з координатами .

4. Обчислюємо значення градієнта .

5. Обчислюємо норму вектора градієнта NG.

6. Якщо |NG| < заданої , то ітераційний процес закінчується і оптимум знайдений.

7. Якщо умова |NG| < не виконується, то визначаються нові координати вектора , які отримуються при русі до мінімуму цільової функції з кроком (рис. 14.5).

8. Порівнюємо два значення цільової функції в двох точках з координатами векторів і за формулою

    

          Рисунок 14.5– Послідовність руху до мінімуму з заданим кроком

     ,     (14.31)

9. Якщо умова не виконується, то крок був вибраний невірно, тобто з цим кроком перескочили через оптимум і крок потрібно зменшити, наприклад в два рази і переходимо до пункту 7 (рис. 14.5).

10. Якщо умова (14.31) виконується, то запам’ятовуємо координати вектора і переходимо до пункту 4.

Схема алгоритму описаного методу представлена на рис. 14.6.