Моделювання в електроенергетиці - Безумовна оптимізація
Безумовна оптимізація. Метод сполучених градієнтів
Метод сполучених градієнтів (в англ. Літературі «conjugate gradient method») - це ітераційний чисельний метод (першого порядку) вирішення оптимізаційних завдань, який дозволяє визначити екстремум (мінімум або максимум) цільової функції:
- Це значення аргументу функції (керовані параметри) на речовій області.
Відповідно до аналізованого методом екстремум (максимум чи мінімум) цільової функції визначають у бік найбільш швидкого зростання (зменшення) функції, тобто. у напрямі градієнта (антиградієнта) функції. Градієнтом функції у точці називається вектор, проекціями якого координатні осі є приватні похідні функції по координатам:
де i, j, ..., n - Поодинокі вектори, паралельні координатним осям.
Градієнт у базовій точці суворо ортогональний до поверхні, яке напрямок показує напрямок якнайшвидшого зростання функції, а протилежний напрямок (антиградіент), відповідно, показує напрямок якнайшвидшого зменшення функції.
Метод сполучених градієнтів є подальшим розвитком методу якнайшвидшого спуску, який поєднує в собі два поняття: градієнт цільової функції та сполучений напрямок векторів. У загальному випадку процес знаходження мінімуму функції є ітераційною процедурою, яка записується у векторній формі таким чином:
де знак "+" використовується для пошуку максимуму функції, а знак "-" використовується для пошуку мінімуму функції.
- одиничний вектор сполучених напрямків, що визначається за формулою:
Існує кілька способів визначення значень вагових коефіцієнтів (змінна),які використовуються для визначення сполученого напрямку.
Як перший спосіб розглядають визначення вагового коефіцієнта за формулою Флетчера-Рівса (Fletcher-Reeves):
- модуль градієнта визначає швидкість зростання або зменшення функції в напрямку градієнта або антиградієнта відповідно.
Як другий спосіб розглядають визначення вагового коефіцієнта за формулою Полака-Райбера (Polak-Ribiere):
Відповідно до представлених виразів новий сполучений напрямок виходить додаванням градієнта (антиградіенту) в точці повороту і попереднього напрямку руху, помноженого на коефіцієнт. Таким чином, метод сполучених градієнтів формує напрямок пошуку до оптимального значення використовуючи інформацію про пошук, отриману на попередніх етапах спуску. Слід зазначити, що пов'язані напрями P[0], P[1], . P[k-1] обчислюють за допомогою формули Флетчера-Рівса, яка дозволяє побудувати сполучені вектори щодо деякої симетричної матриці для довільно заданої функції.
Рис.1. Траєкторія спуску у методі сполучених градієнтів (пошук мінімуму)
Геометричний зміст методу сполучених градієнтів полягає в наступному: із заданої початкової точки х[0] здійснюється спуск у напрямку р[0] (градієнта або антиградієнта) у нову точку х[1], в якій визначається вектор-градієнт функції. Оскільки х[1] є точкою мінімуму функції у напрямку р[0], то вектор-градієнт функції у точці х[1] ортогональний вектору р[0]. Потім визначається вектор р[1] який ортогональний щодо деякої симетричної матриці вектору р[0]. У результаті здійснюється спуск уздовж знайденого напрямку нову точку х[2].
Рис.2. Траєкторія руху до точкиекстремуму при використанні методу якнайшвидшого спуску (зелена ламана) та методу сполучених градієнтів (червона ламана).
Слід зазначити, що через кожний n + 1 крок необхідно виконувати рестарт алгоритмічної процедури (n – розмірність простору пошуку). Рестарт алгоритмічної процедури необхідний, щоб забути останній напрямок пошуку та стартувати алгоритм заново у напрямку якнайшвидшого спуску.
Величина кроку вибирається з умови мінімуму цільової функції f(х) у напрямку руху, тобто в результаті вирішення задачі одновимірної оптимізації в напрямку градієнта або антиградієнта:
Іншими словами, величину кроку визначають при вирішенні даного рівняння:
Пошук оптимального рішення завершується у разі, коли на ітераційному етапі розрахунку (кілька критеріїв):
- траєкторія пошуку залишається в малій околиці поточної точки пошуку:
- Збільшення цільової функції не змінюється:
- градієнт цільової функції в точці локального мінімуму перетворюється на нуль:
Метод сполучених градієнтів є методом першого порядку, але при цьому має квадратичну швидкість збіжності, як Ньютонівські методи розрахунку. p align="justify"> Метод градієнта разом з його численними модифікаціями є поширеним і ефективним методом пошуку оптимуму досліджуваних об'єктів. Недоліком градієнтного пошуку (і розглянутих вище методів) і те, що з його використанні можна знайти лише локальний екстремум функції. Для пошуку інших локальних екстремумів потрібно проводити пошук з інших початкових точок.
Методика розрахунку
•1 крок: Визначення аналітичних виразів (у символьному вигляді) для обчислення градієнта функції
• 2 крок : Задаємо початковенаближення
Далі виконується ітераційний процес.
•3 крок: Визначається необхідність рестарту алгоритмічної процедури для обнулення останнього напряму пошуку. В результаті рестарту пошук здійснюється заново у напрямку якнайшвидшого спуску.
•4 крок : Обчислення координат одиничного вектора за формулою, отриманою на кроці 1, та визначення координат нової точки під час руху за напрямком одиничного вектора як функція від кроку розрахунку.
Обчислення вагового коефіцієнта та одиничного вектора сполучених напрямків на поточному кроці розрахунку (формула Флетчера-Рівса):
- для першого кроку розрахунку ваговий коефіцієнт не обчислюється (або у разі рестарту алгоритму), а одиничний вектор сполучених напрямків визначається так:
- для наступних кроків розрахунку ваговий коефіцієнт та одиничний вектор сполучених напрямів обчислюються за такими співвідношеннями:
•5 крок : визначаємо крок розрахунку з умови пошуку екстремуму для наступної функції (вирішення задачі одновимірної оптимізації).
•6 крок : Визначаємо нові значення аргументів функції після виконання k-го кроку розрахунку:
де знак "+" використовується для пошуку максимуму функції, а знак "-" використовується для пошуку мінімуму функції;
•7 крок: перевіряємо критерії зупинки ітераційного процесу. Обчислювальний процес закінчується, коли буде досягнуто точка, в якій оцінка градієнта дорівнюватиме нулю (коефіцієнти функції відгуку стають незначними). В іншому випадку повертаємось до кроку 3 і продовжуємо ітераційний розрахунок.