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

Постановка задачі

Нехай дана функція 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.

Рис. 2.9. Геометрична інтерпретація методу якнайшвидшого спуску

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

мало відрізняються один від одного, тобто матриця Н(х)добре обумовлена. Нагадаємо, що власними значеннями l i , i =1, …, nматриці є коріння характеристичного рівняння

Однак на практиці, як правило, мінімізовані функції мають погано зумовлені матриці других похідних (Т/М<< 1). Значення таких функцій вздовж деяких напрямків змінюються набагато швидше (іноді кілька порядків), ніж у інших напрямах. Їх поверхні рівня в найпростішому випадку сильно витягуються (Рис. 2.10), а в складніших випадках згинаються і являють собою яри. Функції, які мають такі властивості, називають яружними.Напрямок антиградієнта цих функцій (див. мал. 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-сполучений до р. Далі знаходиться мінімум функції вздовж напрямку рі т.д.

Рис. 2.11 . Траєкторія спуску у методі сполучених градієнтів

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

Приклад 6.8.3-1. Знайти мінімум функції Q (x, y) методом ГДШ.

Нехай Q(x, y) = x 2 +2y 2; x 0 = 2; y 0 = 1.

Перевіримо достатні умови існування мінімуму:

Виконаємо одну ітерацію згідно з алгоритмом.

1. Q(x 0 , y 0) = 6.

2. При х = x 0 і y = y 0

3. Крок l k = l 0 = 0,5

Таким чином, 4< 8, следовательно, условие сходимости не выполняется и требуется, уменьшив шаг (l=l /2), повторять п.п.3-4 до выполнения условия сходимости. То есть, полученный шаг используется для нахождения следующей точки траектории спуска.

Суть методу полягає у наступному. З обраної точки (x 0 , y 0) спуск здійснюють у напрямку антиградієнта доти, доки буде досягнуто мінімальне значення цільової функції Q(x, y) вздовж променя (рис. 6.8.4-1). У знайденій точці промінь стосується лінії рівня. Потім з цієї точки спуск проводиться в напрямку антиградієнта (перпендикулярному лінії рівня) до тих пір, поки відповідний промінь не торкнеться в новій точці лінії лінії, що проходить через неї, і т.д.

Висловимо цільову функцію Q(x, y) через крок l. У цьому представимо цільову функцію певному кроці як функцію однієї змінної, тобто. величини кроку

Величина кроку кожної ітерації визначається з умови мінімуму :

Min((l)) l k = l*(x k , y k), l >0.

Таким чином, на кожній ітерації вибір кроку l k передбачає вирішення задачі одновимірної оптимізації. За способом вирішення цього завдання розрізняють:

· аналітичний метод(НСА);

· Чисельний метод (НСЧ).

У методі НСА значення кроку одержують із умови , а методі НСЧ величину l k знаходять на відрізку c заданою точністю, використовуючи одне із методів одномірної оптимізації.

Приклад 6.8.4-1. Знайти мінімум функції Q (x, y) = x 2 + 2y 2 з точністю e = 0.1, за початкових умов: x 0 = 2; y 0 =1.

Зробимо одну ітерацію методом НСА.

=(x-2lx) 2 +2(y-4ly) 2 = x 2 -4lx 2 +4l 2 x 2 +2y 2 -16ly 2 +32l 2 y 2 .

З умови ¢(l)=0 знайдемо значення l*:

Отримана функція l = l (x, y) дозволяє визначити значення l. При x=2 та y=1 маємо l=0.3333.

Обчислимо значення координат наступної точки:

Перевіримо виконання критерію закінчення ітерацій при k=1:

Оскільки |2*0.6666|>0.1 і |-0.3333*4|>0.1 , умови закінчення процесу ітерацій не виконані, тобто. мінімум не знайдено. Тому слід обчислити нове значення l при x=x1 і y=y1 і отримати координати наступної точки спуску. Обчислення продовжуються доти, доки не виконаються умови закінчення спуску.

Відмінність чисельного методу СР від аналітичного полягає в тому, що пошук значення l на кожній ітерації відбувається одним з чисельних методіводновимірної оптимізації (наприклад, методом дихотомії або методом золотого перерізу). При цьому як інтервал невизначеності служить діапазон допустимих значень l -.

Призначення сервісу. Онлайн-калькулятор використовується для знаходження мінімуму функціїметодом якнайшвидшого спуску або методом Коші(Див. приклад). Рішення оформляється у форматі Word.

f(x 1 ,x 2) =

Для знаходження максимуму функції, необхідно помножити цільову функцію (-1) , тобто. Fmin = -Fmax.
Метод пошуку мінімуму функціїМетод найшвидшого спуску Метод Ньютона
Починаючи з точки ( ; ) .
Точність ξ = . Кількість ітерацій 1 2 3

Правила введення функції

У методі якнайшвидшого спускуяк напрям пошуку вибирається вектор, напрям якого протилежно напрямку вектора градієнта функції ▽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

У цьому варіанті градієнтного методу мінімізуюча послідовність (X k ) також будується за правилом (2.22). Однак величина кроку ak перебуває в результаті вирішення допоміжного завдання одномірної мінімізації

min(j k (a) | a>0), (2.27)

де j k (a) = f (X k - a · (X k)). Таким чином, на кожній ітерації у напрямку антиградієнта виконується вичерпний спуск. Для вирішення задачі (2.27) можна скористатися одним із методів одновимірного пошуку, викладених у розділі 1, наприклад, методом розрядного пошуку або методом золотого перерізу.

Опишемо алгоритм методу якнайшвидшого спуску.

Крок 0Задати параметр точності e>0, вибрати X 0 ÎE n, покласти k = 0.

Крок 1.Знайти (X k) та перевірити умову досягнення заданої точності || (x k) ||£ e. Якщо воно виконується, то перейти до кроку 3, інакше до кроку 2.

Крок 2Розв'язати завдання (2.27), тобто. знайти a k . Знайти ще одну точку , покласти k=k+1 і перейти до кроку 1.

Крок 3Завершити обчислення, поклавши X * = X k, f * = f (X k).

Типовий приклад

Мінімізувати функцію

f(x)=x 1 2 +4x 2 2 -6x 1 -8x 2 +13; (2.28)

Спочатку вирішимо задачу класичнимметодом. Запишемо систему рівнянь, що становлять необхідні умови безумовного екстремуму

Вирішивши її, отримаємо стаціонарну точку X * = (3; 1). Далі перевіримо виконання достатньої умови, для чого знайдемо матрицю других похідних

Так як, згідно з критерієм Сильвестра, ця матриця позитивно визначена при ", то знайдена точка X * є точкою мінімуму функції f (X). Мінімальне значення f * = f (X *) = 0. Таке точне рішення задачі (11).

Виконаємо одну ітерацію методу градієнт спускудля (2.28). Виберемо початкову точку X 0 =(1;0), задаємо початковий крок a=1 та параметр l=0,5. Обчислимо f(X0)=8.

Знайдемо градієнт функції f(X) у точці X 0

(X 0) = = (2.29)

Визначимо нову точку X = X 0 -a · (X 0), обчисливши її координати

x 1 =

x 2 = (2.30)

Обчислимо f (X) = f (X 0 -a · (X 0)) = 200. Оскільки f(X)>f(X 0), то виконуємо дроблення кроку, вважаючи a=a·l=1·0,5=0,5. Знову обчислюємо за формулами (2.30) x 1 = 1 + 4a = 3; x 2 =8a=4 і бачимо значення f(X)=39. Оскільки знову f(X)>f(X 0), ще зменшуємо величину кроку, вважаючи a=a·l=0,5·0,5=0,25. Обчислюємо нову точку з координатами x 1 = 1 + 4 · 0,25 = 2; x 2 =8·0,25=2 і значення функції у цій точці f(X)=5. Оскільки умова зменшення f(X)

Виконаємо одну ітерацію за методом якнайшвидшого спускудля (2.28) з тією самою початковою точкою X 0 = (1; 0). Використовуючи вже знайдений градієнт (2.29), знаходимо

X = X 0 -a · (X 0)

і будуємо функцію j 0 (a) = f (X 0 -a · (X 0)) = (4a-2) 2 +4 (8a-1) 2 . Мінімізуючи її за допомогою необхідної умови

j 0 ¢(a)=8·(4a - 2)+64·(8a - 1)=0

знаходимо оптимальне значення величини кроку a 0 = 5/34.

Визначаємо точку мінімізуючої послідовності

X 1 = X 0 -a 0 · (X 0) .