Тема: Чисельні методи безумовної мінімізації функції багатьох змінних
Розглядаються задачі безумовної оптимізації 
(1)
На сьогоднішній день розроблено та досліджено велика кількість методів безумовної мінімізації функції багатьох змінних. І ця область екстремальних задач продовжує зростати.
Буде розглянуто:
1) З методів «0» порядку – метод координатного спуску;
2) З методів «1» порядку – градієнтний метод;
3) З методів «2» порядку метод Ньютона.
Методи 1-го та 2-го порядку явним чином засновані на ідеї заміни мінімізації функції в області чергової точки xk, першими членами її розкладу для Тейлора.
В градієнтному методі береться лінійна частина розкладення.
В методі Ньютона - квадратична частина – це ідея апроксимації функції.
Загальна схема ітераційних методів для рішення задач безумовної мінімізації функції.
(1)
βk – напрямок зменшення функції 
множина напрямків зменшення функції 
, тобто 
- параметр регулюючої довжину кроку вздовж βk.
Методи монотонного спуску – коли:
(*) називаються релаксаційними.
Якщо функція 
диференційована в точці 
, то релаксаційність методу (*), тоді коли напрямок 
утворює не тупий кут з напрямком градієнта 
Розглянемо основні властивості градієнту функції в т. 
Нехай функція диференційована в т. 
, і нехай в цій точці 
, найбільшого зростання функції в цій точці співпадає з напрямком градієнту в даній точці, а напрямок антиградієнту 
Доведення: з диференційованості в точці слідує, що
(3)
Якщо тоді при достатньо малих головна лінійна частина приросту (3) буде визначатися диференціалом функції:
Справедлива нерівність:
(3)
Причому, якщо: тоді права нерівність перетвориться в рівність, лише при
З цього слідує, що при напрямок найшвидшого приросту функції в точці співпадає з напрямком градієнта , а напрямок найшвидшого спадання – з напрямком антиградієнта –
Умови зупинки ітераційного процесу (критерій закінчення рахунку)
На практиці часто застосовують наступні умови зупинки:
(4)
(5)
(6)
Ці умови ґрунтуються на понятті абсолютної похибки.
До початку обчислень прибирається одна з умов (4-6) и відновідну їй мале додатне число 
.
Обчислення закінчуються після 
кроку, якщо вперши виконується умова зупинки.
На практиці критерій, що складається в одночасному виконанні двох із умов (4-6) або всіх трьох одразу.
Критерій (6) – відноситься лише до задачі безумовної оптимізації. Його виконання означає, що в точці 
з точністю до 
виконується умова стаціонарності.
Замість критеріїв (4-6) заснованих на поняттях абсолютної похибки, можна використати критерій заснований на понятті відносної похибки:
Метод координатного спуску
В практичних задача оптимізації нерідко зустрічаються випадки, коли мінімізуюча функція або не володіє необхідною гладкістю, або є гладкою.
Проте обчислення її похідних з необхідною точністю потребує надто великого об’єму роботи, в таких випадках можуть бути корисними методи нульового порядку – методи, які не потребують обчислення змінних.
Одним з них є метод координатного спуску(МКС).
Опис методу
Позначимо
В МКС в якості напряму спуску 
використовується один з координатних векторів:
(нульовий вектор, і лише і-й елемент – одиниця)
Отже в точці 
зміниться лише одна з компонент.
В схемі метода розрізняють внутрішні та зовнішні ітерації.
Нехай 
- деяке початкове наближення.
- деяке вагоме число
- застосовується для факту позначення
Тоді по методу координатного спуску для k=1
(7)
позначимо через 
(першої ітерації).
За формулами (7) буде здійснено спуск за n (розмірність 
) внутрішніх ітерацій з точки 
в точку 
по ломаній, що складається з відрізків та прямих паралельних осям координат.
Рис. Одна зовнішня ітерація МПКС для n=2
Спуск за всіма n координатами по функціям (7) складає одну зовнішню першу ітерацію.
Друга зовнішня ітерація здійснюється за формулами:
k=2
І так далі.
Нехай:
k – номер чергової зовнішньої ітерації;
і – номер і-координати за котрою відбувається спуск(тобто номер внутрішньої ітерації)
Тоді ітераційна рекурентна формула, яка визначає наступне наближення до точки мінімуму, матиме вид:
; 
(8)
Після i=n лічильник числа зовнішніх операцій k збільшується на 1, а i=1. Ітераційний процес (8) буде продовжуватися до тих пір, доки:
Існують різноманітні способи вибору
. Основна задача при виборі в релаксаційних процесах – мінімізація, щоб забезпечити виконання нерівності:
Розглянемо деякі способи вибору параметру в МПКС.
Спосіб 1: вибір параметру з умови мінімізації функції вздовж напряму
(9)
Спосіб 2: нехай 
, обчислимо значення функції в точці 
, тоді
(10)
Якщо нерівність (10) виконується, то або приймемо, що 
,
та перейдемо до наступної k+2 ітерації, або оберемо 
, якщо значення 
менше його минулого значення, то процес подвоєння можна продовжувати до тих пір, доки зменшення не зупиниться, тобто буде виконуватись нерівність (10).
В тому випадку, якщо нерівність (10) не виконується, то обчислимо значення функції в точці 
та перевіримо нерівність
(11)
В випадку виконання задачі (11), або приймемо
,
або оберемо, як в минулому випадку , доки виконується нерівність(11).
Назвемо ітерацію k+1 успішною, якщо справедливо хоча б одне з нерівностей (10)-(11).
Якщо за одну зовнішню ітерацію, яка складається з n – внутрішніх з вибором усіх координатних осей Е1 та Еn, з кроком αk реалізувалась хоча б одна успішна ітерація, то довжина кроку αk не ділиться і зберігається на протязі усього циклу з n – ітерацій.
Якщо серед останніх n - ітерацій не виявилось ні одної успішної, тоді крок αk ділиться на 
і переходить до наступного циклу.
Найпростіший варіант цього методу
На початку пошуку задаються дві точки: 
і 
, з яких проводиться спуск, за допомогою будь-якого варіанту градієнтного методу. І отримують дві точки: х0 та х1. Потім отримують:
,
де h – додатна константа, яка називається часовим кроком.
З точки 
, краї, загалом знаходяться на «схилі оврагу» проводить спуск за допомогою градієнтного методу та визначають наступну точку х2 на «дні оврагу».
А якщо з відомих точок (х0, х1,…,х k), k>2, тоді
Здійснюючи спуск за допомогою градієнтного методу, знаходимо наступну точку х k+1 на «дні оврагу».
х2 х1 х0
х3 
Величина кроку h підбирається емпірично з урахуванням інформації про мінімізуючи функцію, яку отримали у ході пошуку мінімуму.
Від правильного вибору h залежить швидкість сходження методу, якщо крок h – великий, то на крутих поворотах оврага точки 
можуть занадто віддалятися від дна оврага. І спуск з точки у точку х k може вимагати більшої кількості розрахунків, крім того при великих h на крутих поворотах може відбутися вибір точки з оврагу і правильний напрям нової точки мінімуму буде втрачено.
Якщо крок h занадто малий, то пошук може дуже вповільнитись і ефект від застосування овражного методу може бути незначним.