Градієнтний метод. Огляд градієнтних методів у задачах математичної оптимізації

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

Напрямок якнайшвидшого спуску відповідає напрямку максимального зменшення функції. Відомо, що напрям найбільшого зростання функції двох змінних u = f(x, у) характеризується її градієнтом:

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

Ідея методу градієнтного спуску полягає в наступному. Вибираємо деяку початкову точку

обчислюємо в ній градієнт цієї функції. Робимо крок у напрямку, зворотному до градієнтного:

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

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

В описаному методі потрібно обчислювати кожному кроці оптимізації градієнт цільової функції f(х):

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

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

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

Метод якнайшвидшого спуску випадку функції двох змінних z = f(x,y).

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

Градієнтні методи

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

на k-му етапіградієнтних методів перехід з точки Xk до точки Xk+1 описується співвідношенням:

де k - величина кроку, k - вектор у напрямку Xk+1-Xk.

Методи якнайшвидшого спуску

Вперше такий метод розглянув та застосував ще О. Коші у XVIII ст. Ідея його проста: градієнт цільової функції f(X) у будь-якій точці є вектором у напрямку найбільшого зростання значення функції. Отже, антиградієнт буде направлений у бік найбільшого зменшення функції і є напрямом якнайшвидшого спуску. Антиградієнт (і градієнт) ортогональний поверхні рівня f(X) у точці X. Якщо в (1.2) ввести напрямок

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

Отримуємо формулу переходу з Xk до Xk+1:

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

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

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

Одним із недоліків цього методу є те, що він сходиться до будь-якої стаціонарної точки, у тому числі і сідлової, яка не може бути рішенням.

Але найголовніше - дуже повільна збіжність якнайшвидшого спуску в загальному випадку. Справа в тому, що спуск є "найшвидшим" ​​у локальному сенсі. Якщо гіперпростір пошуку сильно витягнуто ( " яр " ), то антиградієнт спрямований майже ортогонально дну " яру " , тобто. найкращому напрямку досягнення мінімуму. У цьому сенсі прямий переклад англійського терміна" steepest descent " , тобто. спуск по найбільш крутому схилу більше відповідає стану справ, ніж термін "найшвидший", прийнятий у російськомовній спеціальній літературі. Одним із виходів у цій ситуації є використання інформації, яку дають другі приватні похідні. Інший вихід – зміна масштабів змінних.

лінійний апроксимація похідна градієнт

Метод сполученого градієнта Флетчера-Рівса

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

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

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

Алгоритм Флетчера-Рівса

1. У X0 обчислюється.

2. На k-му кроці за допомогою одномірного пошуку в напрямку знаходиться мінімум f(X), який визначає точку Xk+1.

• 3. Обчислюються f(Xk+1) і.
• 4. Напрямок визначається із співвідношення:

• 5. Після (n+1)-й ітерації (тобто при k=n) виробляється рестарт: покладається X0=Xn+1 здійснюється перехід до кроку 1.
• 6. Алгоритм зупиняється, коли

де – довільна константа.

Перевагою алгоритму Флетчера-Рівса і те, що він вимагає звернення матриці і заощаджує пам'ять ЕОМ, оскільки йому не потрібні матриці, використовувані в Ньютоновских методах, але водночас майже так само ефективний як квази-Ньютоновские алгоритми. Т.к. напрями пошуку взаємно пов'язані, то квадратична функція буде мінімізована трохи більше, ніж за n кроків. У випадку використовується рестарт, який дозволяє отримувати результат.

Алгоритм Флетчера-Рівса є чутливим до точності одновимірного пошуку, тому при його використанні необхідно усувати будь-які помилки округлення, які можуть виникнути. Крім того, алгоритм може відмовити в ситуаціях, де Гессіан стає погано обумовленим. Гарантії збіжності завжди і скрізь алгоритм не має, хоча практика показує, що майже завжди алгоритм дає результат.

Ньютонівські методи

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

де – матриця Гессе.

Мінімум правої частини (якщо він існує) досягається там же, де і мінімум квадратичної форми. Запишемо формулу для визначення напряму пошуку:

