Градієнтні методи. Поняття градієнта та його обчислення
Метод релаксації
Алгоритм методу полягає у відшуканні осьового напрямку, вздовж якого цільова функція зменшується найбільше сильно (при пошуку мінімуму). Розглянемо завдання безумовної оптимізації
Для визначення осьового напрямку в початковій точці пошуку з області визначаються похідні , , по всіх незалежних змінних. Осьовому напрямку відповідає найбільша по модулю похідна.
Нехай – осьовий напрямок, тобто. 
.
Якщо знак похідної негативний, функція зменшується у бік осі, якщо позитивний – у напрямі:
У точці обчислюють. У напрямку зменшення функції виконується один крок, визначається і в разі поліпшення критерію кроки продовжуються доти, доки не буде знайдено мінімальне значення за вибраним напрямком. У цій точці знову визначаються похідні по всіх змінних, за винятком тих, якою здійснюється спуск. Знову знаходиться осьовий напрямок найшвидшого спадання, яким проводяться подальші кроки тощо.
Цю процедуру повторюють до тих пір, поки не досягається оптимальна точка, при русі з якої за будь-яким осьовим напрямом подальшого зменшення не відбувається. На практиці критерієм закінчення пошуку є умова
яка при перетворюється на точну умову рівності нулю похідних у точці екстремуму. Природно, умова (3.7) може бути використана тільки в тому випадку, якщо оптимум лежить усередині допустимої області зміни незалежних змінних. Якщо оптимум потрапляє на межу області, критерій типу (3.7) непридатний і замість нього слід застосовувати позитивності всіх похідних за допустимими осьовими напрямками.
Алгоритм спуску для обраного осьового напрямку може бути записано так
(3.8)
де -значення змінної, що варіюється, на кожному кроці спуску;
Розмір k+1 кроку, який може змінюватися в залежності від номера кроку:
- Функція знака z;
Вектор точки, в якій останній разпроводилося обчислення похідних;
Знак “+” у алгоритмі (3.8) приймається під час пошуку max I, а знак “-” – під час пошуку min I.Чим менше крок h., тим більше кількістьобчислень по дорозі руху до оптимуму. Але при дуже великій величині h поблизу оптимуму може виникнути зациклювання процесу пошуку. Поблизу оптимуму необхідно, щоб виконувалася умова h Найпростіший алгоритм зміни кроку h полягає у наступному. На початку спуску задається крок , рівний наприклад, 10% діапазону d; зміни з цим кроком здійснюється спуск по обраному напрямку до того часу, поки виконується умова для двох наступних обчислень При порушенні умови на якомусь кроці напрямок спуску на осі змінюється на зворотне і спуск триває з останньої точки зі зменшеною вдвічі величиною кроку. Формальний запис цього алгоритму: В результаті використання такої стратегії ша спуску буде зменшуватися в районі оптимуму по даному напрямку і пошук за напрямом можна припинити, коли стане менше E. Потім знаходиться новий осьовий напрямок початковий крок для подальшого спуску, зазвичай менший пройденого вздовж попереднього осьового напрямку. Характер руху в оптимумі у цьому методі показаний малюнку 3.4. Рисунок 3.5 – Траєкторія руху до оптимуму у методі релаксації Поліпшення алгоритму пошуку за цим методом можна досягти шляхом застосування методів однопараметричної оптимізації. При цьому може бути запропонована схема розв'язання задачі: Крок 1. - осьовий напрямок, Крок 2. – новий осьовий напрямок; Метод градієнта У цьому методі використовується градієнт функції. Градієнтом функції у точці Рисунок 3.6 – Градієнт функції Напрямок градієнта - це напрям найбільш швидкого зростання функції (найбільш крутого схилу поверхні відгуку). Протилежний йому напрям (напрямок антиградієнта) – це напрямок найшвидшого спадання (напрямок якнайшвидшого “спуску” величин ). Проекція градієнта на площину змінних перпендикулярна до лінії рівня , тобто. градієнт ортогональний до ліній постійного рівня цільової функції(Рис. 3.6). Малюнок 3.7 – Траєкторія руху до оптимуму у методі градієнта На відміну від методу релаксації у методі градієнта кроки відбуваються у бік найшвидшого зменшення (збільшення) функції . Пошук оптимуму проводиться у два етапи. На першому етапі знаходяться значення приватних похідних по всіх змінних, які визначають напрям градієнта в точці, що розглядається. На другому етапі здійснюється крок у напрямку градієнта при пошуку максимуму або у протилежному напрямку – при пошуку мінімуму. Якщо аналітичний вираз невідомий, то напрям градієнта визначається пошуком на об'єкті пробних рухів. Нехай початкова точка. Дається збільшення величина, при цьому. Визначають збільшення та похідну Аналогічно визначають похідні за іншими змінними. Після знаходження складових градієнта пробні рухи припиняються і починаються робочі кроки обраного напрямку. Причому величина кроку тим більша, чим більша абсолютна величина вектора. За виконання кроку одночасно змінюються значення всіх незалежних змінних. Кожна з них отримує приріст, пропорційний відповідній складовій градієнта. або у векторній формі де – позитивна константа; "+" - при пошуку max I; “-” – під час пошуку min I. Алгоритм градієнтного пошуку при нормуванні градієнта (розподіл на модуль) застосовується у вигляді Визначає величину кроку за напрямом градієнта. Алгоритм (3.10) має ту перевагу, що при наближенні до оптимуму довжина кроку автоматично зменшується. А за алгоритму (3.12) стратегію зміни можна будувати незалежно від абсолютної величини коефіцієнта. У методі градієнта кожен розділяється один робочий крок, після якого знову обчислюються похідні, визначається новий напрямок градієнта та процес пошуку триває (рис. 3.5). Якщо розмір кроку вибраний занадто малим, то рух до оптимуму буде занадто довгим через необхідність обчислення в багатьох точках. Якщо крок вибраний занадто великим, в район оптимуму може виникнути зациклювання. Процес пошуку триває до тих пір, поки , , не стануть близькими до нуля або поки не буде досягнуто межі області завдання змінних. В алгоритмі з автоматичним уточненням кроку величину уточнюють так, щоб зміна напряму градієнта у сусідніх точках та Критерії закінчення пошуку оптимуму: де Пошук завершується під час виконання однієї з умов (3.14) – (3.17). Недоліком градієнтного пошуку (як і розглянутих вище методів) і те, що з його використанні можна знайти лише локальний екстремумфункції. Для пошуку інших локальних екстремумів потрібно проводити пошук з інших початкових точок. Градієнтний метод та його різновиди відносяться до найпоширеніших методів пошуку екстремуму функцій кількох змінних. Ідея градієнтного методу полягає в тому, щоб у процесі пошуку екстремуму (для визначеності максимуму) рухатись щоразу у напрямку найбільшого зростання цільової функції. Градієнтний метод передбачає обчислення перших похідних цільової функції за її аргументами. Він, як і попередні, відноситься до наближених методів і дозволяє, як правило, не досягти точки оптимуму, а лише наблизитись до неї за кінцеве число кроків. Рис. 4.11. Рис. 4.12. (двовимірний випадок) Спочатку вибирають початкову точку Якщо в одновимірному випадку (див. підпункт 4.2.6) з неї можна було зрушити тільки вліво або вправо (див. рис. 4.9), то в багатовимірному випадку число можливих напрямків переміщення нескінченно велике. На рис. 4.11, що ілюструє випадок двох змінних, стрілками, що виходять із початкової точки А,показано різні можливі напрямки. При цьому рух за деякими з них дає збільшення значення цільової функції по відношенню до точки А(наприклад, напрямки 1-3),
а за іншими напрямками призводить до його зменшення (напрямки 5-8).
Враховуючи, що положення точки оптимуму невідоме, вважається найкращим напрямок, у якому цільова функція зростає найшвидше. Цей напрямок називається градієнтомфункції. Зазначимо, що в кожній точці координатної площини напрямок градієнта перпендикулярно до лінії рівня, проведеної через ту ж точку. У математичному аналізі доведено, що елементи градієнта складають функції у =/(*, х 2 , ..., х п)є її окремими похідними за аргументами, тобто. &ад/(х 1,х 2 ,.= (ду/дху,ду/дх 2, ...,ду/дх п). (4.20) Таким чином, при пошуку максимуму методом градієнта на першій ітерації обчислюють складові градієнта за формулами (4.20) для початкової точки і роблять робочий крок у знайденому напрямку, тобто. здійснюється перехід у нову точку -0) У" з координатами: 1§гас1/(х (0)), або у векторній формі де X -постійний чи змінний параметр, що визначає довжину робочого кроку, ?і>0. На другій ітерації знову обчислюють вектор градієнта вже для нової точки.У, після чого по анало- гічній формулі переходять у точку х^ >
і т.д. (Рис. 4.12). Для довільної до-й ітерації маємо Якщо знаходиться не максимум, а мінімум цільової функції, то на кожній ітерації робиться крок у напрямку, протилежному напрямку градієнта. Воно називається напрямом антиградієнта. Замість формули (4.22) у цьому випадку буде Існує багато різновидів способу градієнта, що відрізняються вибором робочого кроку. Можна, наприклад, переходити в кожну наступну точку за постійної величини X,і тоді довжина робочого кроку - відстань між сусідніми точками х^ їх 1” – виявиться пропорційним модулю вектора градієнта. Можна, навпаки, на кожній ітерації вибирати Xтаким, щоб довжина робочого кроку залишалася постійною. приклад.Потрібно знайти максимум функції у = 110-2(лг, -4) 2 -3(* 2 -5) 2 . Зрозуміло, скориставшись необхідною умовою екстремуму, відразу отримаємо рішення: х] - 4; х 2= 5. Однак у цьому простому прикладі зручно продемонструвати алгоритм градієнтного методу. Обчислимо градієнт цільової функції: grad у = (ду/дх-,ду/дх 2) =(4(4 - *,); 6(5 - х 2)) і вибираємо початкову точку Л*» = (х) °> = 0; 4 °> = О). Значення цільової функції для цієї точки, як легко підрахувати, дорівнює у[х^ j = 3. Припустимо, X= Const = 0,1. Розмір градієнта у точці Зс (0) дорівнює grad y|x^j = (16; 30). Тоді на першій ітерації отримаємо згідно з формулами (4.21) координати точки х 1)= 0 + 0,1 16 = 1,6; х ^ = 0 + 0,1 30 = 3. у (х (1)) = 110 - 2 (1,6 - 4) 2 - 3 (3 - 5) 2 = 86,48. Як видно, воно суттєво більше за попереднє значення. На другій ітерації маємо за формулами (4.22): Метод Гауса-Зейделя Метод полягає у черговому знаходженні приватних екстремумів цільової функції за кожним фактором. При цьому на кожному етапі стабілізують (k-1) факторів і варіюють лише один i-ий фактор Порядок розрахунку: у локальній області факторного простору виходячи з попередніх дослідів вибирають точку, відповідну найкращому результату процесу, і з неї починають рух до оптимуму. Крок руху за кожним фактором задається дослідником. Спочатку фіксують всі фактори на одному рівні і змінюють один фактор доти, доки буде збільшення (зменшення) функції відгуку (Y), потім змінюють інший фактор при стабілізації інших і т. д. доти не отримають бажаний результат (Y) . Головне правильно вибрати крок руху за кожним фактором. Цей спосіб найбільш простий, наочний, але рух до оптимуму тривалий час і метод рідко призводить до оптимальної точки. В даний час він іноді застосовується при машинному експерименті. Ці методи забезпечують рух до оптимуму прямою перпендикулярною до ліній рівного відгуку, тобто в напрямку градієнта функції відгуку. Градієнтні методимають кілька різновидів, що відрізняються правилами вибору щаблів варіювання та робочих кроків кожному етапі руху до екстремуму. Сутність всіх методів полягає у наступному: спочатку виходячи з попередніх дослідів вибирають базову точку. Потім кожному етапі навколо чергової базової точки організують пробні експерименти, за результатами яких оцінюють новий напрям градієнта, після чого у цьому напрямі роблять один робочий крок. Метод градієнта (звичайний) здійснюється за такою схемою: а) вибирають базову точку; б) вибирають кроки руху за кожним фактором; в) визначають координати пробних точок; г) проводять експерименти у пробних точках. В результаті одержують значення параметра оптимізації (Y) у кожній точці. д) за результатами дослідів обчислюють оцінки складових вектор-градієнта в т. м. для кожного i-го фактора: де H i -крок руху X i . X i – координати попередньої робочої точки. ж) координати цієї робочої точки приймають за нову базову точку, навколо якої проводять експерименти у пробних точках. Обчислюють градієнт і т. д., доки не досягнуть бажаного параметра оптимізації (Y). Коригування напряму руху провадиться після кожного кроку. Переваги методу: простота, вища швидкість руху до оптимуму. Недоліки: велика чутливість до перешкод. Якщо крива має складну форму, метод може призвести до оптимуму. Якщо крива відгуку полога - метод малоефективний. Метод не дає інформації щодо взаємодії факторів. а) Метод крутого сходження (Бокса – Вілсона). б) Ухвалення рішень після крутого сходження. в) симптомний метод оптимізації. г) Переваги та недоліки методів. 5.7.3 Метод крутого сходження (Бокса-Вілсона) Цей метод є синтезом кращих рисградієнтних методів, методу Гаусса-Зейделя та методів ПФЕ та ДФЕ – як засоби отримання математичної моделі процесу. Розв'язання задачі оптимізації даним методом виконується так, щоб кроковий рух здійснювався у напрямку якнайшвидшого зростання (зменшення) параметра оптимізації. Коригування напряму руху (на відміну від градієнтних методів) проводиться не після кожного кроку, а по досягненню приватного екстремуму цільової функції. Далі в точках приватного екстремуму ставиться новий факторний експеримент, складається нова математична модельі знову повторюється круте сходження до досягнення глобального оптимуму. Рух градієнтом починають з нульової точки (центру плану). Метод крутого сходження передбачає рух до оптимуму за градієнтом. Де i,j,k-поодинокі вектори у бік відповідних координатних осей. Порядок розрахунку. Вихідними даними є математична модель процесу, отримана будь-яким способом (ПФЕ, ДФЕ тощо). Розрахунки проводять у такому порядку: а) рівняння регресії краще перевести в натуральний вигляд за формулами кодування змінних: де x i-кодоване значення змінної x i; X i - натуральне значення змінної x i; X i Ц -центральний рівень фактора в натуральному вигляді; l i -інтервал варіювання фактора x i в натуральному вигляді. б) обчислюють кроки руху до оптимуму за кожним фактором. Для цього обчислюють добутки коефіцієнтів рівняння регресії у натуральному вигляді на відповідні інтервали варіювання B i *.l I ,
Потім вибирають з отриманих творів максимальний за модулем,а відповідний цьому твору фактор приймають за базовий фактор(Bala). Для базового фактора слід встановити крок руху, який рекомендується задавати меншим або рівним інтервалу варіювання базового фактора Знак кроку руху l a ' має збігатися зі знаком коефіцієнта рівняння регресії, що відповідає базовому фактору (Ba). Величина кроків для інших факторів обчислюється пропорційно до базового за формулою: Знаки кроків руху також мають співпадати зі знаками відповідних коефіцієнтів рівняння регресії. в) обчислюють функцію відгуку у центрі плану, т. е. при значеннях чинників рівних центральному рівню чинників, т. до. рух до оптимуму починають із центру плану. Далі здійснюють обчислення параметра оптимізації, збільшуючи значення факторів на величину відповідного кроку руху, якщо хочуть отримати Y max . В іншому випадку, якщо необхідно отримати Y min значення факторів зменшують на величину кроку руху. Процедуру повторюють, послідовно збільшуючи кількість кроків до тих пір, поки досягнуто бажаного значення параметра оптимізації (Y). Кожен із факторів після gкроків матиме значення: Якщо Y® max X i = X i ц + gl i ` ' якщо Y ® min . X i = X i ц -gl i `.(5.36) Лекція №8 Градієнтні методи розв'язання задач нелінійного програмування. Методи штрафних функцій. Програми нелінійного програмування до завдань дослідження операцій. Завдання без обмежень.Градієнтним методом можна вирішувати, взагалі кажучи, будь-яке нелінійне завдання. Однак при цьому є лише локальний екстремум. Тому доцільніше застосовувати цей метод під час вирішення завдань опуклого програмування, у яких будь-який локальний екстремум, є водночас і глобальним (див. теорему 7.6). Розглянемо завдання максимізації нелінійної диференційованої функції f(x). Суть градієнтного пошуку точки максимуму х* Досить проста: треба взяти довільну точку х 0 і за допомогою градієнта , обчисленого в цій точці, визначити напрямок, в якому f(х) зростає з найбільшою швидкістю (рис. 7.4), а потім, зробивши невеликий крок у знайденому напрямку, перейти до нової точки x i. Потім знову визначити найкращий напрямок для переходу до чергової точки х 2 і т. д. На рис. 7.4 пошукова траєкторія є ламаною х 0 , x 1 , х 2 ... Отже, треба побудувати послідовність точок х 0 , x 1 , х 2 ,...,x k , ... так, щоб вона сходилася до точки максимуму х*, тобто для точок послідовності виконувались умови Градієнтні методи зазвичай дозволяють отримувати точне рішення за нескінченну кількість кроків і тільки в деяких випадках - за кінцеве. У зв'язку з цим градієнтні методи належать до наближених методів рішення. Рух із точки х kу нову точку x k+1здійснюється по прямій, що проходить через точку х kі має рівняння де k - числовий параметр, від якого залежить величина кроку. Як тільки значення параметра в рівнянні (7.29) вибрано: k = k 0 , так стає визначеною чергова точка на пошуковій ламаною. Градієнтні методи відрізняються один від одного способом вибору величини кроку - значення k 0 параметра k. Можна, наприклад, рухатися з точки в точку з постійним кроком k = λ, тобто при будь-якому k Якщо при цьому виявиться, що Іноді величина кроку береться до пропорційної модулю градієнта. Якщо шукається наближене рішення, пошук можна припинити, ґрунтуючись на наступних міркуваннях. Після кожної серії з певної кількостікроків порівнюють досягнуті значення цільової функції f(x). Якщо після чергової серії зміна f(x) не перевищує деякого наперед заданого малого числа , пошук припиняють і досягнуте значення f(x) розглядають як шуканий наближений максимум, а відповідне йому хприймають за х*. Якщо цільова функція f(x) увігнута (опукла), то необхідним і достатньою умовоюоптимальності точки х* є рівність нулю градієнта функції у цій точці. Поширеним є варіант градієнтного пошуку, який називається методом якнайшвидшого підйому. Суть його наступного. Після визначення градієнта у точці х дорух вздовж прямої Переміщення з точки х kу точку супроводжується зростанням функції f(x) на величину З виразу (7.30) видно, що збільшення є функцією змінної , тобто . При знаходженні максимуму функції f(x) у напрямку градієнта ) необхідно вибирати крок переміщення (множник ), що забезпечує найбільше зростання збільшення функції, саме функції . Величина, при якій досягається найбільше значення, може бути визначена з необхідної умови екстремуму функції: Знайдемо вираз для похідної, диференціюючи рівність (7.30) як складну функцію: Підставляючи цей результат у рівність (7.31), отримуємо Ця рівність має просте геометричне тлумачення: градієнт у черговій точці х до+ 1 ортогональний градієнту в попередній точці х до. I крок. Обчислюємо: На рис. 7.6 з початком у точці х 0 =(5; 10) побудований вектор 1/16, що вказує напрямок якнайшвидшого зростання функції в точці х 0 . На цьому напрямку розташована наступна точка. У цій точці. Використовуючи умову (7.32), отримуємо або 1-4 = 0, звідки = 1/4. Оскільки, то знайдене значення є точкою максимуму. Знаходимо x 1 =(5-16/4; 10-32/4)=(1; 2). II крок. Початкова точка для другого кроку x 1 = (1; 2). Обчислюємо =(-4∙1+4; -4∙2+8)=(0; 0). Отже, х 1 = (1; 2) є стаціонарною точкою. Але оскільки дана функціяувігнута, то в знайденій точці (1; 2) досягається глобальний максимум. Завдання з лінійними обмеженнями. Відразу ж відзначимо, що якщо цільова функція f(х) у задачі з обмеженнями має єдиний екстремум і він знаходиться всередині допустимої області, то для пошуку екстремальної точки х* застосовується викладена вище методика без будь-яких змін. Розглянемо задачу опуклого програмування з лінійними обмеженнями: Передбачається, що f(х) є увігнутою функцією і має безперервні приватні похідні у кожній точці допустимої області. Почнемо з геометричної ілюстрації процесу розв'язання задачі (рис. 7.7). Нехай початкова точка х 0 розташована всередині припустимої області. З точки х 0 можна рухатися в напрямку градієнта , поки f(x) не досягне максимуму. У нашому випадку f(x) весь час зростає, тому зупинитися треба в точці х, на граничній прямій. Як видно з малюнка, далі рухатися у напрямку градієнта не можна, оскільки вийдемо з допустимої області. Тому треба знайти інший напрямок переміщення, який, з одного боку, не виводить із допустимої області, а з іншого – забезпечує найбільше зростання f(x). Такий напрямок визначить вектор , що становить найменший вектор гострий кутв порівнянні з будь-яким іншим вектором, що виходить з точки x iі лежать у допустимій області. Аналітично такий вектор знайдеться за умови максимізації скалярного твору Розглянемо тепер аналітичне розв'язання задачі (7.33) – (7.35). Якщо оптимізаційний пошук починається з точки, що лежить у допустимій області (усі обмеження завдання виконуються як суворі нерівності), то переміщатися слід у напрямку градієнта так, як встановлено вище. Однак тепер вибір λ kу рівнянні (7.29) ускладнюється вимогою, щоб чергова точка залишалася у допустимій області. Це означає, що її координати повинні відповідати обмеженням (7.34), (7.35), тобто повинні виконуватися нерівності: Вирішуючи систему лінійних нерівностей(7.36), знаходимо відрізок допустимих значень параметра λ k, При яких точка х k +1 належатиме допустимій області. Значення λ k *, Яке визначається в результаті рішення рівняння (7.32): За якого f(x) має локальний максимум по λ kу напрямі, має належати відрізку . Якщо ж знайдене значення λ kвиходить за межі зазначеного відрізка, то як λ k *приймається. У цьому випадку чергова точка пошукової траєкторії виявляється на граничній гіперплощині, що відповідає тій нерівності системи (7.36), за якою при вирішенні системи отримана права кінцева точка. відрізка допустимих значень параметра λ k. Якщо оптимізаційний пошук розпочато з точки, що лежить на граничній гіперплощині, або чергова точка пошукової траєкторії виявилася на граничній гіперплощині, то для продовження руху до точки максимуму насамперед необхідно знайти найкращий напрямок руху. З цією метою слід вирішити допоміжне завдання математичного програмування, а саме - максиміз функцію при обмеженнях для тих t, за яких де В результаті розв'язання задачі (7.37) - (7.40) буде знайдено вектор , що становить з градієнтом найменший гострий кут. Умова (7.39) говорить про те, що точка належить межі допустимої області, а умова (7.38) означає, що переміщення з вектором буде направлено всередину допустимої області або по її кордоні. Умова нормалізації (7.40) необхідна обмеження величини , оскільки у іншому разі значення цільової функції (7.37) можна зробити як завгодно великим Відомі різні формиумов нормалізації, і залежно від цього завдання (7.37) – (7.40) може бути лінійним або нелінійним. Після визначення напрямку знаходиться значення λ k *для наступної точки Оптимізаційний пошук припиняється, коли досягнуто точки x k *, в якій Приклад 7.5.Максимізувати функцію при обмеженнях Рішення.Для наочного подання процесу оптимізації супроводжуватимемо його графічною ілюстрацією. На рис 7.8 зображено кілька ліній рівня даної поверхні та допустима область ОАВС, у якій слід знайти точку х*, що доставляє максимум цієї функції (див. приклад 7 4). Почнемо оптимізаційний пошук, наприклад, з точки х 0 =(4, 2,5), що лежить на граничній прямій АВ x 1 +4x 2 = 14. При цьому f(х 0)=4,55. Знайдемо значення градієнта у точці x 0 . Крім того, і по малюнку видно, що через допустиму область проходять лінії рівня з позначками вищими, ніж f(x 0) = 4,55. Словом, треба шукати напрямок r 0 =(r 01 , r 02) переміщення до наступної точки x 1 ближчу до оптимальної. З цією метою розв'язуємо задачу (7.37) – (7.40) максимізації функції при обмеженнях Система обмежувальних рівнянь цього завдання має лише два рішення (-0,9700; 0,2425) та (0,9700;-0,2425) Безпосередньою підстановкою їх у функцію T 0 встановлюємо, що максимум Т 0 відмінний від нуля і досягається при вирішенні (-0,9700; 0,2425) Таким чином, переміщатися з х 0 потрібно за напрямом вектора r 0 = (0,9700; 0,2425), тобто по граничній прямий ВА. Для визначення координат наступної точки x 1 =(x 11 ; x 12) необхідно знайти значення параметра , у якому функція f(x) у точці x звідки =2,0618. У цьому =-0,3999<0. Значит,=2,0618. По формуле (7.42) находим координаты новой точки х 1 (2; 3). Якщо продовжити оптимізаційний пошук, то при вирішенні чергової допоміжної задачі (7.37)-(7.40) буде встановлено, що Т 1 = способи переміщення, що забезпечують побудову послідовності точок, розташованих поблизу кордону і всередині допустимої області, або зигзагоподібний рух уздовж кордону з перетином останньої. Як видно з малюнка, повернення з точки x 1 у допустиму область слід здійснювати вздовж градієнта тієї граничної функції, яка виявилася порушеною. Це забезпечить відхилення чергової точки х2 у бік точки екстремуму х*. Ознакою екстремуму у разі буде коллинеарность векторів і . Метод градієнтного спуску. Напрямок якнайшвидшого спуску відповідає напрямку максимального зменшення функції. Відомо, що напрям найбільшого зростання функції двох змінних u = f(x, у) характеризується її градієнтом: де e1, е2 - поодинокі вектори (орти) у напрямі координатних осей. Отже, напрямок, протилежний градієнтному, вкаже напрямок найбільшого зменшення функції. Методи, що базуються на виборі шляху оптимізації за допомогою градієнта, називаються градієнтними. Ідея методу градієнтного спуску полягає в наступному. Вибираємо деяку початкову точку обчислюємо в ній градієнт цієї функції. Робимо крок у напрямку, зворотному до градієнтного: Процес триває до найменшого значення цільової функції. Строго кажучи, момент закінчення пошуку настане тоді, коли рух із отриманої точки з будь-яким кроком призводить до зростання значення цільової функції. Якщо мінімум функції досягається всередині області, що розглядається, то в цій точці градієнт дорівнює нулю, що також може служити сигналом про закінчення процесу оптимізації. Метод градієнтного спуску має той самий недолік, що й метод покоординатного спуску: за наявності ярів лежить на поверхні збіжність методу дуже повільна. В описаному методі потрібно обчислювати кожному кроці оптимізації градієнт цільової функції f(х): Формули для приватних похідних можна одержати у явному вигляді лише тому випадку, коли цільова функція задана аналітично. В іншому випадку ці похідні обчислюються за допомогою чисельного диференціювання: При використанні градієнтного спуску в задачах оптимізації основний обсяг обчислень зазвичай припадає на обчислення градієнта цільової функції в кожній точці траєкторії спуску. Тому доцільно зменшити кількість таких точок без шкоди самого рішення. Це досягається у деяких методах, що є модифікаціями градієнтного спуску. Одним із них є метод якнайшвидшого спуску. Відповідно до цього методу, після визначення у початковій точці напрямку, протилежного градієнту цільової функції, вирішують одновимірне завдання оптимізації, мінімізуючи функцію вздовж цього напрямку. Зокрема, мінімізується функція: Для мінімізації Метод якнайшвидшого спуску випадку функції двох змінних z = f(x,y). По-перше, легко показати, що градієнт функції перпендикулярний до лінії рівня в даній точці. Отже, у градієнтних методах спуск відбувається нормалі до лінії рівня. По-друге, у точці, в якій досягається мінімум цільової функції вздовж напрямку, похідна функції в цьому напрямі звертається в нуль. Але похідна функції дорівнює нулю за напрямом до лінії рівня. Звідси випливає, що градієнт цільової функції в новій точці перпендикулярний до напрямку одномірної оптимізації на попередньому кроці, тобто спуск на двох послідовних кроках проводиться у взаємно перпендикулярних напрямках.
(3.9)
; , якщо;
називається вектор, проекціями якого на координатні осі є приватні похідні функції координат (рис. 6.5)
.
, (3.10)
, (3.11)
; (3.12)
(3.13)
; (3.16)
; (3.17)
- Норма вектора.
(7.29)
, то слід повернутися в точку і зменшити значення параметра, наприклад, до λ
/2.
виробляється до точки х до+ 1 , в якій досягається максимальне значення функції f(х) у напрямку градієнта . Потім у цій точці знову визначається градієнт, і рух відбувається по прямій у напрямку нового градієнта до точки х до+ 2 , в якій досягається максимальне в цьому напрямку значення f(x). Рух триває доти, доки не буде досягнуто крапки х*, що відповідає найбільшому значенню цільової функції f(x). На рис. 7.5 наведено схему руху до оптимальної точки х* шляхом якнайшвидшого підйому. У цьому випадку напрямок градієнта у точці х kє дотичним до лінії рівня поверхні f(х) у точці х до+ 1 , отже, градієнт у точці х до+ 1 ортогональний градієнту (порівняйте з рис. 7.4).
(7.31)
побудовані лінії рівня цієї поверхні. З цією метою рівняння наведено до виду ( x 1 -1) 2 + (x 2 -2) 2 = 5-0,5 f, з якого ясно, що лініями перетину параболоїда з площинами, паралельними площині x 1 Про x 2 (лініями рівня), є кола радіусом . При f=-150, -100, -50 їх радіуси рівні відповідно 
, а загальний центр знаходиться у точці (1; 2). Знаходимо градієнт цієї функції: 
(7.34)
. В даному випадку вектор, що вказує найвигідніший напрямок, збігається з граничною прямою.
Таким чином, на наступному кроці рухатися треба по граничній прямій доти, доки зростає f(x); у нашому випадку - до точки х 2 . З малюнка видно, що далі слід переміщатися у напрямку вектора , що з умови максимізації скалярного твору 
, Т. е. по граничній прямий. Рух закінчується у точці х 3 оскільки в цій точці завершується оптимізаційний пошук, бо в ній функція f(х) має локальний максимум. Через увігнутість у цій точці f(х) Досягає також глобального максимуму в допустимій області. Градієнт у точці максимуму х 3 =х* Складає тупий кут з будь-яким вектором з допустимої області, що проходить через х 3тому скалярний твірбуде негативним для будь-якого допустимого r kкрім r 3 , спрямованого по граничній прямій. Для нього скалярний добуток =0, так як і взаємно перпендикулярні (гранична пряма стосується лінії рівня поверхні f(х), що проходить через точку максимуму х*). Ця рівність і є аналітичною ознакою того, що в точці х 3 функція f(x) досягла максимуму. 
(7.36)
.
пошукової траєкторії. При цьому використовується необхідна умова екстремуму у формі, аналогічній до рівняння (7.32), але із заміною на вектор , тобто.
(7.41)
.
Оскільки точка х 0 розташовується тільки на одній (першій) граничній прямій ( i=1) x 1 +4x 2 = 14, то умова (7.38) записується у формі рівності. 
(7.42)
, а це свідчить, що точка x 1 є точкою максимуму х* цільової функції у допустимій області. Це видно і з малюнка в точці x 1 одна з ліній рівня стосується межі допустимої області. Отже, точка х 1 є точкою максимуму х*. При цьому f max = f(x*)=5,4.
Завдання із нелінійними обмеженнями. Якщо в завданнях з лінійними обмеженнями рух по граничним прямим виявляється можливим і навіть доцільним, то при нелінійних обмеженнях, що визначають опуклу область, будь-яке як завгодно мале переміщення з граничної точки може відразу вивести за межі області допустимих рішень, і виникне необхідність повернення в допустиму область (Мал. 7.9). Подібна ситуація характерна для завдань, у яких екстремум функції f(x) досягається на межі області. У зв'язку з цим застосовуються різні 
можна використовувати один із методів одновимірної оптимізації. Можна і просто рухатися в напрямку, протилежному градієнту, роблячи при цьому не один крок, а кілька кроків, поки цільова функція не перестане зменшуватися. У знайденій новій точці знову визначають напрямок спуску (за допомогою градієнта) і шукають нову точку мінімуму цільової функції і т. д. У цьому методі спуск відбувається набагато більшими кроками, і градієнт функції обчислюється в меншій кількості точок. Різниця полягає в тому, що напрям одномірної оптимізації визначається градієнтом цільової функції, тоді як покоординатний спуск проводиться на кожному кроці вздовж одного з координатних напрямків.
Завантаження...