Метод якнайшвидшого спуску. Мінімум функції методом якнайшвидшого спуску

Також можна шукати не найкращу точку в напрямку градієнта, а якусь краще за поточну.

Найбільш простий у реалізації із усіх методів локальної оптимізації. Має досить слабкі умови збіжності, та заодно швидкість збіжності досить мала (лінійна). Крок градієнтного методу часто використовується як частина інших методів оптимізації, наприклад, метод Флетчера – Рівса.

Опис [ | ]

Удосконалення[ | ]

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

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

Застосування у штучних нейронних мережах[ | ]

Метод градієнтного спуску з деякою модифікацією широко застосовується для навчання перцептрону і теоретично штучних нейронних мереж відомий як метод зворотного поширення помилки. При навчанні нейромережі типу персептрон потрібно змінювати вагові коефіцієнти мережі так, щоб мінімізувати середню помилкуна виході нейронної мережі при подачі на вхід послідовності навчальних вхідних даних. Формально, щоб зробити всього один крок за методом градієнтного спуску (зробити лише одну зміну параметрів мережі), необхідно подати на вхід мережі послідовно абсолютно весь набір навчальних даних, для кожного об'єкта навчальних даних обчислити помилку та розрахувати необхідну корекцію коефіцієнтів мережі (але не робити цю корекцію), і після подачі всіх даних розрахувати суму в коригуванні кожного коефіцієнта мережі (сума градієнтів) і зробити корекцію коефіцієнтів «на крок». Очевидно, що при великому наборі навчальних даних алгоритм працюватиме вкрай повільно, тому на практиці часто здійснюють коригування коефіцієнтів мережі після кожного елемента навчання, де значення градієнта апроксимуються градієнтом функції вартості, обчисленому тільки на одному елементі навчання. Такий метод називають стохастичним градієнтним спуском або оперативним градієнтним спуском . Стохастичний градієнтний спуск є одним із форм стохастичного наближення. Теорія стохастичних наближень дає умови збіжності способу стохастичного градієнтного спуску.

Посилання [ | ]

• J. Mathews.Модули для Steepest Descent або Gradient Method. (недоступне посилання)

Література [ | ]

• Акуліч І. Л.Математичне програмування в прикладах та задачах. - М.: вища школа, 1986. – С. 298-310.
• Гілл Ф., Мюррей У., Райт М.Практична оптимізація = Practical Optimization. - М.: Світ, 1985.
• Коршунов Ю. М., Коршунов Ю. М.Математичні засади кібернетики. - М.: Вища школа, 1972.
• Максимов Ю. А., Філіповська Є. А.Алгоритми розв'язання задач нелінійного програмування. - М.: МІФІ, 1982.
• Максимов Ю. А.Алгоритми лінійного та дискретного програмування. - М.: МІФІ, 1980.
• Корн Р., Корн Т.Довідник з математики для науковців та інженерів. - М.: Наука, 1970. - С. 575-576.
• С. Ю. Городецький, В. А. Гришагін. Нелінійне програмуваннята багатоекстремальна оптимізація. - Нижній Новгород: Видавництво Нижегородського Університету, 2007. – С. 357-363.

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

d j (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.

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

Призначення сервісу. Онлайн-калькулятор використовується для знаходження мінімуму функціїметодом якнайшвидшого спуску або методом Коші(Див. приклад). Рішення оформляється у форматі 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 ▽f(x 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

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

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