Мінімум досягається при

Алгоритм оптимізації, у якому напрям пошуку визначається з цього співвідношення, називається методом Ньютона, а напрям - ньютонівським напрямом.

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

Класифікація Ньютонівських методів

Власне, метод Ньютона полягає в одноразовому застосуванні Ньютонівського напряму для оптимізації квадратичної функції. Якщо ж функція не є квадратичною, то вірна така теорема.

Теорема 1.4. Якщо матриця Гессе нелінійної функції f загального виду у точці мінімуму X* позитивно визначено, початкова точка обрана досить близько до X* і довжини кроків підібрані правильно, то метод Ньютона сходить до X* із квадратичною швидкістю.

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

Загальний принцип модифікацій методу Ньютона полягає в наступному: на кожній ітерації спочатку будується деяка "пов'язана" з позитивно визначеною матрицею, а потім обчислюється за формулою

Оскільки позитивно визначено, то обов'язково буде напрямом спуску. Процедуру побудови організують так, щоб вона збігалася з матрицею Гессе, якщо вона є позитивно визначеною. Ці процедури будуються на основі деяких матричних розкладів.

Інша група методів, що практично не поступаються швидкодії методу Ньютона, заснована на апроксимації матриці Гессе за допомогою кінцевих різниць, т.к. не обов'язково для оптимізації використовувати точні значення похідних. Ці методи корисні, коли аналітичне обчислення похідних важко або просто неможливо. Такі методи називають дискретними методами Ньютона.

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

Відповідні методи, що спираються на можливість апроксимації кривизни нелінійної функції без явного формування її матриці Гессе, називають квазі-ньютонівськими методами.

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

Метод Ньютона-Рафсона

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

Основна ітераційна формулабагатовимірної оптимізації

використовується в цьому методі при виборі напряму оптимізації із співвідношення

Реальна довжина кроку прихована у ненормалізованому Ньютонівському напрямі.

Так як цей метод не вимагає значення цільової функції в поточній точці, його іноді називають непрямим або аналітичним методомоптимізація. Його здатність визначати мінімум квадратичної функції за одне обчислення виглядає, на перший погляд, виключно привабливо. Однак це "одне обчислення" потребує значних витрат. Насамперед, необхідно обчислити n приватних похідних першого порядку та n(n+1)/2 - другого. Крім того, матриця Гессе має бути інвертованою. Це вже вимагає порядку n3 обчислювальних операцій. З тими самими витратами методи сполучених напрямів чи методи сполученого градієнта можуть зробити порядку n кроків, тобто. досягти практично того ж результату. Отже, ітерація методу Ньютона-Рафсона дає переваг у разі квадратичної функції.

Якщо ж функція не квадратична, то

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

Сама по собі стратегія не розрізняє, до якої саме стаціонарної точки (мінімуму, максимуму, сідлової) наближається пошук, а обчислення значень цільової функції, якими можна було б відстежити, чи не зростає функція, не робляться. Отже, все залежить від того, у зоні тяжіння який стаціонарної точкивиявляється стартова точка пошуку. Стратегія Ньютона-Рафсона рідко використовується як така без модифікації тієї чи іншої роду.

Методи Пірсона

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

Алгоритм Пірсона №2.

У цьому алгоритмі зворотний гесіан апроксимується матрицею Hk, що обчислюється на кожному кроці за формулою

Як початкова матриця H0 вибирається довільна позитивно визначена симетрична матриця.

Даний алгоритм Пірсона часто призводить до ситуацій, коли матриця Hk стає погано обумовленою, а саме вона починає осцилювати, коливаючись між позитивно визначеною і не позитивно визначеною, при цьому визначник матриці близький до нуля. Щоб уникнути цієї ситуації, необхідно через кожні n кроків перезадавати матрицю, прирівнюючи її до H0.

Алгоритм Пірсона №3.

У цьому алгоритмі матриця Hk+1 визначається формулою

Hk+1 = Hk+

