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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Конюгатен градиентен метод на Fletcher-Reeves

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

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

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

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

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 се избира произволна положително определена симетрична матрица.

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

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

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

Hk+1 = Hk +

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

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

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

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

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

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

Метод на Davidon-Fletcher-Powell

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

Методът на Дейвидон-Флетчър-Пауъл (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 итерации. Ако оптимизираната функция има форма, близка до квадратична функция, тогава DFT методът е ефективен поради доброто си приближение G-1 (метод на Нютон). Ако целевата функция има общ вид, тогава методът на DFT е ефективен поради използването на спрегнати посоки.

Методи за градиентна оптимизация

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

Като цяло, стойността на критерия за оптимизация Рможе да се разглежда като функция Р(x b xx..., x n),дефинирани в n-мерно пространство. Тъй като няма визуално графично представяне на n-мерното пространство, ще използваме случая на двумерно пространство.

Ако Р(л б х 2)непрекъснато в региона Д,след това около оптималната точка M°(xi°, x g °)е възможно да се начертае затворена линия в дадена равнина, по която стойността Р= конст. Много такива линии, наречени линии с равни нива, могат да бъдат начертани около оптималната точка (в зависимост от стъпката

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

Концепцията за градиент се използва широко в инженерните изчисления при намиране на екстремуми на нелинейни функции. Градиентните методи са числени методи за търсене. Те са универсални и особено ефективни в случаите на търсене на екстремуми на нелинейни функции с ограничения, както и когато аналитичната функция е напълно неизвестна. Същността на тези методи е да се определят стойностите на променливите, които осигуряват екстремума на целевата функция чрез движение по градиента (при търсене макс.)или в обратна посока (мин.)Различните градиентни методи се различават един от друг по начина, по който определят движението към оптимума. Долната линия е, че ако линиите на равни нива R(xu x i)характеризирайте графично зависимостта R(x\jc?),тогава търсенето на оптималната точка може да се извърши по различни начини. Например, начертайте мрежа върху равнина x\, xrпосочване на стойностите Рвъв възлите на мрежата (фиг. 2.13).

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

Числени методи

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

Числените методи се използват за апроксимиране на функции, за решаване на диференциални уравнения и техните системи, за интегриране и диференциране и за изчисляване на числени изрази.

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

Избор на възлови точки, провеждане на експерименти при определени стойности (нива) на независими променливи (ако стъпката на промяна на фактор е избрана неправилно, ние или ще „пропуснем“ характерна черта на процеса, който се изучава, или ще удължим процедурата и увеличаване на сложността на търсенето на модел);

Изборът на апроксимиращи функции под формата на полиноми, емпирични формули, в зависимост от съдържанието на конкретен проблем (трябва да се стремим да опростим апроксимиращите функции колкото е възможно повече);

Избор и използване на критерии за съгласуване, въз основа на които се намират параметрите на апроксимиращи функции;

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

В задачи за апроксимиране на функции чрез полиноми се използват три класа

Линейна комбинация от степенни функции (редове на Тейлър, полиноми на Лагранж, Нютон и др.);

Комбинация от функции soz ph, w тях(серии на Фурие);

Полином, образуван от функции експ(-a, d).

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

При оптимизиране по градиентния метод оптимумът на изследвания обект се търси в посока на най-бързото нарастване (намаляване) на изходната променлива, т.е. по посока на градиента. Но преди да направите крачка към градиента, трябва да го изчислите. Градиентът може да се изчисли или с помощта на съществуващ модел

моделиране на динамичен градиентен полином

където е частната производна по отношение на i-тия фактор;

i, j, k - единични вектори по посока на координатните оси на факторното пространство, или според резултатите от n пробни движения по посока на координатните оси.

Ако математическият модел на статистически процес има формата на линеен полином, чиито регресионни коефициенти b i са частни производни на разширението на функцията y = f(X) в ред на Тейлър по степени на x i , тогава оптимумът е търсено по посока на градиента с определена стъпка h i:

pkfv n(H)= и 1 r 1 +и 2 r 2 +…+и t r t

Посоката се коригира след всяка стъпка.

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

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

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

при две допълнителни условия:

Този принцип (без модификация) може да се приложи към произволен брой променливи, както и към допълнителни условия. Да разгледаме равнината x 1 , x 2 (фиг. 1). Съгласно формула (8), всяка точка съответства на определена стойност на F. На фиг. 1 линиите F = const, принадлежащи на тази равнина, са представени чрез затворени криви, обграждащи точката M *, в която F е минимална. Нека в началния момент стойностите x 1 и x 2 съответстват на точката M 0 . Изчислителният цикъл започва с поредица от пробни стъпки. Първо, на стойността на x 1 се дава малка стъпка; в този момент стойността на x 2 е непроменена. След това се определя полученото увеличение в стойността на F, което може да се счита за пропорционално на стойността на частичната производна

(ако стойността винаги е една и съща).

Дефиницията на частни производни (10) и (11) означава, че е намерен вектор с координати и , който се нарича градиент на стойността F и се означава по следния начин:

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

След намиране на компонентите на градиента, пробните движения се спират и работните стъпки се извършват в посока, обратна на посоката на градиента, и колкото по-голяма е абсолютната стойност на вектора grad F, толкова по-голям е размерът на стъпката. Тези условия са изпълнени, ако стойностите на работните стъпки са пропорционални на предварително получените стойности на частичните производни:

където b е положителна константа.

След всяка работна стъпка се оценява нарастването на стойността на F. Ако се окаже отрицателно, тогава движението се извършва в правилната посока и трябва да се движите по-нататък в същата посока M 0 M 1. Ако в точка M 1 резултатът от измерването покаже това, тогава работните движения спират и започва нова серия от пробни движения. В този случай градиентът gradF се определя в новата точка M 1, след което работното движение продължава по новооткритата посока на най-стръмно спускане, т.е. по линията M 1 M 2 и т.н. Този метод се нарича метод за най-стръмно спускане/най-стръмно изкачване.

Когато системата е близо до минимума, което се обозначава с малка стойност на

има преминаване към по-„предпазлив“ метод на търсене, така нареченият градиентен метод. Той се различава от метода на най-стръмното спускане по това, че след определяне на градиента gradF се прави само една работна стъпка и след това серия от пробни движения започва отново в нова точка. Този метод на търсене осигурява по-точно определяне на минимума в сравнение с метода на най-стръмното спускане, докато последният ви позволява бързо да се приближите до минимума. Ако по време на процеса на търсене точка М достигне границата на допустимата област и поне една от величините М 1, М 2 промени знака, методът се променя и точка М започва да се движи по границата на областта.

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

Недостатъците на метода на стръмно изкачване включват:

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

2. Трудност при намирането на глобален оптимум. Методът е приложим за намиране само на локални оптимуми.

Градиентният вектор е насочен в посоката на най-бързото нарастване на функцията в дадена точка. Векторът, противоположен на градиента -grad(/(x)) се нарича антиградиент и е насочен в посоката на най-бързото намаляване на функцията. В минималната точка градиентът на функцията е нула. Методите от първи ред, наричани още градиентни методи, се основават на свойствата на градиентите. Ако няма допълнителна информация, тогава от началната точка x (0 > е по-добре да отидете до точка x (1), лежаща в посока на антиградиента - най-бързото намаляване на функцията. Избор на антиградиента -grad(/( x (^)) в точката като посока на спускане x(kполучаваме итеративен процес на формата

В координатна форма този процес се записва по следния начин:

Като критерий за спиране на итеративния процес можете да използвате или условие (10.2), или изпълнение на условието за малък градиент

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

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

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

Градиентните методи с променливи стъпки са по-надеждни и икономични (от гледна точка на броя итерации), когато размерът на стъпката се променя по някакъв начин в зависимост от полученото приближение. Като пример за такъв метод, разгледайте метода на най-стръмното спускане. При този метод при всяка итерация размерът на стъпката i* се избира от условието за минимум на функцията f(x) в посока на спускане, т.е.

Това условие означава, че движението по антиградиента се извършва, докато стойността на функцията /(x) намалява. Следователно при всяка итерация е необходимо да се реши задачата за едномерна минимизация по отношение на φ на функцията φ(τ) =/(x(/r) - - agrad^x^))). Алгоритъмът на метода за най-стръмно спускане е както следва.

• 1. Нека зададем координатите на началната точка x^° и точността на приближеното решение r. Нека зададем к = 0.
• 2. В точка x (/r) изчисляваме стойността на градиента grad(/(x (^)).
• 3. Определете размера на стъпката a^чрез едномерна минимизация на функцията cp(i) по отношение на i.
• 4. Нека определим ново приближение до минималната точка x (* +1 > използвайки формула (10.4).
• 5. Да проверим условията за спиране на итеративния процес. Ако те са изпълнени, изчисленията спират. Иначе предполагаме k k+ 1 и отидете на стъпка 2.

При метода на най-стръмното спускане посоката на движение от точка x (*) докосва линията на нивото в точка x (* +1). Трасето на спускане е зигзагообразно, а съседните зигзагообразни връзки са ортогонални една спрямо друга. Наистина, стъпка a^се избира чрез минимизиране от Афункции ( А). Предпоставка

минимум на функцията - = 0. След като сме изчислили производната

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

Проблемът за минимизиране на функцията φ(π) може да се сведе до проблема за изчисляване на корена на функция на една променлива g(a) =

Градиентните методи се сближават до минимум при скорост на геометрична прогресия за гладки изпъкнали функции. Такива функции имат най-големите и най-малките собствени стойности на матрицата на вторите производни (матрица на Хесен)

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

Няма ограничения при неограничен оптимизационен проблем.

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

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

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

Където  к  стъпков параметър кта итерация по антиградиента. За възходящи методи (търсене на максимума) трябва да се движите по градиента.

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

Метод с постоянен стъпков параметър.При този метод параметърът на стъпката е постоянен във всяка итерация. Възниква въпросът: как практически да изберем стойността на параметъра на стъпката? Достатъчно малък параметър на стъпка може да доведе до неприемливо голям брой итерации, необходими за достигане на минималната точка. От друга страна, твърде голям параметър на стъпка може да доведе до превишаване на минималната точка и до колебателен изчислителен процес около тази точка. Тези обстоятелства са недостатъци на метода. Тъй като е невъзможно да се познае предварително приемливата стойност на параметъра на стъпката  к, тогава има нужда да се използва градиентният метод с променлив параметър на стъпка.

Когато се доближим до оптимума, векторът на градиента намалява като стойност, клонейки към нула, така че когато  к = const дължината на стъпката постепенно намалява. Близо до оптимума дължината на градиентния вектор клони към нула. Дължина на вектора или норма в н-мерното евклидово пространство се определя по формулата

, Където н- брой променливи.

Опции за спиране на оптималния процес на търсене:

От практическа гледна точка е по-удобно да се използва 3-ти критерий за спиране (тъй като стойностите на проектните параметри са от интерес), но за да определите близостта на екстремалната точка, трябва да се съсредоточите върху 2-ри критерий. Могат да се използват няколко критерия за спиране на изчислителния процес.

Нека разгледаме един пример. Намерете минимума на целевата функция Е(х) = (х 1  2) 2 + (х 2  4) 2 . Точно решение на проблема X*= (2,0;4,0).Изрази за частни производни

,
.

Избор на стъпка  к = 0,1. Да търсим от началната точка х 1 = . Нека представим решението под формата на таблица.

Градиентен метод с разделяне на параметъра на стъпката.В този случай, по време на процеса на оптимизация, параметърът на стъпката  k намалява, ако след следващата стъпка целевата функция се увеличи (при търсене на минимум). В този случай дължината на стъпката често се разделя (разделя) наполовина и стъпката се повтаря от предишната точка. Това осигурява по-точен подход към екстремалната точка.

Метод на най-стръмното спускане.Методите с променлива стъпка са по-икономични по отношение на броя на итерациите. Ако оптималната дължина на стъпката  k по антиградиентната посока е решение на едномерен проблем за минимизиране, тогава този метод се нарича метод на най-стръмното спускане. При този метод при всяка итерация се решава проблемът с едномерното минимизиране:

F(X k+1 )=F(X к   к С к )=min F( к ), С к =  F(X);

 к >0

.

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

Пример. мин Е(х 1 , х 2 ) = 2х 1 2 + 4х 2 3 – 3. Тогава  Е(х)= [ 4х 1 ; 12х 2 2 ]. Нека точката х к = , следователно  Е(х)= [ 8; 12], Е(х к   С к ) =

2(2  8 ) 2 + 4(1  12 ) 3  3. Необходимо е да се намери , което осигурява минимума за тази функция.

Алгоритъм за най-стръмния метод на спускане (за намиране на минимума)

Начална стъпка. Нека   е спираща константа. Изберете начална точка х 1 , слагам к = 1 и отидете на основната стъпка.

Основна стъпка. Ако || градФ(х)||< , след това прекратете търсенето, в противен случай определете  Е(х к ) и намери  к  оптимално решение на задачата за минимизиране Е(х к   к С к ) при  к  0. Слагам х к +1 = х к   к С к, възлагам к =

к + 1 и повторете основната стъпка.

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

Метод на дихотомия (разполовяване)Начална стъпка.Изберете константата на различимост  и крайната дължина на интервала на неопределеност л. Стойността  трябва да бъде възможно най-малка, но все пак да позволява да се прави разлика между стойностите на функцията Е( ) И Е( ) . Позволявам [ а 1 , b 1 ] - начален интервал на неопределеност. Слагам к =

Основният етап се състои от краен брой итерации от един и същи тип.

k-та итерация.

Етап 1.Ако b к  а к  л, тогава изчисленията приключват. Решение х * = (а к + b к )/2. В противен случай

,
.

Стъпка 2.Ако Е( к ) < Е( к ), слагам а к +1 = а к ; b к +1 =  к. В противен случай а к +1 =  кИ b к +1 = b к. Присвояване к = к + 1 и отидете на стъпка 1.

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

 = 0,618034 от края на интервала.

Алгоритъм на метода на златното сечение

Начална стъпка.Изберете допустимата крайна дължина на интервала на неопределеност л > 0. Позволявам [ а 1 , b 1 ] - начален интервал на неопределеност. Слагам  1 = а 1 +(1   )(b 1  а 1 ) И  1 = а 1 +  (b 1  а 1 ) , Където  = 0,618 . Изчисли Е( 1 ) И Е( 1 ) , слагам к = 1 и отидете на основната сцена.

Етап 1.Ако b к  а к  л, тогава изчисленията приключват х * = (а к + b к )/ 2. В противен случай ако Е( к ) > Е( к ) , след това преминете към стъпка 2; Ако Е( к )  Е( к ) , отидете на стъпка 3.

Стъпка 2.Слагам а к +1 =  к , b к +1 = b к ,  к +1 =  к ,  к +1 = а к +1 +  (b к +1 – а к +1 ). Изчисли Е( к +1 ), отидете на стъпка 4.

Стъпка 3.Слагам а к +1 = а к , b к +1 =  к ,  к +1 =  к ,  к +1 = а к +1 + (1   )(b к +1 – а к +1 ). Изчисли Е( к +1 ).

Стъпка 4.Присвояване к = к + 1, отидете на стъпка 1.

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

Метод на конюгирания градиент (Fletcher-Reeves).При този метод, избирайки посоката на движение на к+ Стъпка 1 взема предвид промяната в посоката на кстъпка. Векторът на посоката на спускане е линейна комбинация от антиградиентната посока и предишната посока на търсене. В този случай, когато се минимизират функциите на дере (с тесни дълги вдлъбнатини), търсенето не е перпендикулярно на дерето, а покрай него, което позволява бързо достигане на минимума. Координатите на точка при търсене на екстремум с помощта на метода на спрегнат градиент се изчисляват с помощта на израза х к +1 = х к   V к +1 , Където V к +1 – вектор, изчислен чрез следния израз:

.

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

Алгоритъм на метода на спрегнатия градиент

Етап 1.Въведете начална точка х 0 , точност  , измерение н.

Стъпка 2.Слагам к = 1.

Стъпка 3.Поставете вектор V к = 0.

Стъпка 4.Изчисли град Е(х к ).

Стъпка 5.Изчислете вектор V к +1.

Стъпка 6.Извършете едномерно векторно търсене V к +1.

Стъпка 7Ако к < н, слагам к = к + 1 и отидете на стъпка 4, в противен случай отидете на стъпка 8.

Стъпка 8Ако дължината на вектора Vпо-малко от , прекратете търсенето, в противен случай  преминете към стъпка 2.

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

Недостатъци на градиентните методи

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

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