Най-простият градиентен метод. Градиентни неограничени методи за оптимизация

Методът се основава на следната итеративна модификация на формулата

x k +1 = x k + a k s(x k),

x k+1 = x k - a k Ñ f(x k), където

a - даден положителен коефициент;

Ñ ​​​​f(x k) - градиент целева функцияпърва поръчка.

недостатъци:

необходимостта да се избере подходяща стойност на ;

бавна конвергенция към минималната точка поради малката стойност на f(x k) в близост до тази точка.

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

Без първия недостатък на най-простия градиентен метод, тъй като a k се изчислява чрез решаване на задачата за минимизиране Ñ f(x k) по посоката Ñ f(x k), като се използва един от методите за едномерна оптимизация x k+1 = x k - a k Ñ f(x k).

Този метод понякога се нарича метод на Коши.

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

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

Общият проблем на нелинейното програмиране без ограничения е следният: минимизиране на f(x), x E n, където f(x) е целевата функция. Когато решаваме този проблем, използваме методи за минимизиране, които водят до стационарна точка f(x), дефинирана от уравнението f(x *)=0. Методът на спрегнатата посока се отнася до неограничени методи за минимизиране, които използват производни. Задача: минимизирайте f(x), x E n , където f(x) е целевата функция на n независими променливи. Важна характеристикае бърза конвергенция поради факта, че при избора на посоката се използва матрицата на Хесиан, която описва областта на топологията на повърхността на реакция. По-специално, ако целевата функция е квадратична, тогава минималната точка може да бъде получена за не повече от брой стъпки, равни на размерността на проблема.

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

Метод на Нютон

Последователното прилагане на схемата за квадратична апроксимация води до прилагането на метода на оптимизация на Нютон по формулата

x k +1 = x k - Ñ 2 f(x k -1) Ñ f(x k).

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

x k +1 = x k - a k Ñ 2 f(x k -1) Ñ f(x k), където

a k е параметър, избран така, че f(x k+1) min.

2. Намиране на екстремума на функция без ограничение

Някаква функция f(x) е дадена на отворен интервал (a, c) на промяната в аргумента x. Предполагаме, че exst съществува в рамките на този интервал (трябва да се каже, че в общия случай това не може да бъде математически заявено предварително; обаче, в техническите приложения, присъствието на exst много често в рамките на определен интервал на изменение на вариацията на аргумента интервал може да се предвиди от физически съображения).

Дефиниция на екст. Функцията f (x), дадена на интервала (a, c), има в точката x * max (min), ако тази точка може да бъде заобиколена от такъв интервал (x * -ε, x * + ε), съдържащ се в интервал (a, c), че за всички негови точки x, принадлежащи на интервала (x * -ε, x * +ε), е валидно следното неравенство:

f(x) ≤ f(x *) → за макс

f(x) ≥ f(x *) → за min

Тази дефиниция не налага никакви ограничения върху класа функции f(x), което, разбира се, е много ценно.

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

Теорема на Ферма. Нека функцията f(x) е дефинирана в някакъв интервал (a, b) и в точката "c" от този интервал приема най-голямата (най-малката) стойност. Ако в тази точка има двустранна крайна производна, тогава съществуването на exst е необходимо.

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

* В случай, че има min, а когато →max. И накрая, ако при x=x 0, тогава използването на 2-ра производна не помага и трябва да използвате например дефиницията на exst.

При решаването на задача I много често се използват необходимите условия exst (т.е. теоремата на Ферма).

Ако уравнението exst има реални корени, тогава точките, съответстващи на тези корени, са подозрителни за exst (но не непременно самите екстремуми, защото имаме работа с необходими, а не с необходими и достатъчни условия). Така, например, в точката на инфлексия X p се извършва, но, както знаете, това не е екстремум.

Нека също да отбележим, че:

от необходими условияневъзможно е да се каже какъв тип екстремум е открит max или min: необходими са допълнителни изследвания, за да се определи това;

от необходимите условия е невъзможно да се определи дали това е глобален екстремум или локален.

Следователно, когато се открият подозрителни точки за exst, те се изследват допълнително, например въз основа на определението за exst или 2-ра производна.

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

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

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

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

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

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

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

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

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

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

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

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

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

Ще споделя малко от моя опит :)

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