Траєкторія спуску, що породжується алгоритмом, аналогічна до поведінки алгоритму Девідона-Флетчера-Пауелла, але кроки трохи коротші. Пірсон також запропонував різновид цього алгоритму із циклічним перезавданням матриці.

Проективний алгоритм Ньютона-Рафсона

Пірсон запропонував ідею алгоритму, у якому матриця розраховується із співвідношення

H0=R0, де матриця R0 така сама як і початкові матриці попередніх алгоритмах.

Коли k кратно числу незалежних змінних n, матриця Hk замінюється на матрицю Rk+1, що обчислюється як сума

Величина Hk(f(Xk+1) - f(Xk)) є проекцією вектора збільшення градієнта (f(Xk+1)-f(Xk)), ортогональної до всіх векторів збільшення градієнта на попередніх кроках. Після кожних n кроків Rk є апроксимацією зворотного гесіана H-1(Xk), так що по суті здійснюється (наближено) пошук Ньютона.

Метод Девідона-Флетчера-Пауела

Цей метод має інші назви - метод змінної метрики, квазиньютоновский метод, т.к. він використовує обидва ці підходи.

Метод Девідона-Флетчера-Пауела (ДФП) ґрунтується на використанні ньютонівських напрямків, але не вимагає обчислення зворотного гесіана на кожному кроці.

Напрямок пошуку на кроці k є напрямком

де Hi - позитивно певна симетрична матриця, яка оновлюється кожному кроці й у межі стає рівною зворотному гессиану. Як початкова матриця H зазвичай вибирають одиничну. Ітераційна процедура ДФП може бути представлена ​​таким чином:

• 1. На кроці k є точка Xk та позитивно визначена матриця Hk.
• 2. Як новий напрямок пошуку вибирається

3. Одновимірним пошуком (зазвичай кубічною інтерполяцією) вздовж напрямку визначається k, що мінімізує функцію.

4. Належить.

5. Належить.

6. Визначається в. Якщо Vk або малі, процедура завершується.

• 7. Належить Uk = f(Xk+1) - f(Xk).
• 8. Матриця Hk оновлюється за формулою

9. Збільшити k на одиницю та повернутися на крок 2.

Метод ефективний практично, якщо помилка обчислень градієнта невелика і матриця Hk стає погано обумовленою.

Матриця Ak забезпечує збіжність Hk G-1, матриця Bk забезпечує позитивну визначеність Hk+1 на всіх етапах і в межі виключає H0.

У разі квадратичної функції

тобто. алгоритм ДФП використовує пов'язані напрями.

Таким чином, метод ДФП використовує як ідеї ньютоновського підходу, так і властивості сполучених напрямків, і при мінімізації квадратичної функції сходиться не більше ніж за n ітерацій. Якщо оптимізована функція має вигляд, близький до квадратичної функції, метод ДФП ефективний за рахунок гарної апроксимації G-1 (метод Ньютона). Якщо ж цільова функція має загальний вигляд, то метод ДФП ефективний з допомогою використання сполучених напрямів.

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

Існують різні способивибору кроку кожен із яких задає певний варіантградієнтного методу.

1. Метод якнайшвидшого спуску.

Розглянемо функцію однієї скалярної змінної і виберемо в якості значення, для якого виконується рівність

Цей метод, запропонований 1845 р. О. Коші, прийнято тепер називати методом якнайшвидшого спуску.

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

Зазначимо, що з кожної ітерації вибір кроку передбачає вирішення завдання одномірної мінімізації (10.23). Іноді цю операцію вдається виконати аналітично, наприклад, для квадратичної функції.

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

із симетричною позитивно визначеною матрицею А.

Відповідно до формули (10.8), у цьому випадку Тому формула (10.22) виглядає тут так:

Зауважимо, що

Ця функція є квадратичною функцією параметра і досягає мінімуму при такому значенні для якого

Таким чином, стосовно мінімізації квадратичної

функції (10.24) метод якнайшвидшого спуску еквівалентний розрахунку за формулою (10.25), де

