Градієнтні методи безумовної оптимізації. Огляд градієнтних методів у задачах математичної оптимізації

Завдання безумовної оптимізації відсутні обмеження.

Нагадаємо, що градієнтом багатовимірної функції називають вектор, який аналітично виражається геометричною сумоюприватних похідних

Градієнт скалярної функції F(X) в деякій точці спрямований у бік якнайшвидшого зростання функції і ортогональний лінії рівня (поверхні постійного значення F(X), проходить через точку X k). Вектор, протилежний градієнту - антиградієнт - спрямований у бік якнайшвидшого зменшення функції F(X). У точці екстремуму grad F(X)= 0.

У градієнтних методах рух точки при пошуку мінімуму цільової функціїописується ітераційною формулою

де  k  параметр кроку на k-ї ітерації вздовж антиградієнта Для способів сходження (пошуку максимуму) необхідно рухатися по градієнту.

Різні варіанти градієнтних методів відрізняються один від одного способом вибору параметра кроку, а також обліку напрямку руху на попередньому кроці. Розглянемо такі варіанти градієнтних методів: з постійним кроком, зі змінним параметром кроку (подрібненням кроку), метод якнайшвидшого спускута метод сполучених градієнтів.

Метод із постійним параметром кроку.У цьому вся методі параметр кроку постійний кожної ітерації. Виникає питання: як вибрати величину параметра кроку? Досить малий параметр кроку може призвести до неприйнятно великою кількістюітерацій, необхідні досягнення точки мінімуму. З іншого боку, занадто великий параметр кроку може призвести до проскакування точки мінімуму і коливального обчислювального процесу біля цієї точки. Зазначені обставини є недоліками методу. Оскільки неможливо заздалегідь вгадати прийнятне значення параметра кроку  k, виникає необхідність використання градієнтного методу зі змінним параметром кроку.

У міру наближення до оптимуму вектор градієнта зменшується за величиною, прагнучи нуля, тому при  k = const Довжина кроку поступово зменшується. Поблизу оптимуму довжина вектора градієнта прямує до нуля. Довжина вектора або норма в n-мірному евклідовому просторі визначається за формулою

, де n кількість змінних.

Варіанти зупинення процесу пошуку оптимуму:

З практичної точки зору зручніше користуватися третім критерієм зупинки (оскільки цікаві значення параметрів проектування), проте для визначення близькості точки екстремуму потрібно орієнтуватися на 2-й критерій. Для зупинення обчислювального процесу можна використати декілька критеріїв.

Розглянемо приклад. Знайти мінімум цільової функції F(X) = (x 1  2) 2 + (x 2  4) 2 . Точне вирішення задачі X * = (2,0; 4,0).Вирази для приватних похідних

,
.

Вибираємо крок  k = 0,1. Здійснимо пошук із початкової точки X 1 = . Рішення подаємо у вигляді таблиці.

Градієнтний метод із дробленням параметра кроку.У цьому випадку в процесі оптимізації параметр кроку k зменшується, якщо після чергового кроку цільова функція зростає (при пошуку мінімуму). При цьому часто довжина кроку дробиться навпіл, і крок повторюється з попередньої точки. Так забезпечується точніший підхід до точки екстремуму.

Метод якнайшвидшого спуску.Методи зі змінним кроком є ​​економічнішими з погляду кількості ітерацій. Якщо оптимальна довжина кроку  k вздовж напрямку антиградієнта є рішенням одномірної задачі мінімізації, то такий метод називається методом якнайшвидшого спуску. У цьому вся методі кожної ітерації вирішується завдання одномірної мінімізації:

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

 k >0

.

У даному методірух у напрямку антиградієнта продовжується до досягнення мінімуму цільової функції (поки значення цільової функції зменшується). На прикладі розглянемо, як аналітично може бути записана кожному кроці цільова функція залежно від невідомого параметра

приклад. min F(x 1 , x 2 ) = 2x 1 2 + 4x 2 3 – 3. Тоді  F(X)= [ 4x 1 ; 12x 2 2 ]. Нехай крапка X k = , отже  F(X)= [ 8; 12], F(X k   S k ) =

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

