12.1. Градієнтні методи пошуку екстремуму

 

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

Нехай критерій оптимальності  є функцією  змінних , , …,  вектора . Більш лаконічно можна записати, що .

Тоді умова екстремуму набуде вигляду

.      (12.1)

Методи пошуку екстремуму, що ґрунтуються на визначенні градієнта функції , називаються градієнтними.

Пошук екстремуму градієнтними методами містить два етапи:

1) визначення градієнта;

2) рух до екстремуму відповідно до інформації про градієнт.

Розглянемо спочатку методи руху до екстремуму в припущенні, що градієнт обчислений при кожному .

Загальна форма організації руху до екстремуму градієнтними методами зводиться до такої зміни вектора , при якій швидкість зміни параметрів вектора  пов’язана із градієнтом функції  співвідношенням

,                         (12.2)

де  – деяка квадратична -матриця, що залежить від параметрів вектора .

Залежно від вигляду матриці  існує кілька алгоритмів руху до екстремуму.

Алгоритм 1 – метод градієнта.

Це один із найпоширеніших методів градієнтного пошуку екстремуму. Він застосовується, якщо швидкість зміни вектора  пропорційна градієнту від критерію якості:

,                              (12.3)

де  – деякий постійний коефіцієнт, який при пошуку максимуму , при пошуку мінімуму .

У розгорнутому вигляді алгоритм (12.3) можна записати:

,               .                                  (12.4)

При порівнянні (12.4) з (12.2) видно, що , де  – одинична матриця.

Сутність методу градієнта: за заданими параметрами вектора  знаходять градієнт . Потім кожну компоненту вектора  змінюють зі швидкістю, пропорційною складовій градієнта за цією компонентою, і знову визначають градієнт . Операції повторюють, поки не виконається умова (12.1).

Схематично метод градієнта можна зобразити у вигляді рис. 12.1:

При машинних способах пошуку екстремуму метод градієнта реалізується в дискретній формі. У цьому випадку параметри вектора  змінюються стрибкоподібно:

,    =0, 1, 2, …          (12.5)

або в розгорнутому вигляді

,   =0, 1, 2, …,   .   (12.6)

Сутність алгоритму полягає у такому: задається деяке початкове значення  вектора ; у цій точці обчислюють градієнт , і кожна складова вектора  отримує приріст, пропорційний частковій похідній функції  за цією складовою у точці . За формулою (12.5) отримують наступну точку . Далі ті самі дії виконують у точці, отримуючи точку  і т. д.

Обчислення за принципом (12.5) тривають доти, поки при деякому значенні  не будуть виконані умови при пошуку максимуму або мінімуму відповідно:

,                                (12.7)

.                               (12.8)

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

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

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

Цей алгоритм відрізняється від методу градієнта тільки тим, що вектор  змінюється з постійною швидкістю, пропорційною тільки градієнту в заданій початковій точці, а не в кожній точці, як у методі градієнта:

                         (12.9)

або в скалярній формі

,   ,                (12.10)

де .

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

.                                   (12.11)

Якщо умова (12.11) виконується в точці, то цим значенням  замінюють початкову точку  в (12.9) і процес пошуку повторюється, поки не буде отримана умова (12.1):

.                            (12.12)

Хоча метод найшвидшого спуску є багатоцикловим, (спочатку шукається точка , у якій виконується умова (12.11), а потім умова (12.12)), але в межах одного циклу градієнт обчислюється тільки один раз – на початку циклу.

У дискретній формі рух у межах циклу здійснюється покроково:

,   =0, 1, 2, …      (12.13)

Аналогічно методу градієнта цикл пошуку  триває доти, поки не виконається одна з умов (12.7) або (12.8). При досягненні умов (12.7) або (12.8) точці  надається значення  і цикл повторюється, але при іншому значенні аргументу функції , тобто

,  ,,, …    (12.14)

Тут видно, що в кожному циклі буде свій крок, пропорційний .

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

Алгоритм III – узагальнений метод Ньютона.

У багатьох практичних задачах швидше можна досягти екстремуму в (12.2), якщо за матрицю  використовувати від’ємну зворотну матрицю других похідних від функції  за :

.                        (12.15)

У цьому випадку алгоритм руху до екстремуму називається узагальненим методом Ньютона, а матриця других похідних (12.15) – матрицею Гессе або гессіаном.

Тоді алгоритм руху до екстремуму (12.2) набуде вигляду

            (12.16)

або в дискретній формі

,  =0, 1, 2, …  (12.17)

Сутність узагальненого методу Ньютона аналогічна методу градієнта, але за умови, що  не є константою.

Алгоритм IV – метод Гауса-Зайделя.

Складністю I – III алгоритмів є те, що екстремум шукається при аргументах функції , що змінюються одночасно.

У методі Гауса-Зайделя спочатку визначаються екстремальні значення функції , змінюючи тільки аргумент , використовуючи метод градієнта, тобто формули (12.4) та (12.6) набудуть вигляду

,

, =0, 1, 2, …

Після визначення екстремального значення аргументу  функції , для якої виконуються умови (12.1) (при безперервному пошуку) або (12.7), (12.8) (при кроковому пошуку), за такою ж методикою визначається екстремальне значення аргументу  при незмінних , , ..., . Потім змінюють аргумент  і т. д. послідовно до змінної . Після цього весь цикл пошуку повторюють, знову починаючи з , і так доти, поки не будуть виконуватися умови (12.1) або (12.7), (12.8).