градиентен метод. Преглед на градиентните методи в задачите за математическа оптимизация

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

Посоката на най-стръмното спускане съответства на посоката на най-голямото намаляване на функцията. Известно е, че посоката на най-голямо нарастване на функцията на две променливи u = f(x, y) се характеризира с нейния градиент:

където e1, e2 - единични вектори(ортове) по посока на координатните оси. Следователно посоката, противоположна на градиента, ще покаже посоката на най-голямото намаляване на функцията. Извикват се методи, базирани на избор на път за оптимизация с помощта на градиент градиент.

Идеята зад метода на градиентно спускане е следната. Избиране на начална точка

изчисляваме градиента на разглежданата функция в него. Правим стъпка в посока, обратна на градиента:

Процесът продължава, докато се получи най-малката стойност. целева функция. Строго погледнато, краят на търсенето ще дойде, когато движението от получената точка с произволна стъпка доведе до увеличаване на стойността на целевата функция. Ако минимумът на функцията е достигнат вътре в разглежданата област, тогава в този момент градиентът е равен на нула, което също може да служи като сигнал за края на процеса на оптимизация.

Методът за градиентно спускане има същия недостатък като метода за координатно спускане: при наличие на дерета на повърхността конвергенцията на метода е много бавна.

В описания метод се изисква да се изчисли градиентът на целевата функция f(x) при всяка стъпка на оптимизация:

Формули за частни производни могат да бъдат получени изрично само когато целевата функция е дадена аналитично. В противен случай тези производни се изчисляват чрез числено диференциране:

Когато се използва градиентно спускане в задачи за оптимизация, основното количество изчисления обикновено се пада върху изчисляването на градиента на целевата функция във всяка точка от траекторията на спускане. Поради това е препоръчително да се намали броят на тези точки, без да се компрометира самото решение. Това се постига в някои методи, които са модификации на градиентно спускане. Един от тях е методът за най-стръмно спускане. Съгласно този метод, след определяне на посоката, противоположна на градиента на целевата функция в началната точка, се решава едномерен оптимизационен проблем чрез минимизиране на функцията по тази посока. А именно функцията е минимизирана:

Да се ​​минимизира може да се използва един от методите за едномерна оптимизация. Възможно е също така просто да се движите в посока, обратна на градиента, като същевременно правите не една стъпка, а няколко стъпки, докато целевата функция спре да намалява. В намерената нова точка отново се определя посоката на спускане (с помощта на градиент) и се намира нова минимална точка на целевата функция и т.н. При този метод спускането става на много по-големи стъпки, а градиентът на функцията се изчислява в по-малкоточки. Разликата е, че тук посоката на едномерната оптимизация се определя от градиента на целевата функция, докато координатното спускане се извършва на всяка стъпка по една от координатните посоки.

Метод на най-стръмното спускане за случай на функция на две променливи z = f(x,y).

Първо, лесно е да се покаже, че градиентът на функцията е перпендикулярен на допирателната към линията на нивото в дадена точка. Следователно при градиентните методи спускането става по нормалата към линията на нивото. Второ, в точката, където е достигнат минимумът на целевата функция по посоката, производната на функцията по тази посока изчезва. Но производната на функцията е нула в посоката на допирателната към линията на нивото. От това следва, че градиентът на целевата функция в новата точка е перпендикулярен на посоката на едномерната оптимизация на предишната стъпка, т.е. спускането на две последователни стъпки се извършва във взаимно перпендикулярни посоки.

градиентни методи

Методите за градиентна неограничена оптимизация използват само първите производни на целевата функция и са линейни методи за приближение на всяка стъпка, т.е. целевата функция на всяка стъпка се заменя с допирателна хиперравнина към нейната графика в текущата точка.

На k-ти етапградиентни методи, преходът от точката Xk до точката Xk+1 се описва със съотношението:

където k е размерът на стъпката, k е вектор в посоката Xk+1-Xk.

Методи за най-стръмно спускане

За първи път такъв метод е разгледан и приложен от О. Коши през 18 век. Идеята му е проста: градиентът на целевата функция f(X) във всяка точка е вектор в посоката на най-голямото увеличение на стойността на функцията. Следователно антиградиентът ще бъде насочен към най-голямото намаляване на функцията и е посоката на най-стръмното спускане. Антиградиентът (и градиентът) е ортогонален на повърхността на нивото f(X) в точката X. Ако в (1.2) въведем посоката