Алгоритм методу якнайшвидшого спуску (для пошуку мінімуму)

Початковий крок. Нехай   константа зупинки. Вибрати початкову точку X 1 , покласти k = 1 і перейти до основного кроку.

Основний крок. Якщо || gradF(X)||< , то закінчити пошук, інакше визначити  F(X k ) і знайти  k  оптимальне рішеннязавдання мінімізації F(X k   k S k ) при  k  0. Покласти X k +1 = X k   k S k, присвоїти k =

k + 1 та повторити основний крок.

Для пошуку мінімуму функції однієї змінної у методі якнайшвидшого спуску можна використовувати методи унімодальної оптимізації. З великої групиметодів розглянемо метод дихотомії (бісекції) та золотого перерізу. Суть методів унімодальної оптимізації полягає у звуженні інтервалу невизначеності розміщення екстремуму.

Метод дихотомії (бісекції)Початковий крок.Вибирають константу помітності  і кінцеву довжину інтервалу невизначеності l. Величина  має бути по можливості меншою, проте що дозволяє розрізняти значення функції F( ) і F( ) . Нехай [ a 1 , b 1 ]  початковий інтервал невизначеності. Покласти k =

Основний етап складається з кінцевого числаоднотипних ітерацій.

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

Крок 1.Якщо b k  a k  l, то обчислення закінчуються. Рішення x * = (a k + b k )/2. В іншому випадку

,
.

Крок 2Якщо F( k ) < F( k ), покласти a k +1 = a k ; b k +1 =  k. В іншому випадку a k +1 =  kі b k +1 = b k. Присвоїти k = k + 1 та перейти до кроку 1.

Метод золотого перерізу.Ефективніший метод, ніж метод дихотомії. Дозволяє отримати задану величинуінтервалу невизначеності за менше ітерацій і вимагає меншого числа обчислень цільової функції. У цьому вся методі нова точка поділу інтервалу невизначеності обчислюється один раз. Нова точка ставиться з відривом

 = 0,618034 від кінця інтервалу.

Алгоритм методу золотого перерізу

Початковий крок.Вибрати допустиму кінцеву довжину інтервалу невизначеності l > 0. Нехай [ a 1 , b 1 ]  початковий інтервал невизначеності. Покласти  1 = a 1 +(1   )(b 1  a 1 ) і  1 = a 1 +  (b 1  a 1 ) , де  = 0,618 . Обчислити F( 1 ) і F( 1 ) , покласти k = 1 і перейти до основного етапу.

Крок 1.Якщо b k  a k  l, то обчислення закінчуються x * = (a k + b k )/ 2. Інакше якщо F( k ) > F( k ) , Перейти до кроку 2; якщо F( k )  F( k ) , перейти до кроку 3.

Крок 2Покласти a k +1 =  k , b k +1 = b k ,  k +1 =  k ,  k +1 = a k +1 +  (b k +1 – a k +1 ). Обчислити F( k +1 ), Перейти до кроку 4.

Крок 3Покласти a k +1 = a k , b k +1 =  k ,  k +1 =  k ,  k +1 = a k +1 + (1   )(b k +1 – a k +1 ). Обчислити F( k +1 ).

Крок 4.Присвоїти k = k + 1, перейти до кроку 1.

На першій ітерації необхідні два обчислення функції, всіх наступних лише одне.

Метод сполучених градієнтів (Флетчер-Рівс).У цьому методі вибір напряму руху на k+ 1 кроці враховує зміну напряму на kкроку. Вектор напряму спуску є лінійною комбінацією напрямку антиградієнта та попереднього напрямку пошуку. У цьому випадку при мінімізації яружних функцій (з вузькими довгими западинами) пошук не перпендикулярно яру, а вздовж нього, що дозволяє швидше дійти мінімуму. Координати точки при пошуку екстремуму методом сполучених градієнтів розраховуються за виразом X k +1 = X k   V k +1 , де V k +1 - Вектор, що розраховується за наступним виразом:

.

На першій ітерації зазвичай покладається V = 0 і виконується пошук за антиградієнтом, як у методі якнайшвидшого спуску. Потім напрямок руху відхиляється від напрямку антиградієнта тим більше, чим значніше змінювалася довжина вектора градієнта на останній ітерації. Після nкроків для корекції роботи алгоритму роблять простий крок антиградієнтом.

Алгоритм методу сполучених градієнтів

Крок 1.Ввести початкову точку Х 0 , точність  , Розмірність n.

Крок 2Покласти k = 1.

Крок 3Покласти вектор V k = 0.

Крок 4.Обчислити grad F(X k ).

Крок 5.Обчислити вектор V k +1.

Крок 6Виконати одновимірний пошук по вектору V k +1.

Крок 7.Якщо k < n, покласти k = k + 1 і перейти до кроку 4, інакше кроку 8.

Крок 8Якщо довжина вектора Vменше , закінчити пошук, інакше – перейти до кроку 2.

Метод сполучених напрямів одна із найефективніших у вирішенні завдань мінімізації. Метод разом із одномірним пошуком часто практично використовують у САПР. Однак слід зазначити, що він чутливий до помилок, що виникають у процесі рахунку.

Недоліки градієнтних методів

У завданнях з більшим числомзмінних важко чи неможливо отримати похідні у вигляді аналітичних функцій.

При обчисленні похідних за різницевими схемами помилка, що виникає при цьому, особливо в околицях екстремуму, обмежує можливості такої апроксимації.

При оптимізації шляхом градієнта оптимум досліджуваного об'єкта шукають у бік найшвидшого зростання (зменшення) вихідний змінної, тобто. у напрямку градієнта. Але перш ніж зробити крок у напрямку до градієнта, необхідно його розрахувати. Градієнт можна розрахувати або за наявною моделлю

моделювання динамічний градієнтний поліноміальний

де - приватна похідна по i-му фактору;

i, j, k - одиничні векторив напрямку координатних осейфакторного простору, або за результатами n пробних рухів у бік координатних осей.

Якщо математична модель статистичного процесумає вигляд лінійного полінома, коефіцієнти регресії b i якого є приватними похідними розкладання функції y = f(X) в ряд Тейлора за ступенями x i то оптимум шукають у напрямку градієнта з деяким кроком h i:

пкфв н(Ч)= та 1 р 1 +і 2 р 2 +…+і т р т

Напрямок коригують після кожного кроку.

Метод градієнта разом з його численними модифікаціями є поширеним і ефективним методомпошуку оптимуму досліджуваних об'єктів. Розглянемо одну з модифікацій методу градієнта – метод крутого сходження.

Метод крутого сходження, або інакше метод Бокса-Вілсона, поєднує в собі переваги трьох методів - методу Гаусса-Зейделя, методу градієнтів та методу повного (або дробового) факторного експериментів, як засобу отримання лінійної математичної моделі. Завдання методу крутого сходження полягає в тому, щоб кроковий рух здійснювати в напрямку якнайшвидшого зростання (або зменшення) вихідної змінної, тобто по grad y (X). На відміну від методу градієнтів, напрям коригується не після кожного наступного кроку, а при досягненні в певній точці на цьому напрямку приватного екстремуму цільової функції, як це робиться у методі Гауса-Зейделя. У точці приватного екстремуму ставиться новий факторний експеримент, визначається математична модель і знову круте сходження. У процесі руху до оптимуму вказаним методом регулярно проводитись статистичний аналіз проміжних результатівпошуку. Пошук припиняється, коли квадратичні ефекти у рівнянні регресії стають значущими. Це означає, що досягнуто області оптимуму.

Опишемо принцип використання градієнтних методів на прикладі функції двох змінних

за наявності двох додаткових умов:

