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

Метод на релаксация

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

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

Нека е аксиалната посока, т.е. .

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

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

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

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

Алгоритъмът за спускане за избраната аксиална посока може да бъде написан като

(3.8)

където е стойността на променливата на всяка стъпка от спускането;

Стойността на k + 1 стъпка, която може да варира в зависимост от номера на стъпката:

е знаковата функция на z;

Векторът на точката, в която последен пътизчислени са производни;

Знакът „+“ в алгоритъма (3.8) се взема при търсене на max I, а знакът „-“ се взема при търсене на min I. по-малко стъпкач., теми повече количествоизчисления по пътя към оптимума. Но ако стойността на h е твърде голяма, близо до оптималната, може да възникне зацикляне на процеса на търсене. Близо до оптимума е необходимо условието h

Най-простият алгоритъм за промяна на стъпката h е следният. В началото на спускането се задава стъпка, равна например на 10% от диапазона d; промени с тази стъпка, спускането се извършва в избраната посока до изпълнение на условието за следващите две изчисления

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

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

(3.9)

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

След това се намира нова аксиална посока, началната стъпка за по-нататъшно спускане, обикновено по-малка от тази, измината по предишната аксиална посока. Характерът на движението в оптимума при този метод е показан на фигура 3.4.

Фигура 3.5 - Траекторията на движение до оптимума при метода на релаксация

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

Стъпка 1. - аксиална посока,

; , ако ;

Стъпка 2 - нова аксиална посока;

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

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

Фигура 3.6 - Градиент на функцията

.

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

Проекцията на градиента върху равнината на променливите е перпендикулярна на допирателната към линията на нивото, т.е. градиентът е ортогонален на линиите с постоянно ниво целева функция(фиг. 3.6).

Фигура 3.7 - Траекторията на движение към оптимума в метода

градиент

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

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

Ако аналитичният израз е неизвестен, тогава посоката на градиента се определя чрез търсене на пробни движения на обекта. Нека началната точка. Дадено е увеличение, докато . Дефинирайте нарастване и производна

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

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

, (3.10)

или във векторна форма

, (3.11)

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

“+” – при търсене на max I;

“-” – при търсене на min I.

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

; (3.12)

(3.13)

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

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

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

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

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

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

Критерии за прекратяване на търсенето на оптимума:

; (3.16)

; (3.17)

където е нормата на вектора.

Търсенето приключва, когато е изпълнено едно от условията (3.14) - (3.17).

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

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

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

Ориз. 4.11.

Ориз. 4.12.

(двуизмерен случай)

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

се движат само наляво или надясно (виж фиг. 4.9), то в многомерния случай броят на възможните посоки на движение е безкрайно голям. На фиг. 4.11, илюстриращ случая на две променливи, стрелки, излизащи от началната точка И,показани са различни възможни посоки. В същото време движението по някои от тях дава увеличение на стойността на целевата функция по отношение на точката И(например указания 1-3), и в други посоки води до намаляването му (посоки 5-8). Като се има предвид, че позицията на оптималната точка е неизвестна, посоката, в която целевата функция нараства най-бързо, се счита за най-добра. Тази посока се нарича градиентфункции. Обърнете внимание, че във всяка точка от координатната равнина посоката на градиента е перпендикулярна на допирателната към линията на нивото, прекарана през същата точка.

В математическия анализ се доказва, че компонентите на градиентния вектор на функцията при =/(*, х 2, ..., x n)са неговите частни производни по отношение на аргументите, т.е.

&ad/(x 1,x 2 ,.= (du / dhu, dy / dx 2, ..., dy / dx p). (4.20)

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

Y" с координати:

1§газ1/(x (0)),

или във векторна форма

където Х-постоянен или променлив параметър, който определя дължината на работната стъпка, ?i>0. При втората итерация изчислете отново

градиентният вектор вече е за нова точка Y, след което аналогично

формула отидете до точката x^ > и т.н. (фиг. 4.12). За произволни да се-та итерация, която имаме

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

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

дължината на работната стъпка е разстоянието между съседни точки x^

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

Пример.Изисква се да се намери максимумът на функцията

y \u003d 110-2 (lg, -4) 2 -3 (* 2 -5) 2.

Разбира се, използвайки необходимото екстремално условие, веднага получаваме желаното решение: Х ] - 4; х 2= 5. Въпреки това, използвайки този прост пример, е удобно да се демонстрира алгоритъмът на градиентния метод. Нека изчислим градиента на целевата функция:

град y \u003d (du / dx-, dy / dx 2) \u003d(4(4 - *,); 6(5 - x 2)) и изберете началната точка

А*» = (х)°> = 0; 4°> = О).

Стойността на целевата функция за тази точка, както е лесно да се изчисли, е равна на y[x^ j = 3. Нека х= const = 0,1. Стойност на градиента в точка

3c (0) е равно на grad y|x^j = (16; 30). След това на първата итерация по формули (4.21) получаваме координатите на точката

x 1)= 0 + 0,1 16 = 1,6; x^ = 0 + 0,1 30 = 3.