Идеята на този метод е, че търсенето се извършва в посока на спускане на координати по време на новата итерация. Спускането се извършва постепенно по всяка координата. Броят на координатите директно зависи от броя на променливите.
За да демонстрирате как работи този метод, първо трябва да вземете функцията z = f(x1, x2,…, xn) и да изберете всяка точка M0(x10, x20,…, xn0) в n пространство, което зависи от броя на характеристики на функцията. Следващия стъпка по стъпкафиксиране на всички точки на функцията в константа, с изключение на първата. Това се прави с цел търсене многовариантна оптимизациянамаляване на проблема с едномерната оптимизация, тоест търсенето на аргумента x1, до решението на търсенето в определен сегмент.
За да намерите стойността на тази променлива, е необходимо да се спуснете по тази координата до нова точка M1(x11, x21,…, xn1). Освен това функцията се диференцира и тогава можем да намерим стойността на новата следваща точка, използвайки този израз:

След като намерите стойността на променливата, трябва да повторите итерацията, като фиксирате всички аргументи с изключение на x2 и да започнете низходящ нова координатадо следващата нова точка M2(x11,x21,x30…,xn0). Сега стойността на новата точка ще се появи според израза:

И отново, итерацията с фиксиране ще се повтаря, докато всички аргументи от xi до xn свършат. При последната итерация ще преминем последователно през всички възможни координати, в които вече намери локални минимуми, така че целевата функция при последната координата ще достигне глобалния минимум. Едно от предимствата на този метод е, че по всяко време е възможно да се прекъсне спускането и последната намерена точка ще бъде минималната точка. Това е полезно, когато методът преминава в безкраен цикъл и последната намерена координата може да се счита за резултат от това търсене. Въпреки това целевата настройка на търсенето на глобалния минимум в района може да не бъде достигната поради факта, че прекъснахме търсенето на минимума (вижте Фигура 1).

Фигура 1 - Отмяна на координатно спускане

Изследването на този метод показа, че всяка намерена изчислена точка в пространството е глобална минимална точка дадена функция, а функцията z = f(x1, x2,…, xn) е изпъкнала и диференцируема.
От това можем да заключим, че функцията z = f(x1, x2,…, xn) е изпъкнала и диференцируема в пространството и всяка намерена гранична точка в последователността M0(x10, x20,…, xn0) ще бъде глобален минимум точка (виж Фиг. Фигура 2) на тази функция чрез метода на координатно спускане.

Фигура 2 - Локални минимални точки на координатната ос

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

Прогресът на метода на координатно спускане се извършва съгласно алгоритъма, описан в блоковата диаграма (виж Фигура 3). Итерации на изпълнението на този метод:
Първоначално трябва да се въведат няколко параметъра: Epsilon точността, която трябва да е строго положителна, началната точка x1, от която ще започнем да изпълняваме нашия алгоритъм и ще зададем Lambda j;
Следващата стъпка е да се вземе първата начална точка x1, след което се решава обикновеното едномерно уравнение с една променлива и формулата за намиране на минимума ще бъде, където k = 1, j=1:

Сега, след като изчислите точката на екстремума, трябва да проверите броя на аргументите във функцията и ако j е по-малко от n, тогава трябва да повторите предишната стъпка и да предефинирате аргумента j = j + 1. Във всички останали случаи, преминете към следващата стъпка.
Сега е необходимо да предефинирате променливата x съгласно формулата x (k + 1) = y (n + 1) и да се опитате да извършите конвергенцията на функцията с дадена точност съгласно израза:

Сега намирането на екстремната точка зависи от този израз. Ако този израз е верен, тогава изчислението на екстремната точка се намалява до x*= xk + 1. Но често е необходимо да се извършват допълнителни итерации в зависимост от точността, така че стойностите на аргументите ще бъдат предефинирани y(1 ) = x(k + 1), а стойностите на индексите j =1, k = k + 1.

Фигура 3 - Блокова схема на метода на спускане по координати

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

Метод на Nelder-Mead