Цей принцип (без зміни) можна застосувати за будь-якої кількості змінних, а також додаткових умов. Розглянемо площину x1, x2 (Рис. 1). Відповідно до формули (8) кожній точці відповідає деяке значення F. На Рис.1 лінії F = const, що належать цій площині, представлені замкнутими кривими, що оточують точку M * , в якій F мінімально. Нехай у початковий моментзначення x 1 та x 2 відповідають точці M 0 . Цикл розрахунку починається із серії пробних кроків. Спочатку величині x 1 дається невелике збільшення; в цей час значення х 2 незмінне. Потім визначається отримане при цьому збільшення величини F, яке можна вважати пропорційним значенню приватної похідної

(якщо величина завжди та сама).

Визначення приватних похідних (10) та (11) означає, що знайдено вектор з координатами і, який називається градієнтом величини F і позначається так:

Відомо, що напрям цього вектора збігається з напрямом найбільш крутого зростання величини F. Протилежне йому напрям - це «найшвидший спуск», тобто найбільш круте зменшення величини F.

Після знаходження складових градієнта пробні рухи припиняються і здійснюються робочі кроки в напрямку, протилежному до напряму градієнта, причому величина кроку тим більше, чим більше абсолютна величинавектора grad F. Ці умови здійснюються, якщо величини робочих кроків і пропорційні отриманим раніше значенням приватних похідних:

де б – позитивна константа.

Після кожного робочого кроку оцінюється збільшення величини F. Якщо воно виявляється негативним, то рух відбувається в правильному напрямкуі потрібно рухатися в тому ж напрямку M0M1 далі. Якщо ж у точці M 1 результат виміру показує, що, то робочі рухи припиняються і починається Нова серіяпробні рухи. При цьому визначається градієнт gradF в новій точці M 1 потім робочий рухпродовжується за новим знайденим напрямком якнайшвидшого спуску, тобто по лінії M 1 M 2 і т.д. Цей метод називається методом якнайшвидшого спуску/крутого сходження.

Коли система знаходиться поблизу мінімуму, показником чого є мінімальне значення величини

відбувається переключення більш «обережний» метод пошуку, так званий метод градієнта. Від методу якнайшвидшого спуску він відрізняється тим, що після визначення градієнта gradF робиться лише один робочий крок, а потім у новій точці знову починається серія пробних рухів. Такий метод пошуку забезпечує більш точне встановлення мінімуму в порівнянні з методом якнайшвидшого спуску, тим часом як останній дозволяє швидше наблизитися до мінімуму. Якщо процесі пошуку точка М доходить межі допустимої області і хоча одна з величин М 1 , М 2 змінює знак, метод змінюється і точка М починає рухатися вздовж кордону області.

Ефективність методу крутого сходження залежить від вибору масштабу змінних та виду поверхні відгуку. Поверхня зі сферичними контурами забезпечує швидке стягування до оптимуму.

До недоліків методу крутого сходження слід віднести:

1. Обмеженість екстраполяції. Рухаючись вздовж градієнта, ми ґрунтуємось на екстраполяції приватних похідних цільової функції за відповідними змінними. Однак форма поверхні відгуку може змінюватися і необхідно змінювати напрямок пошуку. Іншими словами, рух на площині не може бути тривалим.

2. Проблема пошуку глобального оптимуму. Метод застосовний для відшукання лише локальних оптимумів.

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

Напрямок якнайшвидшого спуску відповідає напрямку максимального зменшення функції. Відомо, що напрям найбільшого зростання функції двох змінних u = f(x, у) характеризується її градієнтом:

де e1, е2 - поодинокі вектори (орти) у напрямі координатних осей. Отже, напрямок, протилежний градієнтному, вкаже напрямок найбільшого зменшення функції. Методи, що базуються на виборі шляху оптимізації за допомогою градієнта, називаються градієнтними.

Ідея методу градієнтного спуску полягає в наступному. Вибираємо деяку початкову точку

обчислюємо в ній градієнт цієї функції. Робимо крок у напрямку, зворотному до градієнтного:

Процес триває до найменшого значення цільової функції. Строго кажучи, момент закінчення пошуку настане тоді, коли рух із отриманої точки з будь-яким кроком призводить до зростання значення цільової функції. Якщо мінімум функції досягається всередині області, що розглядається, то в цій точці градієнт дорівнює нулю, що також може служити сигналом про закінчення процесу оптимізації.