y (x (1)) \u003d 110 - 2 (1,6 - 4) 2 - 3 (3 - 5) 2 \u003d 86,48.

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

• 1,6 + 0,1 4(4 - 1,6) = 2,56;

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

Методът се състои в последователно намиране на частични екстремуми на целевата функция за всеки фактор. В същото време на всеки етап (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)

Лекция No8

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

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

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

и след това, като направите малка стъпка в намерената посока, отидете до нова точка x i. След това отново определете най-добрата посока за преминаване към следващата точка х 2 и т.н. На фиг. 7.4 траекторията на търсене е прекъсната линия х 0 , х 1 , х 2 ... По този начин е необходимо да се изгради последователност от точки х 0 , х 1 , х 2 ,...,х k , ... така че да се сближи до максималната точка х*, т.е. за точките от последователността, условията

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

Движение от точка x kкъм нова точка xk+1извършва се по права линия, минаваща през точката x kи има уравнението

(7.29)

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

Градиентните методи се различават един от друг по начина на избор на размера на стъпката - стойността λ k 0 на параметъра λ k . Възможно е, например, да се движите от точка до точка с постоянна стъпка λ k = λ, т.е. к

Ако се окаже че , тогава трябва да се върнете към точката и да намалите стойността на параметъра, например до λ /2.

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

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

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

Често срещан вариант на градиентно търсене се нарича метод на най-стръмно изкачване. Същността му е следната. След дефиниране на градиента в точка x kдвижение по права линия произведени до точката x k+ 1 , в който е достигната максималната стойност на функцията f(х) по посока на градиента. Тогава градиентът отново се определя в тази точка и движението се извършва по права линия в посока на новия градиент до точката x k+ 2 , където се достига максималната стойност в тази посока f(х). Движението продължава до достигане на точката. х* съответстваща на най-голямата стойност на целевата функция f(х). На фиг. 7.5 показва схемата на движение до оптималната точка х* метод на най-бързото покачване. В този случай посоката на градиента в точката x kе допирателна към линията на нивото на повърхността f(х) в точката x k+ 1, следователно градиентът в точката x k+ 1 е ортогонален на градиента (сравнете с Фигура 7.4).

Преместване от точка x kдо точка се придружава от повишаване на функцията f(х) по стойността

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

(7.31)

Нека намерим израз за производната чрез диференциране на равенството (7.30) по отношение на как сложна функция:

Замествайки този резултат в равенството (7.31), получаваме

Това равенство има проста геометрична интерпретация: градиентът в следващата точка x k+ 1, ортогонален на градиента в предишната точка x k.

са построени линиите на нивото на тази повърхност. За тази цел уравнението се свежда до вида ( х 1 -1) 2 + (x 2 -2) 2 \u003d 5-0,5 f, от което става ясно, че линиите на пресичане на параболоида с равнини, успоредни на равнината х 1 О х 2 (линии на ниво) са кръгове с радиус . При f=-150, -100, -50 техните радиуси са съответно равни , а общият център е в точката (1; 2). Намерете градиента на тази функция:

стъпвам. Изчисляваме:

На фиг. 7.6 с начало в точката х 0 =(5; 10) се конструира векторът 1/16, указващ посоката на най-бързо нарастване на функцията в точката х 0 . Следващата точка се намира в тази посока. В този момент .

Използвайки условието (7.32), получаваме

или 1-4=0, откъдето =1/4. Тъй като , тогава намерената стойност е максималната точка. Намираме х 1 =(5-16/4; 10-32/4)=(1; 2).

II стъпка. Отправна точка за втората стъпка х 1 = (1; 2). Изчислете =(-4∙1 +4; -4∙2+8)=(0; 0). Следователно, х 1 =(1; 2) е неподвижна точка. Но тъй като дадена функциявдлъбнат, то в намерената точка (1; 2) се достига глобалният максимум.

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

Помислете за проблем с изпъкнало програмиране с линейни ограничения:

(7.34)

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

Нека започнем с геометрична илюстрация на процеса на решаване на проблема (фиг. 7.7). Нека началната точка х 0 се намира в разрешената зона. От точка х 0 можете да се движите в посоката на градиента, докато f(х) няма да достигне максимума. В нашия случай f(х) нараства през цялото време, така че трябва да спрете в точката х, на граничната линия. Както се вижда от фигурата, не е възможно да се движим по-нататък в посоката на градиента, тъй като ще напуснем допустимата зона. Следователно е необходимо да се намери друга посока на движение, която, от една страна, да не излиза от допустимата област, а от друга, да осигурява най-голямо увеличение на f(х). Такава посока ще определи вектора , който е най-малък с вектора остър ъгълв сравнение с всеки друг вектор, изходящ от точка x iи лежащ в допустимия район. Аналитично, такъв вектор може да се намери от условието за максимизиране на скаларното произведение . В този случай векторът, показващ най-изгодната посока, съвпада с граничната линия.

