Градіє́нтний спуск (англ. gradient descent) — це ітераційний алгоритм оптимізації (першого порядку), в якому для знаходження локального мінімуму функції здійснюються кроки, пропорційні протилежному значенню градієнту (або наближеного градієнту) функції в поточній точці. Якщо натомість здійснюються кроки пропорційно самому значенню градієнту, то відбувається наближення до локального максимуму цієї функції; і ця процедура тоді відома як градіє́нтний підйо́м (англ. gradient ascent).
Градієнтний спуск відомий також як найшви́дший спуск (англ. steepest descent), або ме́тод найшви́дшого спу́ску (англ. method of steepest descent). Градієнтний спуск не слід плутати з [en] для наближення інтегралів.
Опис
Градієнтний спуск ґрунтується на тому спостереженні, що якщо [en] є [en] та диференційовною в околі точки , то зменшується найшвидше, якщо йти від в напрямку, протилежному градієнтові в , . З цього випливає, що якщо
для достатньо малого , то . Іншими словами, член віднімається від , оскільки ми хочемо рухатися проти градієнту, тобто вниз до мінімуму. Враховуючи це спостереження, починають з припущення про локальний мінімум , і розглядають таку послідовність , що
Ми маємо
і тому сподіваємося, що послідовність збігається до бажаного локального мінімуму. Зауважте, що значення розміру кроку (англ. step size) дозволено змінювати на кожній ітерації. Для деяких припущень стосовно функції (наприклад, що є опуклою, а задовольняє умові Ліпшиця) і певних варіантах вибору (наприклад, якщо його вибирають лінійним пошуком, який задовольняє умови Вольфе), збіжність до локального мінімуму може бути гарантовано. Якщо функція є опуклою, то всі локальні мінімуми є також і глобальними мінімумами, тому в такому випадку градієнтний спуск може збігатися до глобального розв'язку.
Цей процес проілюстровано на зображенні праворуч. Тут припускається, що визначено на площині, і що її графік має форму чаші. Сині криві є ізолініями, тобто областями, в яких значення є сталим. Червоні стрілки, які виходять з точок, показують напрям, протилежний градієнтові в цій точці. Зауважте, що (анти)градієнт у точці є ортогональним до ізолінії, яка проходить цією точкою. Видно, що спуск градієнтом веде нас до дна чаші, тобто до точки, в якій значення функції є мінімальним.
Приклади
Градієнтний спуск має проблеми з патологічними функціями, такими як показана тут функція Розенброка.
Функція Розенброка має вузьку вигнуту долину, яка містить мінімум. Дно цієї долини є дуже пологим. Через вигнутість пологої долини оптимізація повільно рухається в напрямку мінімуму зиґзаґом кроками малого розміру.
«Зиґзаґоподібна» природа цього методу також є очевидною нижче, де градієнтний спуск застосовано до .
Обмеження
Для деяких із наведених вище прикладів градієнтний спуск є відносно повільним поблизу мінімуму: з технічної точки зору, його асимптотичний темп збігання поступається багатьом іншим методам. Для невдало обумовлених опуклих задач градієнтний спуск «зиґзаґує» все більше, коли градієнт вказує майже ортогонально до найкоротшого напряму до точки мінімуму. Докладніше див. коментарі нижче.
Для недиференційовних функцій градієнтні методи є недостатньо визначеними. Для локально ліпшицевих задач, та особливо для задач опуклої оптимізації, цілком визначеними є в'язкові методи спуску. Також можуть застосовуватися не-спускові методи, такі як методи субградієнтної проєкції. Ці методи зазвичай є повільнішими за градієнтний спуск. Іншою альтернативою для недиференційовних функцій є «згладжування» цих функцій, або обмеження функції гладкою функцією. За цього підходу розв'язують згладжену задачу в надії, що відповідь для неї є близькою до відповіді на незгладжену задачу (іноді це може бути зроблено строгим).
Розв'язання лінійної системи
Градієнтний спуск може застосовуватися для розв'язання системи лінійних рівнянь, переформульованого як задача квадратичної мінімізації, наприклад, із застосуванням методу найменших квадратів. Розв'язок
у сенсі методу найменших квадратів визначається як мінімізація функції
В традиційному методі найменших квадратів для дійсних та використовується евклідова норма, і в цьому випадку
В такому випадку мінімізація лінійним пошуком, яка знаходить на кожній ітерації локально оптимальний розмір кроку , може виконуватися аналітично, і явні формули локально оптимального є відомими.
Для розв'язання лінійних рівнянь градієнтний спуск застосовується рідко, а однією з найпопулярніших альтернатив є метод спряжених градієнтів. Швидкість збігання градієнтного спуску залежить від максимального та мінімального власних значень , тоді як швидкість збігання спряжених градієнтів має складнішу залежність від цих власних значень, і може отримувати користь від [en]. Градієнтний спуск також отримує користь від передобумовлювання, але це не роблять так поширено.
Розв'язання нелінійної системи
Градієнтний спуск може також застосовуватися і до розв'язання систем нелінійних рівнянь. Нижче наведено приклад, як застосовувати градієнтний спуск для розв'язання для трьох невідомих змінних, x1, x2 та x3. Цей приклад показує одну ітерацію градієнтного спуску.
Розгляньмо систему нелінійних рівнянь
припустімо, що ми маємо функцію
де
та цільову функцію
з початковим припущенням
Ми знаємо, що
де
Потім обчислімо ці члени в
Отже,
та
Тепер мусить бути знайдено придатний , такий що . Це можна зробити за допомогою будь-якого з безлічі алгоритмів лінійного пошуку. Можна також просто припустити , що дає
При обчисленні на цьому значенні
Зменшення з до значення наступного кроку є відчутним зменшенням цільової функції. Подальші кроки знижуватимуть її значення доти, доки не буде знайдено розв'язок системи.
Коментарі
Градієнтний спуск працює в просторах з будь-яким числом вимірів, навіть у нескінченновимірних. В останньому випадку простір пошуку зазвичай є простором функцій, і для визначення напрямку спуску здійснюється обчислення похідної Гато функціоналу, який мінімізують.
Якщо кривина заданої функції дуже різниться в різних напрямках, то градієнтному спускові може знадобитися багато ітерацій для обчислення локального мінімуму з потрібною точністю. Для таких функцій повільне збігання лікується [en], яке змінює геометрію простору так, щоби надати множинам рівнів функції форми концентричних кіл. Проте побудова та застосування передобумовлювання можуть бути обчислювально витратними.
Градієнтний спуск можна поєднувати з лінійним пошуком, який на кожній ітерації шукає локально оптимальний розмір кроку . Виконання лінійного пошуку може бути витратним за часом. З іншого боку, застосування незмінного малого може давати погану збіжність.
Кращими альтернативами можуть бути методи на основі методу Ньютона та обернення гессіану із застосуванням методик спряжених градієнтів. Загалом такі методи збігаються за меншу кількість ітерацій, але вартість кожної ітерації є вищою. Прикладом є Метод БФГШ, який складається з обчислення на кожному кроці матриці, на яку множиться вектор градієнту, щоби йти в «найкращому» напрямку, поєднаного зі складнішим алгоритмом лінійного пошуку для знаходження «найкращого» значення . Для надзвичайно великих задач, у яких домінують питання комп'ютерної пам'яті, замість БФГШ або найшвидшого спуску повинні застосовуватися методи з обмеженою пам'яттю, такі як [en].
Градієнтний спуск може розглядатися як метод Ейлера для розв'язання звичайних диференційних рівнянь потоку градієнта.
Обчислювальні приклади
Python
Алгоритм градієнтного спуску застосовується для знаходження локального мінімуму функції f(x)=x4−3x3+2 з похідною f'(x)=4x3−9x2. Ось реалізація мовою програмування Python.
# Виходячи з обчислень, ми очікуємо, що локальний мінімум матиме місце в x=9/4 x_old = 0 # Це значення не важливе, оскільки abs(x_new - x_old) > precision x_new = 6 # Алгоритм стартує з x=6 gamma = 0.01 # розмір кроку precision = 0.00001 def f_derivative(x): return 4 * x**3 - 9 * x**2 while abs(x_new - x_old) > precision: x_old = x_new x_new = x_old - gamma * f_derivative(x_old) print("Локальний мінімум має місце в", x_new)
Наведений вище фрагмент коду має бути змінено по відношенню до розміру кроку відповідно до системи, яка є під руками, а збіжність може бути зроблено швидшою шляхом застосування адаптивного розміру кроку. В наведеному вище випадку розмір кроку не є адаптивним. Він залишається на рівні 0.01 в усіх напрямках, що може іноді призводити до невдачі методу за рахунок відхилення від мінімуму.
MATLAB
Наступний код MATLAB демонструє конкретне рішення для розв'язання системи нелінійних рівнянь, представленої в попередньому розділі:
% Багатовимірна вектор-функція G(x) G = @(x) [ 3*x(1) - cos(x(2)*x(3)) - 3/2 ; 4*x(1)^2 - 625*x(2)^2 + 2*x(2) - 1 ; exp(-x(1)*x(2)) + 20*x(3) + (10*pi-3)/3]; % Якобіан G JG = @(x) [ 3, sin(x(2)*x(3))*x(3), sin(x(2)*x(3))*x(2) ; 8*x(1), -1250*x(2)+2, 0 ; -x(2)*exp(-x(1)*x(2)), -x(1)*exp(-x(1)*x(2)), 20 ]; % Цільова функція F(x), яку потрібно мінімізувати, щоби розв'язати G(x)=0 F = @(x) 0.5 * sum(G(x).^2); % Градієнт F (часткові похідні) dF = @(x) JG(x).' * G(x); % Параметри GAMMA = 0.001; % розмір кроку (темп навчання) MAX_ITER = 1000; % максимальне число ітерацій FUNC_TOL = 0.1; % кінцеве допустиме відхилення F(x) fvals = []; % зберігання значень F(x) протягом ітерацій progress = @(iter,x) fprintf('iter = %3d: x = %-32s, F(x) = %f\n', ... iter, mat2str(x,6), F(x)); % Ітерування iter = 1; % лічильник ітерацій x = [0; 0; 0]; % початкове припущення fvals(iter) = F(x); progress(iter, x); while iter < MAX_ITER && fvals(end) > FUNC_TOL iter = iter + 1; x = x - GAMMA * dF(x); % градієнтний спуск fvals(iter) = F(x); % обчислити цільову функцію progress(iter, x); % показати перебіг end % Накреслити plot(1:iter, fvals, 'LineWidth',2); grid on; title('Objective Function'); xlabel('Iteration'); ylabel('F(x)'); % Обчислити кінцевий розв'язок системи рівнянь G(x)=0 disp('G(x) = '); disp(G(x)) % Виведення: % % iter = 1: x = [0;0;0] , F(x) = 58.456136 % iter = 2: x = [0.0075;0.002;-0.20944] , F(x) = 23.306394 % iter = 3: x = [0.015005;0.0015482;-0.335103] , F(x) = 10.617030 % ... % iter = 187: x = [0.683335;0.0388258;-0.52231] , F(x) = 0.101161 % iter = 188: x = [0.684666;0.0389831;-0.522302] , F(x) = 0.099372 % % (збіглося за 188 ітерацій після перевищення кінцевого допустимого відхилення F(x))
Розширення
Градієнтний спуск може бути розширено для підтримки обмежень шляхом включення проєкції на множину обмежень. Цей метод підходить лише тоді, коли ця проєкція є ефективно обчислюваною на комп'ютері. За зручних припущень цей метод збігається. Цей метод є окремим випадком для монотонних включень (який включає опукле програмування та [en]).
Швидкий проксимальний градієнтний метод
Інше розширення градієнтного спуску виникло завдяки [en] 1983 року, і було згодом узагальнене. Він пропонує просту видозміну цього алгоритму, яка уможливлює швидке збігання для опуклих задач. А саме, якщо функція є опуклою, а є ліпшицевою, і немає припущення, що є сильно опуклою, то похибку цільового значення, породжувану методом градієнтного спуску на кожному кроці , буде обмежено . Із застосуванням методики прискорення Нестерова похибка знижується до .
Метод імпульсу
Ще одним розширенням, яке знижує ризик застрягнути в локальному мінімумі, а також істотно прискорює збіжність у випадках, коли інакше процес би сильно зиґзаґував, є метод імпульсу (англ. momentum method), який використовує член імпульсу по аналогії з «масою ньютонових частинок, які рухаються в'язким середовищем у консервативному силовому полі». Цей метод часто використовують як розширення алгоритмів зворотного поширення, що застосовуються для тренування штучних нейронних мереж.
Див. також
Примітки
- Kiwiel, Krzysztof C. (2001). Convergence and efficiency of subgradient methods for quasiconvex minimization. Mathematical Programming (Series A). Т. 90, № 1. Berlin, Heidelberg: Springer. с. 1—25. doi:10.1007/PL00011414. ISSN 0025-5610. MR 1819784. (англ.)
- Yuan, Ya-xiang (1999). Step-sizes for the gradient method (PDF). AMS/IP Studies in Advanced Mathematics. Providence, RI: American Mathematical Society. 42 (2): 785.
{{}}
: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url () (англ.) - G. P. Akilov, L. V. Kantorovich, Functional Analysis, Pergamon Pr; 2 Sub edition, , 1982 (англ.)
- W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C: The Art of Scientific Computing, 2nd Ed., Cambridge University Press, New York, 1992 (англ.)
- T. Strutz: Data Fitting and Uncertainty (A practical introduction to weighted least squares and beyond). 2nd edition, Springer Vieweg, 2016, . (англ.)
- P. L. Combettes and J.-C. Pesquet, «Proximal splitting methods in signal processing» [ 7 липня 2011 у Wayback Machine.], in: Fixed-Point Algorithms for Inverse Problems in Science and Engineering, (H. H. Bauschke, R. S. Burachik, P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowicz, Editors), pp. 185—212. Springer, New York, 2011. (англ.)
- Yu. Nesterov, «Introductory Lectures on Convex Optimization. A Basic Course» (Springer, 2004, ) (англ.)
- Fast Gradient Methods [ 24 грудня 2012 у Wayback Machine.], lecture notes by Prof. Lieven Vandenberghe for EE236C at UCLA (англ.)
- Qian, Ning (January 1999). (PDF). [en]. 12 (1): 145—151. Архів оригіналу (PDF) за 8 травня 2014. Процитовано 17 жовтня 2014. (англ.)
- . [en]. Архів оригіналу за 21 жовтня 2014. Процитовано 17 жовтня 2014. (англ.)
- Geoffrey Hinton; Nitish Srivastava; Kevin Swersky. . YouTube. Архів оригіналу за 10 травня 2015. Процитовано 18 жовтня 2014. Частина з серії лекцій для онлайн-курсу Coursera Neural Networks for Machine Learning [ 29 червня 2016 у Wayback Machine.]. (англ.)
Джерела
- Mordecai Avriel (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. . (англ.)
- Jan A. Snyman (2005). Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms. Springer Publishing. (англ.)
- Raad Z. Homod, K. S. M. Sahari, H. A.F. Almurib, F. H. Nagi, Gradient auto-tuned Takagi-Sugeno fuzzy forward control of a HVAC system using predicted mean vote index Energy and Buildings, 49 (6) (2012) 254—267 [ 11 грудня 2018 у Wayback Machine.] (англ.)
- Cauchy, Augustin (1847). . с. 536—538. Архів оригіналу за 13 жовтня 2016. Процитовано 31 липня 2016. (фр.)
- Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973., , , т. 2, ст. 64.
Посилання
- Застосування градієнтного спуску в C++, Boost, Ublas для лінійної регресії [ 22 липня 2013 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cya stattya pro algoritm optimizaciyi Pro metod nablizhennya integraliv u matematichnomu analizi div en Gradiye ntnij spusk angl gradient descent ce iteracijnij algoritm optimizaciyi pershogo poryadku v yakomu dlya znahodzhennya lokalnogo minimumu funkciyi zdijsnyuyutsya kroki proporcijni protilezhnomu znachennyu gradiyentu abo nablizhenogo gradiyentu funkciyi v potochnij tochci Yaksho natomist zdijsnyuyutsya kroki proporcijno samomu znachennyu gradiyentu to vidbuvayetsya nablizhennya do lokalnogo maksimumu ciyeyi funkciyi i cya procedura todi vidoma yak gradiye ntnij pidjo m angl gradient ascent Gradiyentnij spusk vidomij takozh yak najshvi dshij spusk angl steepest descent abo me tod najshvi dshogo spu sku angl method of steepest descent Gradiyentnij spusk ne slid plutati z en dlya nablizhennya integraliv OpisIlyustraciya metodu najshvidshogo spusku na ryadi mnozhin rivniv Gradiyentnij spusk gruntuyetsya na tomu sposterezhenni sho yaksho en F x displaystyle F mathbf x ye en ta diferencijovnoyu v okoli tochki a displaystyle mathbf a to F x displaystyle F mathbf x zmenshuyetsya najshvidshe yaksho jti vid a displaystyle mathbf a v napryamku protilezhnomu gradiyentovi F displaystyle F v a displaystyle mathbf a F a displaystyle nabla F mathbf a Z cogo viplivaye sho yaksho b a g F a displaystyle mathbf b mathbf a gamma nabla F mathbf a dlya dostatno malogo g displaystyle gamma to F a F b displaystyle F mathbf a geq F mathbf b Inshimi slovami chlen g F a displaystyle gamma nabla F mathbf a vidnimayetsya vid a displaystyle mathbf a oskilki mi hochemo ruhatisya proti gradiyentu tobto vniz do minimumu Vrahovuyuchi ce sposterezhennya pochinayut z pripushennya x 0 displaystyle mathbf x 0 pro lokalnij minimum F displaystyle F i rozglyadayut taku poslidovnist x 0 x 1 x 2 displaystyle mathbf x 0 mathbf x 1 mathbf x 2 dots sho x n 1 x n g n F x n n 0 displaystyle mathbf x n 1 mathbf x n gamma n nabla F mathbf x n n geq 0 Mi mayemo F x 0 F x 1 F x 2 displaystyle F mathbf x 0 geq F mathbf x 1 geq F mathbf x 2 geq cdots i tomu spodivayemosya sho poslidovnist x n displaystyle mathbf x n zbigayetsya do bazhanogo lokalnogo minimumu Zauvazhte sho znachennya rozmiru kroku angl step size g displaystyle gamma dozvoleno zminyuvati na kozhnij iteraciyi Dlya deyakih pripushen stosovno funkciyi F displaystyle F napriklad sho F displaystyle F ye opukloyu a F displaystyle nabla F zadovolnyaye umovi Lipshicya i pevnih variantah viboru g displaystyle gamma napriklad yaksho jogo vibirayut linijnim poshukom yakij zadovolnyaye umovi Volfe zbizhnist do lokalnogo minimumu mozhe buti garantovano Yaksho funkciya F displaystyle F ye opukloyu to vsi lokalni minimumi ye takozh i globalnimi minimumami tomu v takomu vipadku gradiyentnij spusk mozhe zbigatisya do globalnogo rozv yazku Cej proces proilyustrovano na zobrazhenni pravoruch Tut pripuskayetsya sho F displaystyle F viznacheno na ploshini i sho yiyi grafik maye formu chashi Sini krivi ye izoliniyami tobto oblastyami v yakih znachennya F displaystyle F ye stalim Chervoni strilki yaki vihodyat z tochok pokazuyut napryam protilezhnij gradiyentovi v cij tochci Zauvazhte sho anti gradiyent u tochci ye ortogonalnim do izoliniyi yaka prohodit ciyeyu tochkoyu Vidno sho spusk gradiyentom vede nas do dna chashi tobto do tochki v yakij znachennya funkciyi F displaystyle F ye minimalnim Prikladi Gradiyentnij spusk maye problemi z patologichnimi funkciyami takimi yak pokazana tut funkciya Rozenbroka f x 1 x 2 1 x 1 2 100 x 2 x 1 2 2 displaystyle f x 1 x 2 1 x 1 2 100 x 2 x 1 2 2 quad Funkciya Rozenbroka maye vuzku vignutu dolinu yaka mistit minimum Dno ciyeyi dolini ye duzhe pologim Cherez vignutist pologoyi dolini optimizaciya povilno ruhayetsya v napryamku minimumu zigzagom krokami malogo rozmiru Zigzagopodibna priroda cogo metodu takozh ye ochevidnoyu nizhche de gradiyentnij spusk zastosovano do F x y sin 1 2 x 2 1 4 y 2 3 cos 2 x 1 e y displaystyle F x y sin left frac 1 2 x 2 frac 1 4 y 2 3 right cos 2x 1 e y Obmezhennya Dlya deyakih iz navedenih vishe prikladiv gradiyentnij spusk ye vidnosno povilnim poblizu minimumu z tehnichnoyi tochki zoru jogo asimptotichnij temp zbigannya postupayetsya bagatom inshim metodam Dlya nevdalo obumovlenih opuklih zadach gradiyentnij spusk zigzaguye vse bilshe koli gradiyent vkazuye majzhe ortogonalno do najkorotshogo napryamu do tochki minimumu Dokladnishe div komentari nizhche Dlya nediferencijovnih funkcij gradiyentni metodi ye nedostatno viznachenimi Dlya lokalno lipshicevih zadach ta osoblivo dlya zadach opukloyi optimizaciyi cilkom viznachenimi ye v yazkovi metodi spusku Takozh mozhut zastosovuvatisya ne spuskovi metodi taki yak metodi subgradiyentnoyi proyekciyi Ci metodi zazvichaj ye povilnishimi za gradiyentnij spusk Inshoyu alternativoyu dlya nediferencijovnih funkcij ye zgladzhuvannya cih funkcij abo obmezhennya funkciyi gladkoyu funkciyeyu Za cogo pidhodu rozv yazuyut zgladzhenu zadachu v nadiyi sho vidpovid dlya neyi ye blizkoyu do vidpovidi na nezgladzhenu zadachu inodi ce mozhe buti zrobleno strogim Rozv yazannya linijnoyi sistemiGradiyentnij spusk mozhe zastosovuvatisya dlya rozv yazannya sistemi linijnih rivnyan pereformulovanogo yak zadacha kvadratichnoyi minimizaciyi napriklad iz zastosuvannyam metodu najmenshih kvadrativ Rozv yazok A x b 0 displaystyle A mathbf x mathbf b 0 u sensi metodu najmenshih kvadrativ viznachayetsya yak minimizaciya funkciyi F x A x b 2 displaystyle F mathbf x A mathbf x mathbf b 2 V tradicijnomu metodi najmenshih kvadrativ dlya dijsnih A displaystyle A ta b displaystyle mathbf b vikoristovuyetsya evklidova norma i v comu vipadku F x 2 A T A x b displaystyle nabla F mathbf x 2A T A mathbf x mathbf b V takomu vipadku minimizaciya linijnim poshukom yaka znahodit na kozhnij iteraciyi lokalno optimalnij rozmir kroku g displaystyle gamma mozhe vikonuvatisya analitichno i yavni formuli lokalno optimalnogo g displaystyle gamma ye vidomimi Dlya rozv yazannya linijnih rivnyan gradiyentnij spusk zastosovuyetsya ridko a odniyeyu z najpopulyarnishih alternativ ye metod spryazhenih gradiyentiv Shvidkist zbigannya gradiyentnogo spusku zalezhit vid maksimalnogo ta minimalnogo vlasnih znachen A displaystyle A todi yak shvidkist zbigannya spryazhenih gradiyentiv maye skladnishu zalezhnist vid cih vlasnih znachen i mozhe otrimuvati korist vid en Gradiyentnij spusk takozh otrimuye korist vid peredobumovlyuvannya ale ce ne roblyat tak poshireno Rozv yazannya nelinijnoyi sistemiGradiyentnij spusk mozhe takozh zastosovuvatisya i do rozv yazannya sistem nelinijnih rivnyan Nizhche navedeno priklad yak zastosovuvati gradiyentnij spusk dlya rozv yazannya dlya troh nevidomih zminnih x1 x2 ta x3 Cej priklad pokazuye odnu iteraciyu gradiyentnogo spusku Rozglyanmo sistemu nelinijnih rivnyan 3 x 1 cos x 2 x 3 3 2 0 4 x 1 2 625 x 2 2 2 x 2 1 0 exp x 1 x 2 20 x 3 10 p 3 3 0 displaystyle begin cases 3x 1 cos x 2 x 3 tfrac 3 2 0 4x 1 2 625x 2 2 2x 2 1 0 exp x 1 x 2 20x 3 tfrac 10 pi 3 3 0 end cases pripustimo sho mi mayemo funkciyu G x 3 x 1 cos x 2 x 3 3 2 4 x 1 2 625 x 2 2 2 x 2 1 exp x 1 x 2 20 x 3 10 p 3 3 displaystyle G mathbf x begin bmatrix 3x 1 cos x 2 x 3 tfrac 3 2 4x 1 2 625x 2 2 2x 2 1 exp x 1 x 2 20x 3 tfrac 10 pi 3 3 end bmatrix de x x 1 x 2 x 3 displaystyle mathbf x begin bmatrix x 1 x 2 x 3 end bmatrix ta cilovu funkciyu F x 1 2 G T x G x 1 2 3 x 1 cos x 2 x 3 3 2 2 4 x 1 2 625 x 2 2 2 x 2 1 2 exp x 1 x 2 20 x 3 1 3 10 p 3 2 displaystyle F mathbf x tfrac 1 2 G mathrm T mathbf x G mathbf x tfrac 1 2 left left 3x 1 cos x 2 x 3 tfrac 3 2 right 2 left 4x 1 2 625x 2 2 2x 2 1 right 2 left exp x 1 x 2 20x 3 tfrac 1 3 10 pi 3 right 2 right z pochatkovim pripushennyam x 0 x 1 x 2 x 3 0 0 0 displaystyle mathbf x 0 begin bmatrix x 1 x 2 x 3 end bmatrix begin bmatrix 0 0 0 end bmatrix Mi znayemo sho x 1 x 0 g 0 F x 0 displaystyle mathbf x 1 mathbf x 0 gamma 0 nabla F mathbf x 0 de F x 0 J G x 0 T G x 0 displaystyle nabla F mathbf x 0 J G mathbf x 0 mathrm T G mathbf x 0 Matricya Yakobi J G x 0 displaystyle J G mathbf x 0 J G 3 sin x 2 x 3 x 3 sin x 2 x 3 x 2 8 x 1 1250 x 2 2 0 x 2 exp x 1 x 2 x 1 exp x 1 x 2 20 displaystyle J G begin bmatrix 3 amp sin x 2 x 3 x 3 amp sin x 2 x 3 x 2 8x 1 amp 1250x 2 2 amp 0 x 2 exp x 1 x 2 amp x 1 exp x 1 x 2 amp 20 end bmatrix Potim obchislimo ci chleni v x 0 displaystyle mathbf x 0 J G x 0 3 0 0 0 2 0 0 0 20 G x 0 2 5 1 10 472 displaystyle J G left mathbf x 0 right begin bmatrix 3 amp 0 amp 0 0 amp 2 amp 0 0 amp 0 amp 20 end bmatrix qquad G mathbf x 0 begin bmatrix 2 5 1 10 472 end bmatrix Otzhe x 1 0 g 0 7 5 2 209 44 displaystyle mathbf x 1 0 gamma 0 begin bmatrix 7 5 2 209 44 end bmatrix ta F x 0 0 5 2 5 2 1 2 10 472 2 58 456 displaystyle F left mathbf x 0 right 0 5 left 2 5 2 1 2 10 472 2 right 58 456 Animaciya yaka pokazuye pershi 83 iteraciyi gradiyentnogo spusku sho zastosovuyetsya do cogo prikladu Poverhni ye izopoverhnyami F x n displaystyle F mathbf x n na potochnomu pripushenni x n displaystyle mathbf x n a strilki pokazuyut napryamok spusku Z prichini malogo ta nezminnogo kroku zbigannya ye povilnim Teper musit buti znajdeno pridatnij g 0 displaystyle gamma 0 takij sho F x 1 F x 0 displaystyle F mathbf x 1 leq F mathbf x 0 Ce mozhna zrobiti za dopomogoyu bud yakogo z bezlichi algoritmiv linijnogo poshuku Mozhna takozh prosto pripustiti g 0 0 001 displaystyle gamma 0 0 001 sho daye x 1 0 0075 0 002 0 20944 displaystyle mathbf x 1 begin bmatrix 0 0075 0 002 0 20944 end bmatrix Pri obchislenni na comu znachenni F x 1 0 5 2 48 2 1 00 2 6 28 2 23 306 displaystyle F left mathbf x 1 right 0 5 left 2 48 2 1 00 2 6 28 2 right 23 306 Zmenshennya z F x 0 58 456 displaystyle F mathbf x 0 58 456 do znachennya nastupnogo kroku F x 1 23 306 displaystyle F mathbf x 1 23 306 ye vidchutnim zmenshennyam cilovoyi funkciyi Podalshi kroki znizhuvatimut yiyi znachennya doti doki ne bude znajdeno rozv yazok sistemi KomentariGradiyentnij spusk pracyuye v prostorah z bud yakim chislom vimiriv navit u neskinchennovimirnih V ostannomu vipadku prostir poshuku zazvichaj ye prostorom funkcij i dlya viznachennya napryamku spusku zdijsnyuyetsya obchislennya pohidnoyi Gato funkcionalu yakij minimizuyut Yaksho krivina zadanoyi funkciyi duzhe riznitsya v riznih napryamkah to gradiyentnomu spuskovi mozhe znadobitisya bagato iteracij dlya obchislennya lokalnogo minimumu z potribnoyu tochnistyu Dlya takih funkcij povilne zbigannya likuyetsya en yake zminyuye geometriyu prostoru tak shobi nadati mnozhinam rivniv funkciyi formi koncentrichnih kil Prote pobudova ta zastosuvannya peredobumovlyuvannya mozhut buti obchislyuvalno vitratnimi Gradiyentnij spusk mozhna poyednuvati z linijnim poshukom yakij na kozhnij iteraciyi shukaye lokalno optimalnij rozmir kroku g displaystyle gamma Vikonannya linijnogo poshuku mozhe buti vitratnim za chasom Z inshogo boku zastosuvannya nezminnogo malogo g displaystyle gamma mozhe davati poganu zbizhnist Krashimi alternativami mozhut buti metodi na osnovi metodu Nyutona ta obernennya gessianu iz zastosuvannyam metodik spryazhenih gradiyentiv Zagalom taki metodi zbigayutsya za menshu kilkist iteracij ale vartist kozhnoyi iteraciyi ye vishoyu Prikladom ye Metod BFGSh yakij skladayetsya z obchislennya na kozhnomu kroci matrici na yaku mnozhitsya vektor gradiyentu shobi jti v najkrashomu napryamku poyednanogo zi skladnishim algoritmom linijnogo poshuku dlya znahodzhennya najkrashogo znachennya g displaystyle gamma Dlya nadzvichajno velikih zadach u yakih dominuyut pitannya komp yuternoyi pam yati zamist BFGSh abo najshvidshogo spusku povinni zastosovuvatisya metodi z obmezhenoyu pam yattyu taki yak en Gradiyentnij spusk mozhe rozglyadatisya yak metod Ejlera dlya rozv yazannya zvichajnih diferencijnih rivnyan x t f x t displaystyle x t nabla f x t potoku gradiyenta Obchislyuvalni prikladiPython Algoritm gradiyentnogo spusku zastosovuyetsya dlya znahodzhennya lokalnogo minimumu funkciyi f x x4 3x3 2 z pohidnoyu f x 4x3 9x2 Os realizaciya movoyu programuvannya Python Vihodyachi z obchislen mi ochikuyemo sho lokalnij minimum matime misce v x 9 4 x old 0 Ce znachennya ne vazhlive oskilki abs x new x old gt precision x new 6 Algoritm startuye z x 6 gamma 0 01 rozmir kroku precision 0 00001 def f derivative x return 4 x 3 9 x 2 while abs x new x old gt precision x old x new x new x old gamma f derivative x old print Lokalnij minimum maye misce v x new Navedenij vishe fragment kodu maye buti zmineno po vidnoshennyu do rozmiru kroku vidpovidno do sistemi yaka ye pid rukami a zbizhnist mozhe buti zrobleno shvidshoyu shlyahom zastosuvannya adaptivnogo rozmiru kroku V navedenomu vishe vipadku rozmir kroku ne ye adaptivnim Vin zalishayetsya na rivni 0 01 v usih napryamkah sho mozhe inodi prizvoditi do nevdachi metodu za rahunok vidhilennya vid minimumu MATLAB Nastupnij kod MATLAB demonstruye konkretne rishennya dlya rozv yazannya sistemi nelinijnih rivnyan predstavlenoyi v poperednomu rozdili 3 x 1 cos x 2 x 3 3 2 0 4 x 1 2 625 x 2 2 2 x 2 1 0 exp x 1 x 2 20 x 3 10 p 3 3 0 displaystyle begin cases 3x 1 cos x 2 x 3 tfrac 3 2 0 4x 1 2 625x 2 2 2x 2 1 0 exp x 1 x 2 20x 3 tfrac 10 pi 3 3 0 end cases Bagatovimirna vektor funkciya G x G x 3 x 1 cos x 2 x 3 3 2 4 x 1 2 625 x 2 2 2 x 2 1 exp x 1 x 2 20 x 3 10 pi 3 3 Yakobian G JG x 3 sin x 2 x 3 x 3 sin x 2 x 3 x 2 8 x 1 1250 x 2 2 0 x 2 exp x 1 x 2 x 1 exp x 1 x 2 20 Cilova funkciya F x yaku potribno minimizuvati shobi rozv yazati G x 0 F x 0 5 sum G x 2 Gradiyent F chastkovi pohidni dF x JG x G x Parametri GAMMA 0 001 rozmir kroku temp navchannya MAX ITER 1000 maksimalne chislo iteracij FUNC TOL 0 1 kinceve dopustime vidhilennya F x fvals zberigannya znachen F x protyagom iteracij progress iter x fprintf iter 3d x 32s F x f n iter mat2str x 6 F x Iteruvannya iter 1 lichilnik iteracij x 0 0 0 pochatkove pripushennya fvals iter F x progress iter x while iter lt MAX ITER amp amp fvals end gt FUNC TOL iter iter 1 x x GAMMA dF x gradiyentnij spusk fvals iter F x obchisliti cilovu funkciyu progress iter x pokazati perebig end Nakresliti plot 1 iter fvals LineWidth 2 grid on title Objective Function xlabel Iteration ylabel F x Obchisliti kincevij rozv yazok sistemi rivnyan G x 0 disp G x disp G x Vivedennya iter 1 x 0 0 0 F x 58 456136 iter 2 x 0 0075 0 002 0 20944 F x 23 306394 iter 3 x 0 015005 0 0015482 0 335103 F x 10 617030 iter 187 x 0 683335 0 0388258 0 52231 F x 0 101161 iter 188 x 0 684666 0 0389831 0 522302 F x 0 099372 zbiglosya za 188 iteracij pislya perevishennya kincevogo dopustimogo vidhilennya F x RozshirennyaGradiyentnij spusk mozhe buti rozshireno dlya pidtrimki obmezhen shlyahom vklyuchennya proyekciyi na mnozhinu obmezhen Cej metod pidhodit lishe todi koli cya proyekciya ye efektivno obchislyuvanoyu na komp yuteri Za zruchnih pripushen cej metod zbigayetsya Cej metod ye okremim vipadkom dlya monotonnih vklyuchen yakij vklyuchaye opukle programuvannya ta en Shvidkij proksimalnij gradiyentnij metod Inshe rozshirennya gradiyentnogo spusku viniklo zavdyaki en 1983 roku i bulo zgodom uzagalnene Vin proponuye prostu vidozminu cogo algoritmu yaka umozhlivlyuye shvidke zbigannya dlya opuklih zadach A same yaksho funkciya F displaystyle F ye opukloyu a F displaystyle nabla F ye lipshicevoyu i nemaye pripushennya sho F displaystyle F ye silno opukloyu to pohibku cilovogo znachennya porodzhuvanu metodom gradiyentnogo spusku na kozhnomu kroci k displaystyle k bude obmezheno O 1 k displaystyle mathcal O 1 k Iz zastosuvannyam metodiki priskorennya Nesterova pohibka znizhuyetsya do O 1 k 2 displaystyle mathcal O 1 k 2 Metod impulsu She odnim rozshirennyam yake znizhuye rizik zastryagnuti v lokalnomu minimumi a takozh istotno priskoryuye zbizhnist u vipadkah koli inakshe proces bi silno zigzaguvav ye metod impulsu angl momentum method yakij vikoristovuye chlen impulsu po analogiyi z masoyu nyutonovih chastinok yaki ruhayutsya v yazkim seredovishem u konservativnomu silovomu poli Cej metod chasto vikoristovuyut yak rozshirennya algoritmiv zvorotnogo poshirennya sho zastosovuyutsya dlya trenuvannya shtuchnih nejronnih merezh Div takozhMetod spryazhenogo gradiyenta Metod proksimalnogo gradiyenta Stohastichnij gradiyentnij spusk en Delta pravilo Umovi Volfe en Metod BFGSh Metod Neldera Mida Algoritm Frank VulfaPrimitkiKiwiel Krzysztof C 2001 Convergence and efficiency of subgradient methods for quasiconvex minimization Mathematical Programming Series A T 90 1 Berlin Heidelberg Springer s 1 25 doi 10 1007 PL00011414 ISSN 0025 5610 MR 1819784 angl Yuan Ya xiang 1999 Step sizes for the gradient method PDF AMS IP Studies in Advanced Mathematics Providence RI American Mathematical Society 42 2 785 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite journal title Shablon Cite journal cite journal a Obslugovuvannya CS1 Storinki z parametrom url status ale bez parametra archive url posilannya angl G P Akilov L V Kantorovich Functional Analysis Pergamon Pr 2 Sub edition ISBN 0 08 023036 9 1982 angl W H Press S A Teukolsky W T Vetterling B P Flannery Numerical Recipes in C The Art of Scientific Computing 2nd Ed Cambridge University Press New York 1992 angl T Strutz Data Fitting and Uncertainty A practical introduction to weighted least squares and beyond 2nd edition Springer Vieweg 2016 ISBN 978 3 658 11455 8 angl P L Combettes and J C Pesquet Proximal splitting methods in signal processing 7 lipnya 2011 u Wayback Machine in Fixed Point Algorithms for Inverse Problems in Science and Engineering H H Bauschke R S Burachik P L Combettes V Elser D R Luke and H Wolkowicz Editors pp 185 212 Springer New York 2011 angl Yu Nesterov Introductory Lectures on Convex Optimization A Basic Course Springer 2004 ISBN 1 4020 7553 7 angl Fast Gradient Methods 24 grudnya 2012 u Wayback Machine lecture notes by Prof Lieven Vandenberghe for EE236C at UCLA angl Qian Ning January 1999 PDF en 12 1 145 151 Arhiv originalu PDF za 8 travnya 2014 Procitovano 17 zhovtnya 2014 angl en Arhiv originalu za 21 zhovtnya 2014 Procitovano 17 zhovtnya 2014 angl Geoffrey Hinton Nitish Srivastava Kevin Swersky YouTube Arhiv originalu za 10 travnya 2015 Procitovano 18 zhovtnya 2014 Chastina z seriyi lekcij dlya onlajn kursu Coursera Neural Networks for Machine Learning 29 chervnya 2016 u Wayback Machine angl DzherelaMordecai Avriel 2003 Nonlinear Programming Analysis and Methods Dover Publishing ISBN 0 486 43227 0 angl Jan A Snyman 2005 Practical Mathematical Optimization An Introduction to Basic Optimization Theory and Classical and New Gradient Based Algorithms Springer Publishing ISBN 0 387 24348 8 angl Raad Z Homod K S M Sahari H A F Almurib F H Nagi Gradient auto tuned Takagi Sugeno fuzzy forward control of a HVAC system using predicted mean vote index Energy and Buildings 49 6 2012 254 267 11 grudnya 2018 u Wayback Machine angl Cauchy Augustin 1847 s 536 538 Arhiv originalu za 13 zhovtnya 2016 Procitovano 31 lipnya 2016 fr Enciklopediya kibernetiki u 2 t za red V M Glushkova Kiyiv Gol red Ukrayinskoyi radyanskoyi enciklopediyi 1973 t 2 st 64 PosilannyaZastosuvannya gradiyentnogo spusku v C Boost Ublas dlya linijnoyi regresiyi 22 lipnya 2013 u Wayback Machine