Метод градієнтного спуску має той самий недолік, що й метод покоординатного спуску: за наявності ярів на поверхні збіжність методу дуже повільна.

В описаному методі потрібно обчислювати кожному кроці оптимізації градієнт цільової функції f(х):

Формули для приватних похідних можна одержати у явному вигляді лише тому випадку, коли цільова функція задана аналітично. В іншому випадку ці похідні обчислюються за допомогою чисельного диференціювання:

При використанні градієнтного спуску в задачах оптимізації основний обсяг обчислень зазвичай припадає на обчислення градієнта цільової функції в кожній точці траєкторії спуску. Тому доцільно зменшити кількість таких точок без шкоди самого рішення. Це досягається у деяких методах, що є модифікаціями градієнтного спуску. Одним із них є метод якнайшвидшого спуску. Відповідно до цього методу, після визначення у початковій точці напрямку, протилежного градієнту цільової функції, вирішують одновимірне завдання оптимізації, мінімізуючи функцію вздовж цього напрямку. Зокрема, мінімізується функція:

Для мінімізації можна використовувати один із методів одновимірної оптимізації. Можна і просто рухатися у напрямку, протилежному градієнту, роблячи при цьому не один крок, а кілька кроків доти, доки цільова функція не перестане зменшуватися. У знайденій новій точці знову визначають напрям спуску (за допомогою градієнта) і шукають нову точку мінімуму цільової функції і т. д. У цьому методі спуск відбувається набагато більшими кроками, і градієнт функції обчислюється в меншому числіточок. Різниця полягає в тому, що тут напрямок одномірної оптимізації визначається градієнтом цільової функції, тоді як покоординатний спуск проводиться на кожному кроці вздовж одного з координатних напрямків.

Метод якнайшвидшого спуску випадку функції двох змінних z = f(x,y).

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

Лекція №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і має рівняння

(7.29)

де k - числовий параметр, від якого залежить величина кроку. Як тільки значення параметра в рівнянні (7.29) вибрано: k = k 0 , так стає визначеною чергова точка на пошуковій ламаною.

Градієнтні методи відрізняються один від одного способом вибору величини кроку - значення k 0 параметра k. Можна, наприклад, рухатися з точки в точку з постійним кроком k = λ, тобто при будь-якому k

Якщо при цьому виявиться, що , то слід повернутися в точку і зменшити значення параметра, наприклад, до λ /2.

Іноді величина кроку береться до пропорційної модулю градієнта.

Якщо шукається наближене рішення, пошук можна припинити, ґрунтуючись на наступних міркуваннях. Після кожної серії з певної кількості кроків порівнюють досягнуті значення цільової функції f(x). Якщо після чергової серії зміна f(x) не перевищує деякого наперед заданого малого числа , пошук припиняють і досягнуте значення f(x) розглядають як шуканий наближений максимум, а відповідне йому хприймають за х*.

Якщо цільова функція f(x) увігнута (опукла), то необхідним і достатньою умовоюоптимальності точки х* є рівність нулю градієнта функції у цій точці.

Поширеним є варіант градієнтного пошуку, який називається методом якнайшвидшого підйому. Суть його наступного. Після визначення градієнта у точці х дорух вздовж прямої виробляється до точки х до+ 1 , в якій досягається максимальне значенняфункції f(х) у напрямку градієнта . Потім у цій точці знову визначається градієнт, і рух відбувається по прямій у напрямку нового градієнта до точки х до+ 2 , в якій досягається максимальне в цьому напрямку значення f(x). Рух триває доти, доки не буде досягнуто крапки х*, що відповідає найбільшому значенню цільової функції f(x). На рис. 7.5 наведено схему руху до оптимальної точки х* шляхом якнайшвидшого підйому. У даному випадкунапрям градієнта у точці х kє дотичним до лінії рівня поверхні f(х) у точці х до+ 1 , отже, градієнт у точці х до+ 1 ортогональний градієнту (порівняйте з рис. 7.4).

