• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

( 9.9)

В цьому методі напрямок руху до оптимуму (напрямок сходження) одержаний на k + 1 - й ітерації перпендикулярний (ортогональний) до напрямку сходження на k - й ітерації. Таким чином крива руху за методом найшвидшого спуску є ламаною лінією, сусідні ланки якої перпендикулярні між собою, при чому вони є дотичними до поверхонь рівня у відповідних X^k або X^k+1 точках. В даному методі крок зміни параметрів оптимізації 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. проілюстровано зигзагоподібний рух до оптимуму даним методом з повільним сходженням. Рішення таких задач вимагає зміни масштабів змінних або використання методів з похідною другого порядку.

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

1. D) методу мозкового штурму.
2. H) інноваційний менеджмент – це сукупність організаційно-економічних методів управління всіма стадіями інноваційного процесу.
3. I Метод Шеннона-Фано
4. I. Метод рiвних вiдрiзкiв.
5. VII. Нахождение общего решения методом характеристик
6. А. науковий факт, b. гіпотеза, с. метод
7. Автоматизація водорозподілу на відкритих зрошувальних системах. Методи керування водорозподілом. Вимірювання рівня води. Вимірювання витрати.
8. Агрегативна стійкість, коагуляція суспензій. Методи отримання.
9. АгротехнІЧНИЙ метод
10. Адаптовані й специфічні методи дослідження у журналістикознавстві
11. Адміністративні (прямі) методи регулювання.
12. Адміністративні методи - це сукупність прийомів, впливів, заснованих на використанні об'єктивних організаційних відносин між людьми та загальноорганізаційних принципів управління.

Переглядів: 1868