тогава това ще бъде посоката на най-стръмното спускане в точката Xk.

Получаваме формулата за преход от Xk към Xk+1:

Антиградиентът дава само посоката на спускане, а не размера на стъпката. AT общ случайедна стъпка не дава минимална точка, така че процедурата на спускане трябва да се приложи няколко пъти. В минималната точка всички компоненти на градиента са равни на нула.

Всички градиентни методи използват горната идея и се различават един от друг по технически детайли: изчисляване на производни чрез аналитична формула или апроксимация с крайна разлика; размерът на стъпката може да бъде постоянен, да се променя според някои правила или да бъде избран след прилагане на едномерни методи за оптимизация в посока на антиградиента и др. и т.н.

Няма да се спираме подробно, т.к. методът на най-стръмното спускане обикновено не се препоръчва като сериозна процедура за оптимизация.

Един от недостатъците на този метод е, че той конвергира към всяка неподвижна точка, включително седловата точка, което не може да бъде решение.

Но най-важното е много бавната конвергенция на най-стръмното спускане в общия случай. Въпросът е, че слизането е "най-бързото" в местния смисъл. Ако хиперпространството за търсене е силно удължено ("дере"), тогава антиградиентът е насочен почти ортогонално към дъното на "дерето", т.е. най-добрата посока за достигане на минимума. В този смисъл директен превод английски термин"най-стръмно спускане", т.е. спускането по най-стръмния склон е по-съвместимо със състоянието на нещата, отколкото терминът "най-бързият", възприет в рускоезичната специализирана литература. Един изход в тази ситуация е да се използва информацията, дадена от вторите частни производни. Друг изход е да промените мащабите на променливите.

линейно приближение производен градиент

Конюгатен градиентен метод на Флетчър-Рийвс

Методът на спрегнатия градиент конструира последователност от посоки на търсене, които са линейни комбинации от текущата най-стръмна посока на спускане и предишните посоки на търсене, т.е.

и коефициентите са избрани така, че да направят посоките на търсене спрегнати. Доказа това

и това е много ценен резултат, който ви позволява да изградите бърз и ефективен алгоритъм за оптимизация.

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

1. В X0 се изчислява.

2. На k-та стъпка с едномерно търсене по посока се намира минимумът на f(X), който определя точката Xk+1.

• 3. Изчислете f(Xk+1) и.
• 4. Посоката се определя от отношението:

• 5. След (n+1)-тата итерация (т.е. с k=n) се извършва рестартиране: приема се X0=Xn+1 и се извършва преход към стъпка 1.
• 6. Алгоритъмът спира, когато

където е произволна константа.

Предимството на алгоритъма на Флетчър-Рийвс е, че той не изисква инверсия на матрицата и спестява компютърна памет, тъй като не се нуждае от матриците, използвани в методите на Нютон, но в същото време е почти толкова ефективен, колкото квази-Нютоновите алгоритми. защото посоките за търсене са взаимно спрегнати, тогава квадратичната функция ще бъде минимизирана с не повече от n стъпки. В общия случай се използва рестартиране, което ви позволява да получите резултата.

Алгоритъмът на Fletcher-Reeves е чувствителен към точността на едномерно търсене, така че всички грешки при закръгляване, които могат да възникнат, трябва да бъдат коригирани, когато се използва. Освен това алгоритъмът може да се провали в ситуации, в които Хесианът стане лошо обусловен. Алгоритъмът няма гаранция за конвергенция винаги и навсякъде, въпреки че практиката показва, че алгоритъмът почти винаги дава резултат.

Нютонови методи

Посоката на търсене, съответстваща на най-стръмното спускане, е свързана с линейно приближениецелева функция. Методите, използващи втори производни, произтичат от квадратична апроксимация на целевата функция, т.е. при разширяване на функцията в серия на Тейлър, членовете от трети и по-висок ред се отхвърлят.

където е матрицата на Хесиан.

Минимумът на дясната страна (ако съществува) се достига на същото място като минимума квадратна форма. Нека напишем формула за определяне на посоката на търсене:

Минимумът се достига при

Алгоритъм за оптимизация, при който посоката на търсене се определя от тази връзка, се нарича метод на Нютон, а посоката е посоката на Нютон.

В задачи за намиране на минимума на произволна квадратична функцияс положителна матрица от втори производни, методът на Нютон дава решение в една итерация, независимо от избора на начална точка.

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