Переміщення з точки х kу точку супроводжується зростанням функції f(x) на величину

З виразу (7.30) видно, що збільшення є функцією змінної , тобто . При знаходженні максимуму функції f(x) у напрямку градієнта ) необхідно вибирати крок переміщення (множник ), що забезпечує найбільше зростання збільшення функції, саме функції . Величина, при якій досягається найбільше значення, може бути визначена з необхідної умови екстремуму функції:

(7.31)

Знайдемо вираз для похідної, диференціюючи рівність (7.30) як складну функцію:

Підставляючи цей результат у рівність (7.31), отримуємо

Ця рівність має просте геометричне тлумачення: градієнт у черговій точці х до+ 1 ортогональний градієнту в попередній точці х до.

побудовані лінії рівня цієї поверхні. З цією метою рівняння наведено до виду ( x 1 -1) 2 + (x 2 -2) 2 = 5-0,5 f, З якого ясно, що лініями перетину параболоїда з площинами, паралельними площині x 1 Про x 2 (лініями рівня), є кола радіусом . При f=-150, -100, -50 їх радіуси рівні відповідно , а загальний центр знаходиться у точці (1; 2). Знаходимо градієнт цієї функції:

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(х) у задачі з обмеженнями має єдиний екстремум і він знаходиться всередині допустимої області, то для пошуку екстремальної точки х* застосовується викладена вище методика без будь-яких змін.

Розглянемо задачу опуклого програмування з лінійними обмеженнями:

(7.34)

Передбачається, що f(х) є увігнутою функцією і має безперервні приватні похідні у кожній точці допустимої області.

Почнемо з геометричної ілюстрації процесу розв'язання задачі (рис. 7.7). Нехай початкова точка х 0 розташована всередині припустимої області. З точки х 0 можна рухатися в напрямку градієнта , поки f(x) не досягне максимуму. У нашому випадку f(x) весь час зростає, тому зупинитися треба в точці х, на граничній прямій. Як видно з малюнка, далі рухатися у напрямку градієнта не можна, оскільки вийдемо з допустимої області. Тому треба знайти інший напрямок переміщення, який, з одного боку, не виводить із допустимої області, а з іншого – забезпечує найбільше зростання f(x). Такий напрямок визначить вектор , що становить найменший вектор гострий кутв порівнянні з будь-яким іншим вектором, що виходить з точки x iі лежать у допустимій області. Аналітично такий вектор знайдеться за умови максимізації скалярного твору . В даному випадку вектор, що вказує найвигідніший напрямок, збігається з граничною прямою.

Таким чином, на наступному кроці рухатися треба по граничній прямій доти, доки зростає f(x); у нашому випадку - до точки х 2 . З малюнка видно, що далі слід переміщатися у напрямку вектора , що з умови максимізації скалярного твору , Т. е. по граничній прямий. Рух закінчується у точці х 3 оскільки в цій точці завершується оптимізаційний пошук, бо в ній функція f(х) має локальний максимум. Через увігнутість у цій точці f(х) Досягає також глобального максимуму в допустимій області. Градієнт у точці максимуму х 3 =х* Складає тупий кут з будь-яким вектором з допустимої області, що проходить через х 3тому скалярний твірбуде негативним для будь-якого допустимого r kкрім r 3 , спрямованого по граничній прямій. Для нього скалярний добуток =0, так як і взаємно перпендикулярні (гранична пряма стосується лінії рівня поверхні f(х), що проходить через точку максимуму х*). Ця рівність і є аналітичною ознакою того, що в точці х 3 функція f(x) досягла максимуму.

Розглянемо тепер аналітичне розв'язання задачі (7.33) – (7.35). Якщо оптимізаційний пошук починається з точки, що лежить у допустимій області (всі обмеження задачі виконуються як суворі нерівності), то переміщатися слід у напрямку градієнта так, як встановлено вище. Однак тепер вибір λ kу рівнянні (7.29) ускладнюється вимогою, щоб чергова точка залишалася у допустимій області. Це означає, що її координати повинні відповідати обмеженням (7.34), (7.35), тобто повинні виконуватися нерівності:

