Градієнтний метод найшвидшого спуску

В попередньому методі для всіх ітерацій вибирався постійний крок, який забезпечував рух до мінімуму цільової функції. Звичайно, що цей крок був дуже малим і, щоб досягти мінімуму, потрібно було зробити багато ітерацій. Через те ті методи, які працюють із змінним кроком, є більш економними в кількості ітерацій. Градієнтний метод пошуку мінімуму в якому на кожній ітерації крок h^k вибирається із умови мінімуму функції F(X) в напрямку рух називається методом найшвидшого спуску. Цю умову можна записати так:

( 9.9)

В цьому методі напрямок руху до оптимуму (напрямок сходження) одержаний на k + 1 - й ітерації перпендикулярний (ортогональний) до напрямку сходження на k - й ітерації. Таким чином крива руху за методом найшвидшого спуску є ламаною лінією, сусідні ланки якої перпендикулярні між собою, при чому вони є дотичними до поверхонь рівня у відповідних X^k або X^k⁺¹ точках. В даному методі крок зміни параметрів оптимізації h^k на кожній ітерації вибирається за допомогою розв’язування допоміжної задачі одновимірної оптимізації або іншим шляхом наприклад по формулі:

(9.10)

де h – початкове значення кроку, а знаменник виразу – норма вектора градієнту цільової функції в k – й точці.

Схема алгоритму даного методу показана на рис. 9.3. В даному алгоритмі, як і в попередньому методі вводяться: початкова точка пошуку, вектор на n параметрів X⁰, початкове значення кроку h > 0, точність обчислень оптимального значення цільової функції e > 0, максимально допустиме число ітерацій k_m > 1, підпрограми обчислення цільової функції F(X) і градієнту цільової функції G(X) і крім цього точність обчислень оптимального кроку h^kна k – тій ітерації e_о > 0 , підпрограма – функція обчислення оптимального кроку НН.

Оптимальне значення кроку вираховується в напрямку руху до оптимуму (мінімуму) одним із методів однопараметричної оптимізації ( блок 7). Величина кроку повинна зменшуватись при наближенні до оптимуму. Знайшовши нову точку пошуку аналогічно попередньому алгоритму перевіряється досягнення оптимуму по одній із формул, наприклад (9.8) блок 11, і досягнення лічильником ітерацій k свого максимально допустимого значення k_m, блок 12.

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

Рис. 9.3. Схема алгоритму визначення оптимального значення цільової функції градієнтним методом найшвидшого спуску

Приведемо для прикладу схему алгоритму знаходження оптимального кроку h^k на кожній ітерації методом ділення відрізка пополам (рис. 9.4). В блок схемі підпрограми-функції методу на вхід поступають координати поточної точки, a₀, b₀, c₀, значення градієнту цільової функції в цій точці GA, GB, GC, початковий крок h, точність обчислення кроку e_о, цільова функція F(X), блок 1.

Рис. 9.4. Схема алгоритму знаходження оптимального кроку пошуку в градієнтному методі найшвидшого спуску методом ділення відрізка пополам

В блока 2 – 8 в результаті виконання і – тих кроків руху до мінімуму знаходиться інтервал зміни кроку, де є оптимум. Цей інтервал ha – hb. При пошуку цього інтервалу в напрямку градієнта початковий крок вибирався по формулі (9.10), де S знаходилось в блоці 2 по формулі:

(9.11)

В блоках 9 – 17 на інтервалі ha – hb по відомому методу одно параметричної оптимізації діленням відрізку пополам знаходиться оптимальне значення кроку h.

Рис. 9.5. Зигзагоподібна траєкторія руху до оптимуму методом найшвидшого спуску у вузькому яру

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Градієнтний метод із дробленням кроку	\|	Розв’язок задачі

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.