Всъщност методът на Нютон се състои в еднократно прилагане на посоката на Нютон за оптимизиране на квадратичната функция. Ако функцията не е квадратна, тогава е вярна следната теорема.

Теорема 1.4. Ако матрицата на Хесиан на обща нелинейна функция f в минималната точка X* е положително определена, началната точка е избрана достатъчно близо до X* и дължините на стъпките са избрани правилно, тогава методът на Нютон се сближава към X* с квадратична скорост.

Методът на Нютон се счита за еталонен и всички разработени оптимизационни процедури се сравняват с него. Въпреки това, методът на Нютон е ефективен само за положително определена и добре обусловена матрица на Хес (нейният детерминант трябва да бъде по същество Над нулата, по-точно съотношението на най-големите и най-малките собствени стойности трябва да бъде близо до единица). За да преодолеем този недостатък, използваме модифицирани методиНютон, като използва нютоновите посоки доколкото е възможно и се отклонява от тях само когато е необходимо.

Общият принцип на модификациите на метода на Нютон е следният: при всяка итерация първо се конструира някаква положително определена матрица, „свързана“ с, след което се изчислява по формулата

Тъй като е положително определена, тогава - задължително ще бъде посоката на спускане. Процедурата по конструиране е организирана така, че да съвпада с матрицата на Хесиан, ако е положително определена. Тези процедури са изградени на базата на някои матрични разширения.

Друга група методи, които са почти толкова бързи, колкото метода на Нютон, се основават на апроксимацията на матрицата на Хесиан с помощта на крайни разлики, т.к. не е необходимо да се използват точните стойности на производните за оптимизация. Тези методи са полезни, когато аналитичното изчисляване на производните е трудно или просто невъзможно. Такива методи се наричат ​​дискретни методи на Нютон.

Ключът към ефективността на методите от Нютонов тип е вземането под внимание на информацията за кривината на функцията, която се минимизира, която се съдържа в матрицата на Хесиан и прави възможно изграждането на локално точни квадратични модели на целевата функция. Но е възможно да се събере и натрупа информация за кривината на функция въз основа на наблюдение на промяната в градиента по време на итерации на спускане.

Съответните методи, основани на възможността за апроксимиране на кривината на нелинейна функция без изрично формиране на нейната матрица на Хес, се наричат ​​квазинютонови методи.

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

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

Този метод се състои в многократно използване на посоката на Нютон при оптимизиране на функции, които не са квадратични.

Основен итерационна формуламноговариантна оптимизация

се използва в този метод, когато се избира посоката на оптимизация от релацията

Реалната дължина на стъпката е скрита в ненормализираната нютонова посока.

Тъй като този метод не изисква стойността на целевата функция в текущата точка, понякога се нарича индиректен или аналитичен методоптимизация. Способността му да определя минимума на квадратична функция с едно изчисление изглежда изключително привлекателна на пръв поглед. Това „единно изчисление“ обаче струва скъпо. На първо място е необходимо да се изчислят n частни производни от първи ред и n(n+1)/2 - от втори. Освен това матрицата на Хесиан трябва да бъде обърната. Това вече изисква около n3 изчислителни операции. При една и съща цена, методите с конюгирана посока или методите с конюгиран градиент могат да предприемат около n стъпки, т.е. постигат почти същия резултат. По този начин итерацията на метода на Нютон-Рафсън не дава предимства в случай на квадратична функция.

Ако функцията не е квадратна, тогава

• - началната посока вече, най-общо казано, не показва действителната минимална точка, което означава, че итерациите трябва да се повтарят многократно;
• - стъпка с единична дължина може да доведе до точка с най-лошата стойностцелева функция и търсенето може да даде грешна посока, ако например Хесианът не е положително определен;
• - Хесианът може да стане лошо обусловен, което прави невъзможно обръщането му, т.е. определяне на посоката за следващата итерация.

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

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

Пиърсън предложи няколко метода за приближаване на обратния Хесиан без изрично изчисляване на вторите производни, т.е. чрез наблюдение на промени в посоката на антиградиента. В този случай се получават спрегнати посоки. Тези алгоритми се различават само в детайли. Ето кои получиха най-много широко използванев приложни области.

Алгоритъм на Пиърсън #2.

В този алгоритъм обратният хесиан се апроксимира чрез матрицата Hk, изчислена на всяка стъпка по формулата

Като начална матрица H0 се избира произволна положително-определена симетрична матрица.

