Метод якнайшвидшого спуску. Градієнтний спуск
Метод якнайшвидшого спускує градієнтним методом із змінним кроком. На кожній ітерації величина кроку k вибирається з умови мінімуму функції f(x) у бік спуску, тобто.
Ця умова означає, що рух уздовж антиградієнта відбувається доти, доки значення функції f (x) зменшується. З математичної точки зору на кожній ітерації необхідно вирішувати завдання одномірної мінімізації за функцією
() = f (x (k) -f (x (k)))
Скористайтеся при цьому методом золотого перерізу.
Алгоритм методу якнайшвидшого спуску полягає в наступному.
Визначаються координати початкової точки x (0) .
У точці x (k), k = 0, 1, 2, …, обчислюється значення градієнта f (x (k)).
Визначається величина кроку k шляхом одномірної мінімізації за функцією
()=f(x(k)-f(x(k))).
Визначаються координати точки x (k):
x i (k+1) = x i (k) - k f i (x (k)), i = 1, …, n.
Перевіряється умова зупинки ітераційного процесу:
||f(x(k+1))|| .
Якщо воно виконується, то обчислення припиняються. В іншому випадку здійснюється перехід до п. 1. Геометрична інтерпретація методу якнайшвидшого спуску представлена на рис. 1.
Рис. 2.1. Блок схема методу якнайшвидшого спуску.
Реалізація методу у програмі:
Метод якнайшвидшого спуску.
Рис. 2.2. Реалізація способу якнайшвидшого спуску.
Висновок: У нашому випадку спосіб зійшовся за 7 ітерацій. Крапка А7 (0,6641; -1,3313) є точкою екстремуму. Метод сполучених напрямів. Для квадратичних функцій можна створити градієнтний метод, при якому час збіжності буде кінцевим і дорівнює кількості змінних n.
Назвемо деякий напрямок і сполученими стосовно деякої позитивно визначеної матриці ГессаH, якщо виконується:
Тоді тобто. Значить при одиничній H, сполучений напрямок означає їх перпендикуляр. У загальному випадку H непоодинока. У загальному випадкуСполученість - це застосування матриці Гесса до вектора - означає поворот цього вектора на деякий кут його розтяг або стиснення.
А тепер вектору векторортогонален т. е. сполученість це не ортогональність вектора, а ортогональність повернутого векторат.е.і.
Рис. 2.3. Блок-схема методу сполучених напрямів.
Реалізація методу у програмі: Метод сполучених напрямків.
Рис. 2.4. Реалізація методу пов'язаних напрямів.
Рис. 2.5. Графік методу сполучених напрямів.
Висновок: Точка А3 (0,6666; -1,3333) була знайдена за 3 ітерації і є точкою екстремуму.
3. Аналіз методів визначення мінімального, максимального значення функції за наявності обмежень
Нагадаємо, що загальне завдання умовної оптимізації виглядає так
f(x) ® min, x Î W,
де W - власне підмножина R m. Підклас завдань з обмеженнями типу рівностей виділяється тим, що безліч задається обмеженнями виду
f i (x) = 0, де fi: R m ®R (i = 1, …, k).
Таким чином, W = (x R m: f i (x) = 0, i = 1, …, k).
Нам буде зручно писати у функції f індекс "0". Таким чином, завдання оптимізації з обмеженнями типу рівностей записується у вигляді
f 0 (x) ® min, (3.1)
f i (x) = 0, i = 1, …, k. (3.2)
Якщо позначити тепер через f функцію на R m зі значеннями R k , координатний запис якої має вигляд f(x) = (f 1 (x), …, f k (x)), то (3.1)–(3.2)можна також записати у вигляді
f 0 (x) min, f(x) = Q.
Геометрично завдання з обмеженнями типу рівностей - це завдання пошуку найнижчої точки графіка функції f 0 над різноманіттям (див. рис. 3.1).
Точки, що задовольняють усім обмеженням (тобто точки множини ), зазвичай називають допустимими. Допустима точка x* називається умовним мінімумом функції f 0 при обмеженнях f i (x) = 0, i = 1, ..., k (або розв'язанням задачі (3.1)–(3.2)), якщо при всіх допустимих точках x f 0 (x *) f 0 (x). (3.3)
Якщо (3.3) виконується тільки для допустимих x, що лежать в околиці V x * точки x *, то говорять про локальний умовний мінімум. Природно визначаються поняття умовних суворих локального та глобального мінімумів.
Постановка задачі
Нехай дана функція f(х) R n
Потрібно f(х) X = R n
Стратегія пошуку
x k
} , k = 0,1,...,
таких, що 
, k = 0,1,...
. Точки послідовності ( x k
) обчислюються за правилом
де точка х 0 задається користувачем; величина кроку t k визначається для кожного значення k з умови
Розв'язання задачі (3) може здійснюватися з використанням необхідної умови мінімуму з подальшою перевіркою достатньої умови мінімуму. Такий шлях може бути використаний або за досить простої мінімізованої функції, або за попередньої апроксимації достатньо складної функції 
поліномом P(t k)
(як правило, другого або третього ступеня), і тоді умова заміщується умовою , а умова умовою 
Побудова послідовності ( x k )
закінчується в точці x k
, для якої , де ε
- задане мале позитивне число, або k ≥ M
, де М
- гранична кількість ітерацій, або при дворазовому одночасному виконанні двох нерівностей 
, 
де ε 2
- мале позитивне число. Питання, чи може точка x k
розглядатися як знайдене наближення шуканої точки локального мінімуму x *
, Вирішується шляхом додаткового дослідження.
Геометрична інтерпретація методу для n=2 на рис. 4.
Метод покоординатного спуску
Постановка задачі
Нехай дана функція f(х) , обмежена знизу на безлічі R n і має безперервні приватні похідні у всіх його точках.
f(х) на безлічі допустимих рішень X = R n , тобто. знайти таку точку, що
Стратегія пошуку
Стратегія розв'язання задачі полягає у побудові послідовності точок ( x k
} , k = 0,1,...,
таких, що , k = 0,1,...
. Точки послідовності ( x k
) обчислюються за циклами відповідно до правила
(4)
де j - Номер циклу обчислень; j = 0,1,2,...; k - Номер ітерації всередині циклу, k = 0,1, ..., n - 1; е k +1, k = 0, l, ..., n - 1 -поодинокий вектор, (k +1) -я проекція якого дорівнює 1; крапка х 00 задається користувачем, величина кроку t k вибирається з умови
або 
.
Якщо вибрана умова при поточному t k
не виконується, крок зменшується вдвічі і крапка 
обчислюється заново. Легко бачити, що за фіксованого j за одну ітерацію з номером k
змінюється лише одна проекція точки х jk
, що має номер k + 1
, а протягом всього циклу з номером j
, тобто. починаючи з k = 0
і закінчуючи k = n -1
, змінюються всі проекцій точки х j0
. Після цього точці х j n
присвоюється номер х j + 1,0
, і вона береться за початкову точку для обчислень у j + 1
циклі. Розрахунок закінчується у точці х jk
при виконанні по Крайній міріодного з трьох критеріїв закінчення рахунку: 
, або двократного виконання нерівностей .
Отримані в результаті обчислень точки можуть бути записані як елементи послідовності (х l), де l=n*j+k - Порядковий номер точки,
Геометрична інтерпретація методу для п = 2 наведено на рис. 5.
4. Метод Франка-Вулфа .
Нехай потрібно знайти максимальне значення увігнутої функції
За умов
Характерною особливістюцієї задачі є те, що її система обмежень містить лише лінійні нерівності. Ця особливість є основою для заміни в околиці досліджуваної точки нелінійної цільової функції лінійної, завдяки чому рішення вихідного завдання зводиться до послідовному рішеннюзадач лінійного програмування
Процес знаходження рішення задачі починають з визначення точки, що належить області допустимих розв'язків.
270
дачі. Нехай це точка X(k)
тоді у цій точці обчислюють градієнт функції (57)
І будують лінійну функцію
Потім знаходять максимальне значення цієї функції при обмеженнях (58) та (59). Нехай вирішення цього завдання визначається точкою Z(k)
. Тоді за нове допустиме вирішення вихідного завдання приймають координати точки X (k+1)
:
Де λ k - деяке число, зване кроком обчислень і укладене між нулем та одиницею (0<λ k < 1). Это число λ k беруть довільно або визначають
таким чином, щоб значення функції у точці X(k+1) f(X(k+1)) , що залежить від λ k , було максимальним. Для цього необхідно знайти рішення рівняння та вибрати його найменший корінь. Якщо його значення більше одиниці, слід покласти λ k=1 . Після визначення числа λ k знаходять координати точки X (k+1) обчислюють значення цільової функції в ній та з'ясовують необхідність переходу до нової точки X (k+2) . Якщо така необхідність є, то обчислюють у точці X (k+1) градієнт цільової функції, переходять до відповідної задачі лінійного програмування та знаходять її розв'язання. Визначають координати точки та X (k+2) та досліджують необхідність проведення подальших обчислень. Після кінцевого числа кроків одержують із необхідною точністю рішення вихідної задачі.
Отже, процес знаходження рішення задачі (57) - (59) методом Франка-Вулфа включає наступні етапи:
1. Визначають вихідне допустиме розв'язання задачі.
2. Знаходять градієнт функції (57) у точці допустимого рішення.
3. Будують функцію (60) та знаходять її максимальне значення за умов (58) та (59).
4. Визначають крок обчислень.
5. За формулами (61) знаходять компоненти нового припустимого рішення.
6. Перевіряють необхідність переходу до наступного допустимого рішення. У разі необхідності переходять до етапу 2, інакше знайдено прийнятне рішення вихідного завдання.
Спосіб штрафних функцій.
Розглянемо задачу визначення максимального значення увігнутої функції
f (х 1, х 2, .... х n)за умов g i (х 1, х 2, .... х n) ≤ b i (i=l, m) , х j ≥ 0 (j=1, n) , де g i (х 1, х 2, .... х n) - опуклі функції.
Замість безпосередньо вирішувати це завдання, знаходять максимальне значення функції F(х 1, х 2, ...., х n) = f(х 1, х 2, ...., х n) +H(х 1, х 2, ...., х n) є сумою цільової функції завдання, та деякої функції
H(х 1, х 2, ...., х n), яка визначається системою обмежень і називається штрафною функцією. Штрафну функцію можна побудувати у різний спосіб. Однак найчастіше вона має вигляд
А a i > 0
- деякі постійні числа, що є ваговими коефіцієнтами.
Використовуючи штрафну функцію, послідовно переходять від однієї точки до іншої, доки не отримають прийнятне рішення. При цьому координати наступної точки знаходять за формулою
З останнього співвідношення випливає, що якщо попередня точка знаходиться в області допустимих рішень вихідної задачі, друге доданок в квадратних дужках дорівнює нулю і перехід до наступної точки визначається тільки градієнтом цільової функції. Якщо ж зазначена точка не належить до області допустимих рішень, то за рахунок даного доданку на наступних ітераціях досягається повернення в область допустимих рішень.
рішень. При цьому чим менше a i
тим швидше знаходиться прийнятне рішення, проте точність визначення його знижується. Тому ітераційний процес зазвичай починають при порівняно малих значеннях a i
і, продовжуючи її, ці значення поступово збільшують.
Отже, процес знаходження рішення задачі опуклого програмування методом штрафних функцій включає такі етапи:
1. Визначають вихідне припустиме рішення.
2. Вибирають крок обчислень.
3. Знаходять по всіх змінних приватні похідні від цільової функції та функцій, що визначають область допустимих розв'язків задачі.
4. За формулою (72) знаходять координати точки, що визначає можливе нове рішення задачі.
5. Перевіряють, чи задовольняють координати знайденої точки системі обмежень задачі. Якщо ні, то переходять до наступного етапу. Якщо координати знайденої точки визначають припустиме розв'язання задачі, то досліджують необхідність переходу до наступного припустимого рішення. У разі такої необхідності переходять до етапу 2, інакше знайдено прийнятне рішення вихідної задачі.
6. Встановлюють значення вагових коефіцієнтів та переходять до етапу 4.
Метод Ерроу – Гурвіца.
При знаходженні розв'язання задач нелінійного програмуванняметодом штрафних функцій ми вибирали значення a i , Довільно, що призводило до значних коливань віддаленості визначених точок від області допустимих рішень. Цей недолік усувається під час вирішення завдання методом Ерроу - Гурвіца, згідно з яким на черговому кроці числа a i (k) обчислюють за формулою
Як початкові значення a i (0) беруть довільні невід'ємні числа.
ПРИКЛАД РІШЕННЯ
Приклад 1.
Знайти локальний мінімум функції
Визначення точки х k
1. Задамо.
2. Покладемо до = 0 .
3 0 . Обчислимо
4 0 . Обчислимо 
. Переходимо до кроку 5.
5 0 . Перевіримо умову 
. Переходимо до кроку 6.
6 0 . Задамо t 0 = 0,5 .
7 0 . Обчислимо
8 0 . Порівняємо 
. Маємо 
. Висновок: умова для k = 0
не виконується. Задамо t 0 = 0,25
, Переходимо до повторення кроків 7, 8.
7 01 . Обчислимо.
8 01 . Порівняємо f (х 1) та f (х 0) . Висновок: f (x 1)< f (x 0) . Переходимо до кроку 9.
9 0 . Обчислимо
Висновок: гадаємо k =1 та переходимо до кроку 3.
3 1 . Обчислимо
4 1 . Обчислимо 
. Переходимо до кроку 5.
5 1 . Перевіримо умову k ≥ M: k = 1< 10 = M . Переходимо до кроку 6.
6 1 . Задамо t1 = 0,25.
7 1 . Обчислимо
8 1 . Порівняємо f(х2) з f(х1) . Висновок: f (х 2)< f (х 1). Переходимо до кроку 9.
9 1 . Обчислимо
Висновок: гадаємо k = 2 та переходимо до кроку 3.
3 2 . Обчислимо
4 2 . Обчислимо. Переходимо до кроку 5.
5 2 . Перевіримо умову k ≥ M : k = 2< 10 = М , Переходимо до кроку 6.
6 2 . Задамо t 2 =0,25 .
7 2 . Обчислимо
8 2 . Порівняємо f (х 3) і f (х 2) . Висновок: f (х 3)< f (х 2) .Переходимо до кроку 9.
9 2 . Обчислимо 
Висновок: гадаємо k = 3 та переходимо до кроку 3.
3 3 . Обчислимо
4 3 . Обчислимо. Переходимо до кроку 5.
5 3 . Перевіримо умову k ≥ M : k = 3<10 = М , Переходимо до кроку 6.
6 3 . Задамо t3 = 0,25.
7 3 . Обчислимо
8 3 . Порівняємо f (х 4) і f (х 3): f (х 4)< f (х 3) .
9 3 . Обчислимо 
Умови виконані при k = 2,3 . Розрахунок
закінчено. Знайдено крапку
На рис. 3 отримані точки з'єднані пунктирною лінією.
ІІ. Аналіз точки х 4 .
Функція 
є двічі диференційованою, тому проведемо перевірку достатніх умов мінімуму у точці х 4
. Для цього проаналізуємо матрицю Гессе.
Матриця стала і є позитивно визначеною (тобто . H> 0
) , оскільки обидва її кутові мінори і позитивні. Отже, точка 
є знайдене наближення точки локального мінімуму, а значення 
є знайдене наближення значення f (x *) = 0
. Зауважимо, що умова H> 0
, є одночасно умова суворої опуклості функції 
. Отже, є знайдені наближення точки глобального мінімуму f(x)
та її найменшого значення на R 2
. ■
Приклад 2
Знайти локальний мінімум функції
I. Визначення точки х k, в якій виконано принаймні один із критеріїв закінчення розрахунків.
1. Задамо.
Знайдемо градієнт функції у довільній точці
2. Покладемо до = 0 .
3 0 . Обчислимо
4 0 . Обчислимо . Переходимо до кроку 5.
5 0 . Перевіримо умову 
. Переходимо до кроку 6.
6°. Наступна точка знаходиться за формулою
Підставимо отримані вирази для координат
Знайдемо мінімум функції f(t 0) по t 0 за допомогою необхідних умов безумовного екстремуму:
Звідси t 0 =0.24
. Так як 
, знайдене значення кроку забезпечує мінімум функції f(t 0)
по t 0
.
Визначимо 
7 0 . Знайдемо
8 °. Обчислимо
Висновок: гадаємо k = 1 та переходимо до кроку 3.
3 1 . Обчислимо
4 1 . Обчислимо 
5 1 . Перевіримо умову k ≥ 1: k = 1< 10 = М.
6 1 . Визначимо
7 1 . Знайдемо 
:
8 1 . Обчислимо
Вважаємо k = 2 та переходимо до кроку 3.
3 2 . Обчислимо
4 2 . Обчислимо
5 2 . Перевіримо умову k ≥ M: k = 2< 10 = M .
6 2 . Визначимо
7 2 . Знайдемо 
8 2 . Обчислимо
Вважаємо k =3 та переходимо до кроку 3.
3 3 . Обчислимо
4 3 . Обчислимо.
Розрахунок закінчено. Знайдено крапку
ІІ. Аналіз точки х 3 .
У прикладі 1.1 (гл.2 §1) було показано, що функція f(x) є строго опуклою і, отже, точках3 є знайденим наближенням точки глобального мінімуму х* .
приклад 3.
Знайти локальний мінімум функції
I. Визначення точки x jk , в якій виконано принаймні один із критеріїв закінчення розрахунків.
1. Задамо
Знайдемо градієнт функції у довільній точці 
2. Задамо j = 0.
3 0 . Перевіримо виконання умови
4 0 . Задамо k = 0.
5 0 . Перевіримо виконання умови
6 0 . Обчислимо
7 0 . Перевіримо умову 
8 0 . Задамо
9 0 . Обчислимо 
, де
10 0 . Перевіримо умову
Висновок: думаємо та переходимо до кроку 9.
9 01 . Обчислимо х 01 з кроком
10 01 . Перевіримо умову 
11 0 . Перевіримо умови
Вважаємо k =1 та переходимо до кроку 5.
5 1 . Перевіримо умову
6 1 . Обчислимо
7 1 . Перевіримо умову
8 1 . Задамо
9 1 . Обчислимо
10 1 . Перевіримо умову 
:
11 1 . Перевіримо умови
Вважаємо k = 2 , Переходимо до кроку 5.
5 2 . Перевіримо умову. Задамо, переходимо до кроку 3.
3 1 . Перевіримо умову
4 1 . Задамо k = 0.
5 2 . Перевіримо умову
6 2 . Обчислимо
7 2 . Перевіримо умову
8 2 . Задамо
9 2 . Обчислимо
10 2 . Перевіримо умову 
11 2 . Перевіримо умови
Вважаємо k =1 та переходимо до кроку 5.
5 3 . Перевіримо умову
6 3 . Обчислимо
7 3 . Перевіримо умови
8 3 . Задамо
9 3 . Обчислимо
10 3 . Перевіримо умову 
11 3 . Перевіримо умови
Задамо k = 2 та переходимо до кроку 5.
5 4 . Перевіримо умову 
Вважаємо j = 2, х 20 = х 12 та переходимо до кроку 3.
3 2 . Перевіримо умову
4 2 . Задамо k =0 .
5 4 . Перевіримо умову
6 4 . Обчислимо
7 4 . Перевіримо умову
8 4 . Задамо
9 4 . Обчислимо
10 4 . Перевіримо умову перейдемо до кроку 11.
11 4 . Перевіримо умови
Умови виконані у двох послідовних циклах із номерами j = 2 і j -1 = 1 . Розрахунок закінчено, знайдено точку
На рис. 6 отримані точки з'єднані пунктирною лінією.
У методі покоординатного спуску ми спускаємося ламаною, що складається з відрізків прямих, паралельних координатним осям.
ІІ. Аналіз точки х21.
У прикладі 1.1 показано, що функція f(х)
суворо випукла, має єдиний мінімум і, отже, точка 
є знайденим наближенням точки глобального мінімуму.
У всіх розглянутих вище градієнтних методах послідовність точок. ( x k ) сходиться до стаціонарної точки функції f(x) за досить загальних пропозицій щодо властивостей цієї функції. Зокрема, справедлива теорема:
Теорема. Якщо функція f (x) обмежена знизу, її градієнт задовольняє умові Липшиця () та вибір значення t n проводиться одним з описаних вище способів, то, якою б не була початкова точка х 0 :
при .
За практичної реалізації схеми
k =1, 2, … n.
ітерації припиняються, якщо всім i, i = 1, 2, ..., n , виконані умови типу
,
де - Деяке задане число, що характеризує точність знаходження мінімуму.
В умовах теореми градієнтний метод забезпечує збіжність за функцією або до точної нижньої грані (якщо функція f(х) не має мінімуму; Рис. 7), або до значення функції в певній стаціонарній точці, що є межею послідовності (х до). Неважко вигадати приклади, коли в цій точці реалізується сідло, а не мінімум. Насправді методи градієнтного спуску впевнено обходять сідлові точки і знаходять мінімуми цільової функції (загалом - локальні).
ВИСНОВОК
Вище було розглянуто приклади градієнтних методів безумовної оптимізації. В результаті виконаної роботи можна зробити такі висновки:
1. Більш менш складні завдання відшукання екстремуму за наявності обмежень вимагають спеціальних підходів, методів.
2. Багато алгоритмів вирішення завдань з обмеженнями включають мінімізацію без обмежень як певний етап.
3. Різні методиспуску відрізняються один від одного способами вибору напрямку спуску та довжини кроку вздовж цього напрямку.
4. Немає поки що такої теорії, яка врахувала б будь-які особливості функцій, що описують постановку завдання. Слід віддавати перевагу таким методам, якими простіше керувати у процесі вирішення задачі.
Реальні прикладні завдання оптимізації складні. Сучасні методиоптимізації які завжди справляються з вирішенням реальних завдань без допомоги людини.
СПИСОК ЛІТЕРАТУРИ
1. Косоруков О.А. Дослідження операцій: підручник. 2003
2. Пантлєєв А.В. Методи оптимізації в прикладах та завданнях: навч. Допомога. 2005
3. Шишкін Є.В. Дослідження операцій: навч. 2006
4. Акуліч І.Л. Математичне програмування в прикладах та задачах. 1986
5. Вентцель Є.С. Дослідження операцій. 1980
6. Вентцель Є.С., Овчаров Л.А. Теорія ймовірностей та її інженерні програми. 1988
©2015-2019 сайт
Усі права належати їх авторам. Цей сайт не претендує на авторства, а надає безкоштовне використання.
Дата створення сторінки: 2017-07-02
Градієнтом диференційованої функції f(x) у точці хназивається n-мірний вектор f(x) , компоненти якого є приватними похідними функції f(х),обчисленими у точці х, тобто.
f"(x ) = (дf(х)/дх 1 , …, дf(х)/дх n) T.
Цей вектор перпендикулярний до площини, проведеної через точку. х, та дотичної до поверхні рівня функції f(x),проходить через точку х.У кожній точці такої поверхні функція f(x)набуває однакового значення. Прирівнюючи функцію різним постійним величинам 0 , 1 , ... , отримаємо серію поверхонь, що характеризують її топологію (Рис. 2.8).
Рис. 2.8. ГрадієнтВектор-градієнт спрямований у бік якнайшвидшого зростання функції у цій точці. Вектор протилежний градієнту (-f'(х)) , називається антиградієнтомі спрямований у бік якнайшвидшого зменшення функції. У точці мінімуму градієнт функції дорівнює нулю. На властивостях градієнта засновані методи першого порядку, звані також градієнтним та методами мінімізації. Використання цих методів у випадку дозволяє визначити точку локального мінімуму функції.
Очевидно, якщо немає додаткової інформації, то з початкової точки хрозумно перейти до точки х, що лежить у напрямку антиградієнта - найшвидшого зменшення функції. Вибираючи як напрямок спуску р[k] антиградієнт - f'(х[k] ) у точці х[k], отримуємо ітераційний процес виду
х[ k+ 1] = x[k]-a k f"(x[k] ) , а k > 0; k=0, 1, 2, ...
У координатній формі цей процес записується так:
x i [ k+1]=х i[k] - a kf(x[k] ) /x i
i = 1, ..., n; k= 0, 1, 2,...
Як критерій зупинки ітераційного процесу застосовують або виконання умови трошки збільшення аргументу || x[k+l] - x[k] || <= e , либо выполнение условия малости градиента
|| f'(x[k+l] ) || <= g ,
Тут e та g - задані малі величини.
Можливий і комбінований критерій, що полягає у одночасному виконанні зазначених умов. Градієнтні методи відрізняються один від одного способами вибору величини кроку а k.
При методі з постійним кроком всім ітерацій вибирається деяка постійна величина кроку. Досить малий крок а kзабезпечить зменшення функції, тобто виконання нерівності
f(х[ k+1]) = f(x[k] – a k f'(x[k] )) < f(x[k] ) .
Однак це може призвести до необхідності проводити неприйнятно велику кількість ітерацій для досягнення точки мінімуму. З іншого боку, занадто великий крок може викликати несподіване зростання функції або призвести до коливань близько мінімальної точки (зациклювання). Через складність отримання необхідної інформації для вибору величини кроку методи з постійним кроком застосовуються практично рідко.
Більш економічні у сенсі кількості ітерацій та надійності градієнтні методи зі змінним кроком,коли залежно від результатів обчислень величина кроку певним чином змінюється. Розглянемо варіанти таких методів, що застосовуються на практиці.
При використанні методу якнайшвидшого спуску на кожній ітерації величина кроку а kвибирається з умови мінімуму функції f(x)у напрямі спуску, тобто.
f(x[k]-a k f'(x[k]))
= f(x[k] - af"(x[k]))
.
Ця умова означає, що рух уздовж антиградієнта відбувається доти, доки значення функції f(x)зменшується. З математичної точки зору на кожній ітерації необхідно вирішувати задачу одномірної мінімізації по афункції
j (a) = f(x[k]- af"(x[k]))
.
Алгоритм методу якнайшвидшого спуску полягає в наступному.
1. Визначаються координати початкової точки х.
2. У точці х[k], k = 0, 1, 2, ... обчислюється значення градієнта f'(x[k]) .
3. Визначається величина кроку a k шляхом одномірної мінімізації по афункції j (a) = f(x[k]- af"(x[k])).
4. Визначаються координати точки х[k+ 1]:
х i [ k+ 1]= x i[k]– а k f’ i (х[k]), i = 1, ..., п.
5. Перевіряються умови зупинки стераційного процесу. Якщо вони виконуються, то обчислення припиняються. В іншому випадку здійснюється перехід до п. 1.
У аналізованому методі напрямок руху з точки х[k] стосується лінії рівня в точці x[k+ 1] (Рис. 2.9). Траєкторія спуску зигзагоподібна, причому сусідні ланки зигзагу ортогональні один одному. Дійсно, крок a k вибирається шляхом мінімізації по афункції? (a) = f(x[k] - af"(x[k])) . Необхідна умова мінімуму функції d j (a)/da = 0.Обчисливши похідну складної функції, отримаємо умову ортогональності векторів спускових напрямків у сусідніх точках:
dj (a)/da = -f'(x[k+ 1]f'(x[k]) = 0.
Градієнтні методи сходяться до мінімуму з високою швидкістю (зі швидкістю геометричної прогресії) для гладких опуклих функцій. У таких функцій найбільше Мі найменше mвласні значення матриці других похідних (матриці Гессе)
мало відрізняються один від одного, тобто матриця Н(х)добре обумовлена. Нагадаємо, що власними значеннями l i , i =1, …, nматриці є коріння характеристичного рівняння
Однак на практиці, як правило, мінімізовані функції мають погано зумовлені матриці других похідних (Т/М<< 1). Значення таких функцій вздовж деяких напрямків змінюються набагато швидше (іноді кілька порядків), ніж у інших напрямах. Їх поверхні рівня в найпростішому випадку сильно витягуються (Рис. 2.10), а в складніших випадках згинаються і являють собою яри. Функції, які мають такі властивості, називають яружними.Напрямок антиградієнта цих функцій (див. мал. 2.10) істотно відхиляється від напрямку в точку мінімуму, що призводить до уповільнення швидкості збіжності.
Швидкість збіжності градієнтних методів залежить також від точності обчислень градієнта. Втрата точності, а це зазвичай відбувається в околиці точок мінімуму або в яру, може взагалі порушити збіжність процесу градієнтного спуску. Внаслідок перерахованих причин градієнтні методи найчастіше використовуються у комбінації з іншими, більш ефективними методами на стадії вирішення завдання. У цьому випадку точка хзнаходиться далеко від точки мінімуму, і кроки в напрямку антиградієнта дозволяють досягти суттєвого зменшення функції.
Розглянуті вище градієнтні способи шукають точку мінімуму функції у випадку лише за нескінченне число ітерацій. Метод сполучених градієнтів формує напрями пошуку, більшою мірою відповідні геометрії функції, що мінімізується. Це суттєво збільшує швидкість їх збіжності та дозволяє, наприклад, мінімізувати квадратичну функцію.
f(x) = (х, Нх) + (b, х) + а
із симетричною позитивно визначеною матрицею Нза кінцеву кількість кроків п,дорівнює кількості змінних функції. Будь-яка гладка функція на околиці точки мінімуму добре апроксимується квадратичною, тому методи сполучених градієнтів успішно застосовують для мінімізації та неквадратичних функцій. У разі вони перестають бути кінцевими і стають ітеративними.
За визначенням, два n-мірні вектор хі уназивають пов'язанимипо відношенню до матриці H(або H-сполученими), якщо скалярний твір (x, ну) = 0.Тут Н -симетрична позитивно визначена матриця розміром пх п.
Однією з найістотніших проблем у методах сполучених градієнтів є проблема ефективної побудови напрямків. Метод Флетчера-Рівса вирішує цю проблему шляхом перетворення на кожному кроці антиградієнта -f(x[k]) у напрям p[k], H-пов'язане з раніше знайденими напрямками р, р, ..., р[k-1]. Розглянемо спочатку цей метод стосовно задачі мінімізації квадратичні функції.
Напрями р[k] обчислюють за формулами:
p[ k] = -f'(x[k]) +b k-1 p[k-l], k>= 1;
p = - f’(x) .
Величини b k-1 вибираються так, щоб напрямки p[k], р[k-1] були H-сполученими :
(p[k], Hp[k- 1])= 0.
В результаті для квадратичної функції
,
ітераційний процес мінімізації має вигляд
x[ k+l] =x[k]+a k p[k],
де р[k] - напрямок спуску на k-м кроку; а k -величина кроку. Остання вибирається з умови мінімуму функції f(х)по ау напрямку руху, тобто в результаті вирішення задачі одновимірної мінімізації:
f(х[ k] + а k р[k]) = f(x[k] + ар [k]) .
Для квадратичної функції
Алгоритм методу сполучених градієнтів Флетчера-Рівса полягає у наступному.
1. У точці хобчислюється p = -f'(x) .
2. На k-м кроку за наведеними вище формулами визначаються крок а k . і крапка х[k+ 1].
3. Обчислюються величини f(x[k+1]) і f'(x[k+1]) .
4. Якщо f'(x) = 0, то точка х[k+1] є точкою мінімуму функції f(х).В іншому випадку визначається новий напрямок p[k+l] із співвідношення
та здійснюється перехід до наступної ітерації. Ця процедура знайде мінімум квадратичної функції не більше ніж за пкроків. При мінімізації неквадратичних функцій метод Флетчера-Рівса з кінцевого стає ітеративним. У такому разі після (П+ 1)-ї ітерації процедури 1-4 циклічно повторюються із заміною хна х[п+1] , а обчислення закінчуються при , де - Задане число. При цьому застосовують таку модифікацію методу:
x[ k+l] = x[k]+a k p[k],
p[ k] = -f'(x[k])+ b k- 1 p[k-l], k>= 1;
p = -f'( x);
f(х[ k] + a k p[k]) = f(x[k] + ap[k];
.
Тут I- безліч індексів: I= (0, n, 2 п, Зп, ...), тобто оновлення методу відбувається через кожні пкроків.
Геометричний змістметоду сполучених градієнтів полягає у наступному (Рис. 2.11). Із заданої початкової точки хздійснюється спуск у напрямку р = -f"(x). У точці хвизначається вектор-градієнт f"(x). Оскільки хє точкою мінімуму функції у напрямку р, то f'(х) ортогональний вектор р. Потім знаходиться вектор р , H-сполучений до р. Далі знаходиться мінімум функції вздовж напрямку рі т.д.
Методи сполучених напрямів є одними з найефективніших для вирішення задач мінімізації. Проте слід зазначити, що вони чутливі до помилок, що виникають у процесі рахунку. При великому числізмінних похибка може настільки зрости, що процес доведеться повторювати навіть для квадратичної функції, тобто процес для неї не завжди вкладається в пкроків.
Рис.3. Геометрична інтерпретація способу якнайшвидшого спуску. На кожному кроці вибирається те щоб наступна ітерація була точкою мінімуму функції на промені L.
Цей варіант градієнтного методуґрунтується на виборі кроку з наступного міркування. З точки рухатимемося у напрямку антиградієнта до того часу, поки досягнемо мінімуму функції f цьому напрямі, т. е. на промені:
Інакше кажучи, вибирається те щоб наступна ітерація була точкою мінімуму функції f на промені L (див. рис. 3). Такий варіант градієнтного методу називається методом якнайшвидшого спуску. Зауважимо, до речі, що в цьому методі напрямки сусідніх кроків ортогональні.
Метод якнайшвидшого спуску вимагає вирішення кожному етапі завдання одномірної оптимізації. Практика показує, що цей метод часто вимагає менше операцій, ніж градієнтний метод з постійним кроком.
У загальній ситуації, проте, теоретична швидкість збіжності методу якнайшвидшого спуску не вища за швидкість збіжності градієнтного методу з постійним (оптимальним) кроком.
Числові приклади
Метод градієнтного спуску з постійним кроком
Для дослідження збіжності методу градієнтного спуску з постійним кроком було обрано функцію:
З отриманих результатів можна дійти невтішного висновку, що з занадто великому чазі метод розходиться, за дуже малому сходиться повільно і точність гірше. Треба вибирати крок найбільшим із тих, у яких метод сходиться.
Градієнтний метод із дробленням кроку
Для дослідження збіжності методу градієнтного спуску з дробленням кроку (2) було обрано функцію:
Початкове наближення – точка (10,10).
Використано критерій зупинки:
Результати експерименту відображені у таблиці:
|
Значення параметра |
Значення параметру |
Значення параметру |
Досягнута точність |
Кількість ітерацій |
З отриманих результатів можна зробити висновок про оптимальному виборіпараметрів: , хоча метод не дуже чутливий до вибору параметрів.
Метод якнайшвидшого спуску
Для дослідження збіжності методу якнайшвидшого спуску було обрано функцію:
Початкове наближення – точка (10,10). Використано критерій зупинки:
Для вирішення одновимірних завдань оптимізації використано метод золотого перерізу.
Метод отримав точність 6e-8 за 9 ітерацій.
Звідси можна дійти невтішного висновку, що спосіб якнайшвидшого спуску сходиться швидше, ніж градієнтний спосіб з дробленням кроку і спосіб градієнтного спуску з незмінним кроком.
Недоліком методом якнайшвидшого спуску є необхідність вирішувати одновимірне завдання оптимізації.
При програмуванні методів градієнтного спуску слід акуратно ставитися до вибору параметрів, а саме
- · Метод градієнтного спуску з постійним кроком: крок слід вибирати менше 0.01, інакше метод розходиться (метод може розходитися і при такому кроці в залежності від функції, що досліджується).
- · Градієнтний метод з дробленням кроку не дуже чутливий до вибору параметрів. Один із варіантів вибору параметрів:
- · Метод якнайшвидшого спуску: як метод одномірної оптимізації можна використовувати метод золотого перерізу (коли він застосовний).
Метод сполучених градієнтів – ітераційний метод для безумовної оптимізації у багатовимірному просторі. Основною перевагою методу є те, що він вирішує квадратичну задачу оптимізації за кінцеве число кроків. Тому спочатку описується метод сполучених градієнтів для оптимізації квадратичного функціоналу, виводяться ітераційні формули, наводяться оцінки швидкості збіжності. Після цього показується, як метод сполучених узагальнюється для оптимізації довільного функціоналу, розглядаються різні варіантиметоду, що обговорюється збіжність.
Постановка задач оптимізації
Нехай задано безліч і на цій множині визначено цільову функцію (objective function). Завдання оптимізації полягає у знаходженні на множині точної верхньої або точної нижньої грані цільової функції. Безліч точок, у яких досягається нижня грань цільової функції позначається.
Якщо завдання оптимізації називається безумовною (unconstrained). Якщо задача оптимізації називається умовною (constrained).
Метод сполучених градієнтів для квадратичного функціоналу
Виклад методу
Розглянемо таку задачу оптимізації:
Тут – симетрична позитивно визначена матриця розміру. Таке завдання оптимізації називається квадратичною. Зауважимо, що. Умова екстремуму функції еквівалентна системі Функція досягає своєї нижньої грані в єдиній точці, що визначається рівнянням. Таким чином, це завдання оптимізації зводиться до вирішення системи. лінійних рівняньІдея методу сполучених градієнтів полягає в наступному: Нехай - базис ст. Тоді для будь-якої точки вектор розкладається по базису Таким чином, представимо у вигляді
Кожне наступне наближення обчислюється за такою формулою:
Визначення. Два вектори і називаються сполученими щодо симетричної матриці B, якщо
Опишемо спосіб побудови базису в методі сполучених градієнтів Як початкове наближення вибираємо довільний вектор. На кожній ітерації вибираються за правилом:
Базисні вектори обчислюються за формулами:
Коефіцієнти вибираються так, щоб вектори були пов'язаними щодо А.
Якщо позначити за, то після кількох спрощень отримаємо остаточні формули, що використовуються при застосуванні методу сполучених градієнтів на практиці:
Для методу сполучених градієнтів справедлива наступна теорема: Теорема Нехай де - симетрична позитивно визначена матриця розміру. Тоді метод сполучених градієнтів сходиться лише за кроків і справедливі такі співвідношення:
Збіжність методу
Якщо всі обчислення точні, і вихідні дані точні то метод сходиться до вирішення системи лише за ітерацій, де - розмірність системи. Більш тонкий аналіз показує, що кількість ітерацій не перевищує, де - число різних власних значеньматриці A. Для оцінки швидкості збіжності вірна наступна (досить груба) оцінка:
Вона дозволяє оцінити швидкість збіжності, якщо відомі оцінки для максимального та мінімального власних значень матриці. На практиці найчастіше використовують наступний критерій зупинки:
Обчислювальна складність
На кожній ітерації методу виконуються операції. Така кількість операцій потрібна для обчислення твору - це трудомістка процедура на кожній ітерації. Отальні обчислення вимагають O(n) операцій. Сумарна обчислювальна складність методу вбирається у - оскільки кількість ітерацій не більше n.
Чисельний приклад
Застосуємо метод сполучених градієнтів для вирішення системи, де за допомогою методу сполучених градієнтів рішення цієї системи виходить за дві ітерації. Власні числаматриці - 5, 5, -5 - серед них два різні, тому, згідно з теоретичною оцінкою число ітерацій не могло перевищувати двох
Метод сполучених градієнтів - один із найбільш ефективних методіврішення СЛАУ із позитивно визначеною матрицею. Метод гарантує збіжність за кінцеве число кроків, а потрібна точність може бути досягнута значно раніше. Основна проблема полягає в тому, що через накопичення похибок може порушуватись ортогональність базисних вітрорів, що погіршує збіжність.
Метод сполучених градієнтів у випадку
Розглянемо тепер модифікацію методу сполучених градієнтів для випадку, коли функціонал, що мінімізується, не є квадратичним: Будемо вирішувати завдання:
Безперервно диференційована функція. Щоб модифікувати метод сполучених градієнтів для вирішення цього завдання необхідно отримати для формули, які не входять матриця А:
можна обчислювати за однією з трьох формул:
1. - Метод Флетчера – Рівса (Fletcher-Reeves method)
- 2. - Метод Полака - Райбера (Polak-Ribi`ere method)
Якщо функція - квадратична і випукла, то всі три формули дають однаковий результат. Якщо - довільна функція, то кожній із формул відповідає своя модифікація методу сполучених градієнтів. Третя формула використовується рідко, так як вона вимагає, щоб функція та обчислення гесіана функції на кожному кроці методу.
Якщо функція – не квадратична, метод сполучених градієнтів може і не сходитися за кінець кількох кроків. Крім того, точне обчислення на кожному кроці можливе лише в окремих випадках. Тому накопичення похибок призводить до того, що вектора перестають вказувати напрямок зменшення функції. Тоді на якомусь кроці вважають. Сукупність усіх номерів, за яких приймається, позначимо за. Номери називаються моментами поновлення методу. Насправді часто вибирають, де - розмірність простору.
Збіжність методу
Для методу Флетчера - Рівса існує теорема про збіжність, що накладає не надто жорсткі умови на функцію, що мінімізується: Теорема. Нехай і виконуються такі умови:
Безліч обмежена
Похідна задовольняє умові Липшиця з константою в околиці
множини M: .
Для методу Полака-Райбера доведено збіжність у припущенні, що суворо опукла функція. У випадку довести збіжність методу Полака - Райбера неможливо. Напоротив, вірна така теорема: Теорема. Припустимо, що у методі Полака-Райбера значення кожному кроці обчислюються точно. Тоді існує функція, і початкове наближення, такі що.
Тим не менш, на практиці метод Полака-Райбер працює краще. Найпоширеніші критерії зупинення практично: Норма градієнта стає менше деякого порога Значення функції протягом m послідовних ітерацій майже змінилося
Обчислювальна складність
На кожній ітерації методів Полака-Райбера або Флетчера-Рівса по одному разу обчислюються функція та її градієнт, вирішується завдання одновимірної оптимізації. Таким чином, складність одного кроку методу сполучених градієнтів має той самий порядок, що і складність кроку методу якнайшвидшого спуску. Насправді метод сполучених градієнтів показує кращу швидкість збіжності.
Шукатимемо методом сполучених градієнтів мінімум функції
Мінімум цієї функції дорівнює 1 і досягається в точці (5, 4). Порівняємо з прикладу цієї функції методи Полака-Райбера і Флетчера-Ривса. Ітерації в обох методах припиняються, коли на поточному етапі квадрат норми градієнта стає меншим. Для вибору використовується метод золотого перерізу
|
Метод Флетчера – Рівса |
Метод Полака – Райбера |
|||||
|
Число ітерацій |
Знайдене рішення |
Значення функції |
Число ітерацій |
Знайдене рішення |
Значення функції |
|
|
(5.01382198,3.9697932) |
(5.03942877,4.00003512) |
|||||
|
(5.01056482,3.99018026) |
(4.9915894,3.99999044) |
|||||
|
(4.9979991,4.00186173) |
(5.00336181,4.0000018) |
|||||
|
(4.99898277,4.00094645) |
(4.99846808,3.99999918) |
|||||
|
(4.99974658,4.0002358) |
(4.99955034,3.99999976) |
Реалізовано два варіанти методу сполучених градієнтів: для мінімізації квадратичного функціоналу та для мінімізації довільної функції. У першому випадку метод реалізується функцією vector
Методи градієнтного спуску є досить потужним інструментом розв'язання задач оптимізації. Головним недоліком методів є обмежена сфера застосування. У методі сполучених градієнтів використовується інформація лише про лінійну частину збільшення в точці, як і методах градієнтного спуску. При цьому метод сполучених градієнтів дозволяє вирішувати квадратичні завдання за кінець кількох кроків. На багатьох інших завданнях метод сполученого градієнта також перевершує метод градієнтного спуску. Збіжність методу градієнтів істотно залежить від цього, наскільки точно вирішується завдання одномірної оптимізації. Можливі зациклювання методу усуваються за допомогою оновлень. Проте, якщо метод потрапить до локального мінімуму функції, швидше за все, йому не вдасться з нього вибратися.
Призначення сервісу. Онлайн-калькулятор використовується для знаходження мінімуму функціїметодом якнайшвидшого спуску або методом Коші(Див. приклад). Рішення оформляється у форматі Word.Правила введення функції
У методі якнайшвидшого спускуяк напрям пошуку вибирається вектор, напрям якого протилежно напрямку вектора градієнта функції ▽f(x). З математичного аналізувідомо, що вектор grad f(x)=▽f(x) характеризує напрямок найшвидшого зростання функції (див. градієнт функції). Тому вектор - grad f(X) = -▽f(X) називається антиградієнтомі є напрямом найшвидшого її спадання. Рекурентне співвідношення, За допомогою якого реалізується метод якнайшвидшого спуску, має вигляд X k +1 = X k - k (k, k = 0,1,...,
де λ k >0 - величина кроку. Залежно від вибору величини кроку можна отримати різні варіанти методу градієнта. Якщо в процесі оптимізації величина кроку фіксована, то метод носить назву градієнтного методу з дискретним кроком. Процес оптимізації на перших ітераціях можна значно прискорити, якщо k вибирати з умови k = min f (X k + S k) .
Для визначення k використовується будь-який метод одновимірної оптимізації. І тут метод називається методом якнайшвидшого спуску. Як правило, у загальному випадку недостатньо одного кроку для досягнення мінімуму функції, процес повторюють доти, доки наступні обчислення дозволяють покращувати результат.
Якщо простір дуже витягнутий за деякими змінними, то утворюється "яр". Пошук може сповільнитись і йти зигзагами поперек дна “яру”. Іноді рішення неможливо одержати за прийнятний час.
Ще одним недоліком методу може бути критерій зупинки | | f (X k) | |<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
Приклад. Починаючи з точки x k =(-2, 3) визначте точку x k +1 методом якнайшвидшого спуску для мінімізації функції .
Як напрямок пошуку виберемо вектор градієнт у поточній точці 
Перевіримо критерій зупинки. Маємо 
Обчислимо значення функції у початковій точці f(X 1) = 35. Зробимо
крок вздовж напрямку антиградієнта
Обчислимо значення функції у новій точці
f(X 2) = 3(-2 + 19λ 1) 2 + (3-8λ 1) 2 - (-2 + 19λ 1)(3-8λ 1) - 4(-2 + 19λ 1)
Знайдемо такий крок, щоб цільова функція досягала мінімуму вздовж цього напряму. З необхідної умови існування екстремуму функції
f'(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) – (73 - 304 λ 1) – 4*19
або f'(X 2) = 2598 λ 1 - 425 = 0.
Отримаємо крок λ 1 = 0.164
Виконання цього кроку приведе до точки 
у якій значення градієнта 
значення функції f(X 2) = 0.23. Точність не досягнуто, з точки робимо крок вздовж напрямку антиградієнта.
f(X 2) = 3(1,116 – 1,008λ 1) 2 + (1,688-2,26λ 1) 2 - (1,116 – 1,008λ 1)(1,688-2,26λ 1) - 4(1,116 – 1,008λ 1
f'(X 2) = 11,76 - 6,12λ 1 = 0
Отримуємо λ 1 = 0.52 
Завантаження...