Така на следващата стъпка е необходимо да се движите по граничната линия, докато f(х); в нашия случай - по същество х 2. От фигурата се вижда, че следва да се движи по-нататък в посока на вектора , което се намира от условието за максимизиране на скаларното произведение , т.е. по протежение на граничната линия. Движението завършва в точка х 3, тъй като търсенето за оптимизация приключва в този момент, тъй като функцията f(х) има локален максимум. Поради вдлъбнатината в тази точка f(х) също достига глобален максимум в допустимия регион. градиент в максимална точка х 3 =х* прави тъп ъгъл с който и да е вектор от валидната област, преминаващ през него х 3, така скаларно произведениеще бъде отрицателен за всеки допустим рк, Освен това r 3, насочена по граничната линия. За него скаларното произведение = 0, тъй като и са взаимно перпендикулярни (граничната линия докосва линията на нивото на повърхността f(х), преминаваща през максималната точка х*). Това равенство служи като аналитичен знак, че в точката х 3 функция f(х) достигна своя максимум.

Разгледайте сега аналитичното решение на проблема (7.33) - (7.35). Ако търсенето на оптимизация започва от точка, лежаща в допустимата област (всички ограничения на проблема са изпълнени като строги неравенства), тогава трябва да се движите по посоката на градиента, както е установено по-горе. Сега обаче изборът λkв уравнение (7.29) се усложнява от изискването следващата точка да остане в допустимата зона. Това означава, че неговите координати трябва да отговарят на ограниченията (7.34), (7.35), т.е. трябва да са изпълнени неравенствата:

(7.36)

Решаване на системата линейни неравенства(7.36), намираме сегмента на допустимите стойности на параметъра λk, при което точката x k +1 ще принадлежи на допустимата площ.

Значение λ k *определена в резултат на решаване на уравнение (7.32):

При което f(х) има локален максимум в λkв посока трябва да принадлежи на сегмента. Ако намерената стойност λkизлиза извън посочения сегмент, тогава като λ k *се получава. В този случай следващата точка от траекторията на търсене се оказва на граничната хиперравнина, съответстваща на неравенството на системата (7.36), според което дясната крайна точка е получена при решаването на системата. интервал от приемливи стойности на параметрите λk.

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

под ограничения

за тези т, при което

където .

В резултат на решаването на задача (7.37) - (7.40) ще бъде намерен вектор, който образува най-малкия остър ъгъл с градиента.

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

След определяне на посоката се намира стойността λ k *за следващата точка траектория на търсене. В този случай необходимото екстремално условие се използва във вид, подобен на уравнение (7.32), но със замяна на вектора , т.е.

(7.41)

Търсенето на оптимизация спира, когато се достигне точката x k *, при което .

Пример 7.5.Максимизиране на функция при ограничения

Решение.За визуално представяне на процеса на оптимизация ще го придружим с графична илюстрация. Фигура 7.8 показва няколко линии на ниво на дадена повърхност и приемлива област на OABS, в която да се намери точка х* който осигурява максимума на тази функция (вижте пример 7 4).

Нека започнем търсенето на оптимизация, например, от точката х 0 =(4, 2,5), лежащ на граничната линия AB х 1 +4х 2=14. При което f(х 0)=4,55.

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

в точката х 0 . В допълнение, от фигурата може да се види, че линиите на нивото с маркировки по-високи от f(х 0)=4,55. С една дума, трябва да търсите посока r 0 =(r 01 , r 02) преминаване към следващата точка х 1 по-близо до оптималното. За тази цел ние решаваме проблема (7.37) - (7.40) за максимизиране на функцията при ограниченията

Тъй като точката х 0 се намира само на една (първа) гранична линия ( аз=1) х 1 +4х 2 =14, тогава условието (7.38) се записва под формата на равенство.

Системата от ограничителни уравнения на този проблем има само две решения (-0.9700; 0.2425) и (0.9700; -0.2425) Чрез директното им заместване във функцията т 0 зададено на максимум т 0 не е нула и се достига чрез решаване на (-0,9700; 0,2425) По този начин се преместете от х 0 е необходимо в посоката на вектора r 0 \u003d (0,9700; 0,2425), тоест по граничната линия BA.

За определяне на координатите на следващата точка х 1 =(х 11 ; х 12)

(7.42)

необходимо е да се намери стойността на параметъра, при който функцията f(х) в точката х

откъдето = 2,0618. В същото време = -0,3999<0. Значит,=2,0618. По формуле (7.42) находим координаты новой точки х 1 (2; 3).

Ако продължим търсенето на оптимизация, тогава при решаването на следващата спомагателна задача (7.37) - (7.40) ще се установи, че Т 1 = , което означава, че точката x 1 е максималната точка x* на целевата функция в допустимата област. Същото се вижда от фигурата в точка х 1 една от нивелирните линии докосва границата на допустимата площ. Следователно точката x 1 е точката на максимум x*. При което fмакс= f(х*)=5,4.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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