Този алгоритъм на Pearson често води до ситуации, при които матрицата Hk става лошо обусловена, а именно, тя започва да се колебае, колебаейки се между положително определена и неположително определена, докато детерминантата на матрицата е близо до нула. За да се избегне тази ситуация, е необходимо матрицата да се пренастройва на всеки n стъпки, приравнявайки я на H0.

Алгоритъм на Пиърсън #3.

В този алгоритъм матрицата Hk+1 се определя от формулата

Hk+1 = Hk +

Пътят на спускане, генериран от алгоритъма, е подобен на поведението на алгоритъма на Davidon-Fletcher-Powell, но стъпките са малко по-кратки. Пиърсън също предложи вариант на този алгоритъм с циклично пренареждане на матрицата.

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

Пиърсън предложи идеята за алгоритъм, в който матрицата се изчислява от релацията

H0=R0, където матрицата R0 е същата като първоначалните матрици в предишните алгоритми.

Когато k е кратно на броя на независимите променливи n, матрицата Hk се заменя с матрицата Rk+1, изчислена като сумата

Стойността Hk(f(Xk+1) - f(Xk)) е проекцията на вектора на нарастване на градиента (f(Xk+1)-f(Xk)), ортогонален на всички вектори на нарастване на градиента в предишните стъпки. След всеки n стъпки Rk е приближение на обратния Хесиан H-1(Xk), така че по същество се извършва (приблизително) търсене на Нютон.

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

Този метод има и други имена - методът на променливата метрика, методът на квази-Нютон, защото той използва и двата подхода.

Методът на Дейвидон-Флетчър-Пауъл (DFP) се основава на използването на нютонови посоки, но не изисква изчисляване на обратния Хесиан на всяка стъпка.

Посоката на търсене на стъпка k е посоката

където Hi е положително-определена симетрична матрица, която се актуализира на всяка стъпка и в границата става равна на обратния Хесиан. Идентификационната матрица обикновено се избира като начална матрица H. Итеративната DFT процедура може да бъде представена по следния начин:

• 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 в границата.

В случай на квадратична функция

тези. алгоритъмът на DFP използва спрегнати посоки.

По този начин методът DFT използва както идеите на Нютоновия подход, така и свойствата на спрегнатите посоки и при минимизиране на квадратичната функция се сближава за не повече от n итерации. Ако функцията, която се оптимизира, има форма, близка до квадратична функция, тогава методът DFP е ефективен поради добро приближение на G-1 (метод на Нютон). Ако целевата функция има обща форма, тогава DFP методът е ефективен поради използването на конюгирани посоки.

Нека разгледаме проблема за безусловното минимизиране на диференцируема функция на няколко променливи.Нека стойността на градиента в точка се доближава до минимум. При разглеждания по-долу градиентен метод посоката на слизане от точката се избира директно.Така според градиентния метод

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

1. Метод на най-стръмното спускане.

Помислете за функция на една скаларна променлива и изберете като стойност, за която равенството

Този метод, предложен през 1845 г. от О. Коши, сега се нарича метод на най-стръмното спускане.

На фиг. 10.5 показва геометрична илюстрация на този метод за минимизиране на функция от две променливи. От началната точка, перпендикулярно на линията на нивото в посоката, спускането продължава до достигане на минималната стойност на функцията по лъча. В намерената точка този лъч се допира до линията на нивото.След това се прави спускане от точката в посока, перпендикулярна на линията на нивото, докато съответният лъч докосне линията на нивото, минаваща през тази точка в точката и т.н.

Отбелязваме, че при всяка итерация изборът на стъпка предполага решението на едномерния проблем за минимизиране (10.23). Понякога тази операция може да се извърши аналитично, например за квадратична функция.

Прилагаме метода на най-стръмното спускане, за да минимизираме квадратичната функция

със симетрична положително определена матрица A.

Следователно съгласно формула (10.8) в този случай формула (10.22) изглежда така:

забележи това

Тази функция е квадратична функция на параметъра a и достига минимум при такава стойност, за която

Така, както се прилага към минимизирането на квадратното

функция (10.24), методът на най-стръмното спускане е еквивалентен на изчислението по формула (10.25), където

Забележка 1. Тъй като минималната точка на функцията (10.24) съвпада с решението на системата, методът на най-стръмното спускане (10.25), (10.26) също може да се използва като итеративен методрешения на линейни системи алгебрични уравнениясъс симетрични положително определени матрици.

Забележка 2. Забележете, че къде е отношението на Рейли (вижте § 8.1).