Зауваження 1. Оскільки точка мінімуму функції (10.24) збігається з рішенням системи метод якнайшвидшого спуску (10.25), (10.26) може застосовуватися і як ітераційний методрішення систем лінійних алгебраїчних рівняньіз симетричними позитивно визначеними матрицями.

Зауваження 2. Зазначимо, що відношення Релея (див. § 8.1).

Приклад 10.1. Застосуємо метод якнайшвидшого спуску для мінімізації квадратичної функції

Тому точне значення точки мінімуму нам заздалегідь відомо. Запишемо цю функціюу вигляді (10.24), де матриця та вектор Як неважко бачити,

Візьмемо початкове наближення і вести обчислення за формулами (10.25), (10.26).

І ітерація.

ІІ ітерація.

Можна показати, що для всіх на ітерації буде отримано значення

Зауважимо, що таким чином,

послідовність отримана методом якнайшвидшого спуску, сходиться зі швидкістю геометричній прогресії, знаменник якої

На рис. 10.5 зображено саме траєкторію спуску, яка була отримана в даному прикладі.

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

Теорема 10.1. Нехай А – симетрична позитивно визначена матриця та мінімізується квадратична функція (10.24). Тоді за будь-якого вибору початкової наближення метод найшвидшого спуску (10.25), (10.26) сходиться і вірна наступна оцінка похибки:

Тут і Ладо – мінімальне та максимальне власні значення матриці А.

Зазначимо, що це метод сходиться зі швидкістю геометричної прогресії, знаменник якої причому якщо їх близькі, мало і метод сходиться досить швидко. Наприклад, у прикладі 10.1 маємо і тому Якщо Ащах, то і 1 і слід очікувати повільної збіжності методу якнайшвидшого спуску.

Приклад 10.2. Застосування методу якнайшвидшого спуску для мінімізації квадратичної функції при початковому наближенні дає послідовність наближень, де Траєкторія спуску зображена на рис. 10.6.

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

ніж у попередньому примірю. Тому що тут і отриманий результат цілком узгоджується з оцінкою (10.27).

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

Зауваження 2. Для квадратичної цільової функції (10.24) розв'язання задачі одновимірної мінімізації (10.23) вдається знайти у вигляді простої явної формули (10.26). Однак для більшості інших нелінійних функційцього зробити не можна і для обчислення методом якнайшвидшого спуску доводиться застосовувати Чисельні методиодномірної мінімізації типу тих, що були розглянуті у попередньому розділі.

2. Проблема "ярів".

З проведеного вище обговорення випливає, що градієнтний метод сходиться досить швидко, якщо для мінімізованої функції поверхні рівня близькі до сфер (при лінії рівня близькі до кола). Для таких функцій і 1. Теорема 10.1, зауваження 1, а також результат прикладу 10.2 вказують на те, що швидкість збіжності різко падає при збільшенні величини. . У двовимірному випадку рельєф відповідної поверхні нагадує рельєф місцевості з яром (рис. 10.7). Тому такі функції прийнято називати яружними. Уздовж напрямів, що характеризують "дно яру", ярова функція змінюється незначно, а в інших напрямках, що характеризують "схил яра", відбувається різка зміна функції.

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

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

Більше детальну інформаціюПро проблему "ярів" і "яружних" методах можна знайти, наприклад, в , .

3. Інші підходи щодо визначення кроку спуску.

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

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

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

Опис [ | ]

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

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

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

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

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

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

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

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

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

Нарешті параметр m можна задавати постійним на всіх ітераціях. Однак при великих значеннях m процес пошуку може розходитися. Хорошим способомвибору m може бути його визначення на першій ітерації з умови екстремуму за напрямом градієнта. На наступних ітераціях m залишається незмінним. Це ще спрощує обчислення.

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

Обчислюємо координати х (1):

Для обчислення координат точки х (2) знаходимо проекції градієнта в точці х (1) : тоді

і т.д.

Ця послідовність також сходиться.

Кроковий градієнтний метод

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

Нехай дана сепарабельна функція та початкова точка . Задамо постійним кроком по координаті х 1 , нехай Dх 1 =0,2. Крок по координаті х 2 знаходимо із співвідношення градієнтів та кроків.