Заслужава да се отбележи популярността на този алгоритъм сред изследователите на многомерни методи за оптимизация. Методът на Nelder-Mead е един от малкото методи, базирани на концепцията за последователна трансформация на деформируем симплекс около точка на екстремум и не използва алгоритъма за движение към глобалния минимум.
Този симплекс е правилен и е представен като полиедър с равноотдалечени върхове на симплекса в N-мерно пространство. В различни пространства симплексът се преобразува в R2-равностранен триъгълник, а в R3 - правилен тетраедър.
Както бе споменато по-горе, алгоритъмът е развитие на простия метод на Spendley, Hoekst и Himsworth, но за разлика от последния позволява използването на неправилни прости методи. Най-често симплекс означава изпъкнал многостенс брой върхове N+1, където N е броят на параметрите на модела в n-мерното пространство.
За да започнете да използвате този метод, трябва да определите основния връх на всички налични координатни набори, като използвате израза:

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

Където xc е центърът на тежестта (вижте Фигура 1).

Фигура 1 - Отражение през центъра на тежестта

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

Алгоритъмът на Nelder-Mead също използва тези симплексни функции съгласно следните формули:

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

Това отражение се извършва стриктно към екстремалната точка и само през центъра на тежестта (виж Фигура 2).

Фигура 2 - Отражението на симплекса става през центъра на тежестта

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

За да се извърши компресия, е необходимо да се определи точката с най-малка стойност (виж Фигура 3).

Фигура 3 - Симплексът е компресиран до най-малкия аргумент.

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

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

Фигура 4 - Отражение с компресия

Функцията за отражение на симплексното разтягане (вижте Фигура 5) се осъществява с помощта на две функции - отражение през центъра на тежестта и разтягане през най-голямата стойност.

Фигура 5 - Отражение с разтягане.

За да се демонстрира работата на метода на Nelder-Mead, е необходимо да се направи справка с блоковата диаграма на алгоритъма (виж Фигура 6).
На първо място, както в предишните примери, е необходимо да зададете параметъра на изкривяване ε, който трябва да бъде строго Над нулата, както и задаване на необходимите параметри за изчисляване на α, β и a. Това ще е необходимо за изчисляване на функцията f(x0), както и за конструиране на самия симплекс.

Фигура 6 - Първата част от метода на Nelder - Mead.

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

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

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

Ако това условие е изпълнено, тогава точката x(0) ще бъде минималната точка, в противен случай трябва да преминете към следващата стъпка, в която трябва да търсите най-малкия аргумент на функцията:

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

Фигура 7 - Втората част от метода на Nelder - Mead.

Стойността, изчислена от предишната функция, трябва да бъде заменена в условието fmin< f(xN). При истинном выполнении данного условия, точка x(N) будет являться минимальной из группы тех, которые хранятся в отсортированном списке и нужно вернуться к шагу, где мы рассчитывали центр тяжести, в противном случае, производим сжатие симплекса в 2 раза и возвращаемся к самому началу с новым набором точек.
Проучванията на този алгоритъм показват, че методите с неправилни прости (вижте фигура 8) все още са доста слабо проучени, но това не им пречи да се справят перфектно със задачите си.
По-задълбочените тестове показват, че експериментално е възможно да изберете параметрите на функциите за разтягане, компресия и отражение, които са най-подходящи за проблема, но можете да използвате общоприетите параметри на тези функции α = 1/2, β = 2, γ = 2 или α = 1/4, β = 5/2, γ = 2. Следователно, преди да отхвърлите този метод за решаване на проблема, трябва да разберете, че за всяко ново търсене на безусловен екстремум трябва внимателно да наблюдавате поведение на симплекса по време на неговата работа и бележка нестандартни решенияметод.

Фигура 8 - Процесът на намиране на минимума.

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

P.S. Текстът е изцяло мой. Надявам се някой тази информацияще бъде полезно.

Както вече отбелязахме, проблемът за оптимизация е проблемът за намиране на такива стойности на факторите х 1 = х 1* , х 2 = х 2* , …, хк = хк * , за която функцията за отговор ( при) достига екстремна стойност при= ext (оптимум).

известен различни методирешение на задачата за оптимизация. Един от най-широко използваните е градиентният метод, наричан още метод на Бокс-Уилсън и метод на стръмно изкачване.

Разгледайте същността на градиентния метод, като използвате примера на двуфакторна функция за отговор y=е(х 1 , Х 2 ). На фиг. 4.3 са показани криви на факторното пространство равни стойностифункции на отговор (криви на ниво). Точка с координати х 1 *, х 2 * съответства на екстремната стойност на функцията за отговор привътр.

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

Градиент на непрекъсната еднозначна функция y=f(х 1 , Х 2) е вектор, определен от посоката на градиента с координати:

където аз,йса единични вектори по посока на координатните оси х 1 и х 2. Частични производни и характеризират посоката на вектора.

Тъй като не знаем вида на зависимостта y=f(х 1 , Х 2), не можем да намерим частните производни и да определим истинската посока на градиента.

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

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

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

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

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

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

Тъй като х 1 0 = 0 и х 2 0 = 0, тогава .

Като дефинирате посоката на градиента () и изберете размера на стъпката м, ние извършваме опит на начално ниво х 1 0 , х 2 0 .

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

Продължаваме да се движим по градиента, докато функцията на отговор започне да намалява. На фиг. 4.3 движението по градиента съответства на права линия, излизаща от точката ( х 1 0 , хдвадесет). Той постепенно се отклонява от истинската посока на градиента, показана с пунктираната линия, поради нелинейността на функцията на отговор.

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

Изграждане на нов линеен модел , извършвам регресионен анализ. Ако в същото време тестът за значимостта на факторите покаже, че поне един коеф

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

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

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

1) начални нива на фактори ( хй 0) трябва да бъде избран възможно най-близо до оптималната точка, ако има някаква априорна информация за нейното положение;

2) интервали на вариация (Δ хй) трябва да бъдат избрани така, че линейният модел да е подходящ. Долна граница Δ хйв този случай е минималната стойност на интервала на изменение, при който функцията на отговор остава значима;

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

.

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

Метод на Гаус-Зайдел

Методът се състои в последователно намиране на частични екстремуми на целевата функция за всеки фактор. В същото време на всеки етап (k-1) факторите се стабилизират и само един i-ти фактор варира

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

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

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

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

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

Методът на градиента (нормален) се извършва съгласно следната схема:

а) изберете базова точка;

б) изберете стъпки на движение за всеки фактор;

в) определяне на координатите на тестовите точки;

г) провеждане на експерименти в тестови точки. В резултат на това във всяка точка се получават стойностите на параметъра за оптимизация (Y).

д) въз основа на резултатите от експериментите се изчисляват оценки на компонентите на градиентния вектор в точка М за всеки i-ти фактор:

където H i е стъпката на движение по X i.

X i – координати на предишната работна точка.

g) координатите на тази работна точка се приемат като нова базова точка, около която се провеждат експерименти в тестови точки. Градиентът се изчислява и така нататък, докато се достигне желания параметър за оптимизация (Y). След всяка стъпка се прави корекция на посоката на движение.

Предимства на метода: простота, по-висока скорост на движение до оптималната.

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

а) Метод на стръмно изкачване (Box-Wilson).

б) Вземане на решение след стръмно изкачване.

в) Симплексен методоптимизация.

г) Предимства и недостатъци на методите.

5.7.3 Метод на стръмно изкачване (Box-Wilson)

Този метод е синтез най-добри характеристикиградиентни методи, методът на Гаус-Зайдел и методите PFE и DFE - като средство за получаване на математически модел на процеса. Решаването на задачата за оптимизация по този метод се извършва така, че стъпковото движение да се извършва в посока на най-бързото увеличение (намаляване) на параметъра за оптимизация. Корекцията на посоката на движение (за разлика от градиентните методи) се извършва не след всяка стъпка, а при достигане на конкретен екстремум на целевата функция. Освен това, в точките на частичен екстремум, се поставя нов факторен експеримент, нов математически модели отново стръмното изкачване се повтаря до достигане на глобалния оптимум. Движението по градиента започва от нулевата точка (центъра на плана).

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

Където i,j,k са единични вектори по посока на съответните координатни оси.

Процедура за изчисление.

Първоначалните данни са математически модел на процеса, получен по произволен метод (PFE, DFE и др.).

Изчисленията се извършват в следния ред:

а) по-добре е регресионното уравнение да се преведе в естествена форма, като се използват формулите за кодиране на променливи:

където х i -кодирана стойност на променлива x i ;

X i - естествена стойност на променливата x i ;

X i C - централното ниво на фактора в неговата естествена форма;

l i - интервалът на изменение на фактора x i в естествена форма.

б) изчислете стъпките на движение до оптималното за всеки фактор.

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

B i *.l I ,

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

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

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

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

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

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

Ако Y® макс X i \u003d X i c + gl i ` ’

ако Y® мин. X i \u003d X i c -gl i `.(5.36)