Пример 10.1. Прилагаме метода на най-стръмното спускане, за да минимизираме квадратичната функция

Имайте предвид, че следователно точната стойност на минималната точка ни е известна предварително. Нека запишем тази функциявъв формата (10.24), където матрицата и векторът Както е лесно да се види,

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

I итерация.

II итерация.

Може да се покаже, че за всички на итерацията ще бъдат получени стойностите

Имайте предвид, че с Така,

последователността, получена чрез метода на най-стръмното спускане, се сближава със скорост геометрична прогресия, чийто знаменател

На фиг. 10.5 показва точно траекторията на спускане, получена в този пример.

За случая на минимизиране на квадратична функция е вярно следното общ резултат.

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

Тук и Lado са минималните и максималните собствени стойности на матрицата A.

Имайте предвид, че този метод се сближава със скоростта на геометрична прогресия, чийто знаменател, освен това, ако са близки, тогава той е малък и методът се сближава доста бързо. Например, в Пример 10.1 имаме и, следователно, Ако Asch, тогава 1, и трябва да очакваме методът на най-стръмното спускане да се сближава бавно.

Пример 10.2. Прилагането на метода на най-стръмното спускане за минимизиране на квадратичната функция при първоначалното приближение дава последователност от приближения, където траекторията на спускане е показана на фиг. 10.6.

Последователността се събира тук със скоростта на геометрична прогресия, чийто знаменател е, т.е. много по-бавен,

отколкото в предишния пример. Тъй като тук полученият резултат е в пълно съответствие с оценката (10.27).

Забележка 1. Формулирахме теорема за сходимостта на метода на най-стръмното спускане в случай, когато целевата функция е квадратична. В общия случай, ако функцията, която се минимизира, е строго изпъкнала и има минимална точка x, тогава също, независимо от избора на първоначалното приближение, последователността, получена чрез този метод, се сближава към x при . В този случай, след попадане в достатъчно малка околност на минималната точка, конвергенцията става линейна и знаменателят на съответната геометрична прогресия се оценява отгоре чрез стойността и където както минимумът, така и максимумът собствени стойностиХесиански матрици

Забележка 2. За квадратичната целева функция (10.24) решението на задачата за едномерна минимизация (10.23) може да бъде намерено под формата на проста изрична формула (10.26). Въпреки това, за повечето други нелинейни функциитова не може да се направи и за изчисляване по метода на най-стръмното спускане трябва да се приложи числени методиедномерни минимизации от типа, разгледан в предишната глава.

2. Проблемът с "дерета".

От дискусията по-горе следва, че градиентният метод се сближава сравнително бързо, ако повърхностите на нивото за минимизираната функция са близки до сфери (когато линиите на нивото са близо до кръгове). За такива функции и 1. Теорема 10.1, Забележка 1 и резултатът от Пример 10.2 показват, че скоростта на сходимост намалява рязко със стойността на . В двумерния случай релефът на съответната повърхност прилича на терена с дере (фиг. 10.7). Следователно такива функции обикновено се наричат ​​дерета. По направленията, характеризиращи „дъното на дерето”, функцията на дерето се променя незначително, докато в другите посоки, характеризиращи „наклона на дерето”, настъпва рязка промяна на функцията.

Ако началната точка попада на "наклона на дерето", тогава посоката на градиентното спускане се оказва почти перпендикулярна на "дъното на дерето" и следващото приближение попада на противоположния "склон на дерето". Следващата стъпка към "дъното на дерето" връща подхода към първоначалния "наклон на дерето". В резултат на това, вместо да се движи по „дъното на дерето“ към минималната точка, траекторията на спускане прави зигзагообразни скокове през „дерето“, почти не приближавайки целта (фиг. 10.7).

За да се ускори конвергенцията на градиентния метод, като същевременно се минимизират функциите на дере, са разработени редица специални методи за "дере". Нека да дадем представа за един от най-простите методи. От две близки изходни точки се прави градиентно спускане до „дъното на дерето”. През намерените точки се изчертава права линия, по която се прави голяма стъпка "дере" (фиг. 10.8). От така намерената точка отново се прави едно стъпало на градиентно спускане до точката.След това се прави втората стъпка „дере“ по правата, минаваща през точките . В резултат на това движението по "дъното на дерето" до минималната точка се ускорява значително.

| Повече ▼ подробна информацияотносно проблема с методите "дерета" и "дера" може да се намери например в , .

3. Други подходи за определяне на стъпката на спускане.