(7.36)

Вирішуючи систему лінійних нерівностей(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 *для наступної точки пошукової траєкторії. При цьому використовується необхідна умоваекстремуму у формі, аналогічній рівнянню (7.32), але із заміною на вектор , тобто.

(7.41)

Оптимізаційний пошук припиняється, коли досягнуто точки 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 розташовується тільки на одній (першій) граничній прямій ( i=1) x 1 +4x 2 = 14, то умова (7.38) записується у формі рівності.

Система обмежувальних рівнянь цього завдання має лише два рішення (-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)

(7.42)

необхідно знайти значення параметра , у якому функція f(x) у точці x

звідки =2,0618. У цьому =-0,3999<0. Значит,=2,0618. По формуле (7.42) находим координаты новой точки х 1 (2; 3).

Якщо продовжити оптимізаційний пошук, то при вирішенні чергової допоміжної задачі (7.37)-(7.40) буде встановлено, що Т 1 = , а це свідчить, що точка x 1 є точкою максимуму х* цільової функції у допустимій області. Це видно і з малюнка в точці x 1 одна з ліній рівня стосується межі допустимої області. Отже, точка х 1 є точкою максимуму х*. При цьому f max = f(x*)=5,4.

Завдання із нелінійними обмеженнями. Якщо в завданнях з лінійними обмеженнями рух по граничним прямим виявляється можливим і навіть доцільним, то при нелінійних обмеженнях, що визначають опуклу область, будь-яке як завгодно мале переміщення з граничної точки може відразу вивести за межі області допустимих рішень, і виникне необхідність повернення в допустиму область (Мал. 7.9). Подібна ситуація характерна для завдань, у яких екстремум функції f(x) досягається на межі області. У зв'язку з цим застосовуються різні

способи переміщення, що забезпечують побудову послідовності точок, розташованих поблизу кордону і всередині допустимої області, або зигзагоподібний рух уздовж кордону з перетином останньої. Як видно з малюнка, повернення з точки x 1 у допустиму область слід здійснювати вздовж градієнта тієї граничної функції, яка виявилася порушеною. Це забезпечить відхилення чергової точки х2 у бік точки екстремуму х*. Ознакою екстремуму у разі буде коллинеарность векторів і .

1. Концепція градієнтних методів.Необхідною умовою існування екстремуму безперервної функції, що диференціюється, є умови виду

де – аргументи функції. Більш компактно цю умову можна записати у формі

(2.4.1)

де - Позначення градієнта функції в заданій точці.

Методи оптимізації, які використовують щодо екстремуму цільової функції градієнт, називаються градієнтними.Їх широко застосовують у системах оптимального адаптивного управління станами, що встановилися, в яких проводиться пошук оптимального (в сенсі обраного критерію) стану системи, що встановився, при зміні її параметрів, структури або зовнішніх впливів.

Рівняння (2.4.1) у випадку нелінійно. Безпосереднє рішення його або неможливе, або дуже складно. Знаходження рішень такого роду рівнянь можливе шляхом організації спеціальної процедури пошуку точки екстремуму, заснованої на використанні різноманітних рекурентних формул.

Процедура пошуку будується у формі багатокрокового процесу, при якому кожен наступний крок призводить до збільшення або зменшення цільової функції, тобто виконуються умови у разі пошуку максимуму та мінімуму відповідно:

Через nі n- 1 позначені номери кроків, а через і – вектори, що відповідають значенням аргументів цільової функції n-м і ( п- 1) кроки. Після r-го кроку можна отримати

тобто після r - кроків - цільова функція вже не буде збільшуватися (зменшуватися) при будь-якій подальшій зміні її аргументів; Останнє означає досягнення точки з координатами для якої можна написати, що

	(2.4.2)
	(2.4.3)

де - Екстремальне значення цільової функції.

Для вирішення (2.4.1) у загальному випадку може бути застосовано таку процедуру. Запишемо значення координат цільової функції як

де - Деякий коефіцієнт (скаляр), не рівний нулю.

У точці екстремуму так як

Рішення рівняння (2.4.1) у такий спосіб можливе, якщо виконується умова збіжності ітераційного процесу для будь-якого початкового значення.

Методи визначення, засновані на вирішенні рівняння (2.2.), відрізняються один від одного вибором, тобто вибором кроку зміни цільової функції у процесі пошуку екстремуму. Цей крок може бути постійним або змінним У другому випадку закон зміни значення кроку, у свою чергу, може бути заздалегідь визначений. залежатиме від поточного значення (може бути нелінійним).

2. Метод якнайшвидшого спуску.Ідея методу якнайшвидшого спуску у тому, що пошук екстремуму має здійснюватися у бік найбільшого зміни градієнта чи антиградієнта, оскільки це шлях – найкоротший досягнення екстремальної точки. За його реалізації, насамперед, необхідно обчислити градієнт у цій точці і вибрати значення кроку.

Обчислення градієнта.Так як в результаті оптимізації знаходяться координати точки екстремуму, для яких справедливе співвідношення:

то обчислювальну процедуру визначення градієнта можна замінити процедурою визначення складових градієнтів у дискретних точках простору цільової функції

	(2.4.5)

де – мала зміна координати

Якщо припустити, що точка визначення градієнта знаходиться посередині

відрізка то

Вибір (2.4.5) або (2.4.6) залежить від крутості функції на ділянці - Ах; якщо крутість не велика, перевагу слід віддати (2.4.5), оскільки обчислень тут менше; в іншому випадку більш точні результати дає обчислення (2.4.4). Підвищення точності визначення градієнта можливо за рахунок усереднення випадкових відхилень.

Вибір значення крокуСкладність вибору значення кроку у тому, що напрям градієнта може змінюватися від точки до точки. При цьому занадто великий крок призведе до відхилення від оптимальної траєкторії, тобто від напрямку по градієнту або антиградієнту, а дуже малий крок - до дуже повільного руху до екстремуму за рахунок необхідності виконання великого обсягу обчислень.

Одним із можливих методів оцінки значення кроку є метод Ньютона – Рафсона. Розглянемо його на прикладі одновимірного випадку у припущенні, що екстремум досягається в точці, яка визначається рішенням рівняння (рис.2.4.2).

Нехай пошук починається з точки причому в околицях цієї точки функція розкладається в ряд Тейлора. Тоді

Напрямок градієнта у точці збігається з напрямом дотичної. При пошуку мінімальної екстремальної точки зміна координати хпри русі градієнтом можна записати у вигляді:

Рис.2.4.2 Схема обчислення кроку методом Ньютона – Рафсона.

Підставивши (2.4.7) у (2.4.8), отримаємо:

Так як за умовою даного прикладу значення досягається в точці, що визначається рішенням рівняння, то можна спробувати зробити такий крок, щоб тобто щоб

Підставимо нове значення у цільову функцію. Якщо то в точці процедура визначення повторюється, у результаті знаходиться значення:

і т.д. обчислення припиняється, якщо зміни цільової функції малі, тобто.

де – допустима похибка визначення цільової функції.

Оптимальний метод градієнта.Ідея цього методу полягає в наступному. У звичайному методі якнайшвидшого спуску крок вибирається у випадку [коли ] довільно, керуючись лише тим, що він повинен перевищувати певного значення. В оптимальному градієнтному методі значення кроку вибирається виходячи з вимоги, що з даної точки в напрямку градієнта (антиградієнта) слід рухатися доти, доки цільова функція буде збільшуватися (зменшуватися). Якщо ця вимога не виконується, необхідно припинити рух і визначити новий напрямок руху (напрямок градієнта) і т. д. (до знаходження оптимальної точки).

Таким чином, оптимальні значення для пошуку мінімуму і максимуму відповідно визначаються з вирішення рівнянь:

В (1) та (2) відповідно

Отже визначення на кожному кроці полягає в знаходженні рівнянь (1) або (2) для кожної точки траєкторії руху вздовж градієнта, починаючи з вихідної.