Както е лесно да се разбере, при всяка итерация би било желателно да се избере посока на спускане, близка до посоката, по която движението води от точка до точка x. За съжаление, антиградиентът (като правило е неуспешна посока на спускане. Това е особено изразено за функциите на оврага. Следователно има съмнение относно целесъобразността на задълбочено търсене на решение на проблема с едномерната минимизация (10.23) и има желание да се направи само такава стъпка в посоката, която би осигурила "значително намаляване" на функцията. Освен това на практика понякога човек се задоволява с дефинирането на стойност, която просто осигурява намаляване на стойността на целта функция.

Можете също да търсите не най-добрата точка в посоката на градиента, а нещо по-добро от текущата.

Най-лесният за внедряване от всички локални методи за оптимизация. Той има доста слаби условия на конвергенция, но скоростта на конвергенция е доста малка (линейна). Методът на стъпковия градиент често се използва като част от други методи за оптимизация, като например метода на Флетчър-Рийвс.

Описание [ | ]

Подобрения[ | ]

Методът на градиентно спускане се оказва много бавен при движение по дере и с увеличаването на броя на променливите на целевата функция това поведение на метода става типично. За борба с това явление се използва, чиято същност е много проста. След като направи две стъпки на градиентно спускане и получи три точки, третата стъпка трябва да се направи в посока на вектора, свързващ първата и третата точка, по дъното на дерето.

За функции, близки до квадратичните, методът на спрегнатия градиент е ефективен.

Приложение в изкуствени невронни мрежи[ | ]

Методът на градиентно спускане с известна модификация се използва широко за обучение на персептрон и е известен в теорията на изкуствените невронни мрежи като метод на обратно разпространение. Когато тренирате невронна мрежа от тип персептрон, се изисква да промените тегловните коефициенти на мрежата по такъв начин, че да минимизирате средна грешкана изхода невронна мрежапри прилагане на последователност от входни данни за обучение към входа. Формално, за да се направи само една стъпка според метода на градиентно спускане (направете само една промяна в мрежовите параметри), е необходимо последователно да се подаде целия набор от тренировъчни данни към мрежовия вход, да се изчисли грешката за всяка тренировъчна информация обект и изчислете необходимата корекция на коефициентите на мрежата (но не правете тази корекция) и след като изпратите всички данни, изчислете сумата в корекцията на всеки коефициент на мрежата (сума от градиенти) и коригирайте коефициентите „с една стъпка“ . Очевидно при голям набор от данни за обучение алгоритъмът ще работи изключително бавно, следователно на практика коефициентите на мрежата често се коригират след всеки елемент за обучение, където стойността на градиента се апроксимира от градиента на функцията на разходите, изчислена само върху един тренировъчен елемент. Такъв метод се нарича стохастичен градиент на спускане или оперативно градиентно спускане . Стохастичното градиентно спускане е форма на стохастично приближение. Теорията на стохастичните апроксимации дава условия за конвергенцията на метода на стохастичното градиентно спускане.

Връзки [ | ]

• Дж. Матюс.Модул за най-стръмно спускане или метод на градиент. (недостъпна връзка)

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

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

И накрая, параметърът m може да бъде зададен постоянен при всички итерации. Въпреки това, когато големи стойности m процесът на търсене може да се разминава. в добър смисълизборът на m може да бъде неговата дефиниция при първата итерация от условието за екстремум в посоката на градиента. При следващите итерации m остава константа. Това още повече опростява изчисленията.

Например за функция с с градиентни проекции определя се по метода на най-стръмното спускане. Приемаме константата на параметъра при всички итерации.

Изчислете координатите x (1):

За да изчислим координатите на точката x (2), намираме проекцията на градиента в точката x (1) : , тогава

и т.н.

Тази последователност също се сближава.

метод на стъпков градиент

Този метод е разработен от инженери и се състои в това, че стъпката за една от променливите се приема постоянна, а за други променливи се избира въз основа на пропорционалността на градиентите на точките. С това, така да се каже, екстремната повърхност се мащабира, т.к конвергенцията не е еднаква за всички променливи. Следователно, като избират различни стъпки за координатите, те се опитват да направят скоростта на конвергенция приблизително еднаква за всички променливи.

Нека са дадени разделима функция и начална точка . Нека зададем постоянна стъпка по координатата x 1, нека Dx 1 =0,2. Стъпката по координатата x 2 се намира от съотношението на градиентите и стъпките.