епорожньо, так як a=0, u=0 є допустимим планом. Значить, допоміжна завдання має рішення (ak, uk), причому uk $ 0. Якщо uk> 0, то неважко показати, що напрямок ak є можливим напрямом зростання функції f (x), тобто точка xk + 1=xk + akak при досить малому ak належить безлічі Х і забезпечує більше значення функції f (x), ніж хk. Вибір пари (аk, uk) з можливо великим значенням uk при цьому означає вибір допустимого напрямки, найбільш близького до градієнту функції, тобто можливого напрямку з найбільшим зростанням функції. Якщо uk=0, то виходить стаціонарна точка процесу, яка для завдання опуклого програмування дає рішення, а в загальному випадку вимагає доповнитьЄльня дослідження.
Методи множників Лагранжа
Ця група методів заснована на зведенні рішення задачі математичного програмування до знаходження сідлової точки функції Лагранжа. Методи множників Лагранжа являють собою різні процедури пошуку сідлової точки. В якості такої процедури можна взяти, наприклад, ітеративний процес як у методі проекції градієнта, застосувавши його для підйому по змінної х і спуску по змінній y. Отримаємо процес
(x)=(g1 (x), _, gm (x)), Y={y | y $ 0}.
Проекція на безліч Y визначається досить просто:
(y)=(Z1, _, Zm), Zi=max (yi, 0), i=1, 2, _, m.
Якщо R - ненегативний ортант, то проекція на нього визначається аналогічним чином.
Методи другого порядку
До цих пір ми розглядали методи першого порядку, тобто методи пошуку екстремуму, що використовують першу похідні. Фактично в цих методах проводиться лінеаризація, пов'язана із заміною максімізіруемой функції f (x) лінійним членом розкладання її в ряд Тейлора. Але якщо функція двічі безперервно дифференцируема, то можна використовувати для її аппроксімізаціі два члени ряду Тейлора. Використання такої аппроксімізаціі в итеративном процесі може підвищити швидкість збіжності.
Найбільш відомим з методів другого порядку є метод Ньютона, який полягає в наступному. На k-й ітерації, маючи наближення хk, ставимо допоміжну завдання максимізації функції
(x)=б f 1 (xk), x - xk з + 0,5 б f" (xk) (x - xk), x - xk з
на безлічі Х. Нехай тоді наступне наближення будується за формулою Крок ak можна вибирати різними способами, зокрема можна покласти ak=1, тоді як наступного наближення приймається просто рішення допоміжної задачі, тобто.
Для завдання без обмежень, коли Х=R n, метод Ньютона істотно спрощується. Дійсно, в цьому випадку тобто
Значить, для знаходження треба вирішити систему лінійних рівнянь (14). Якщо матриця f" (xk) НЕ виродилися, то маємо просто (при ak=1)
Перевагою методу Ньютона є висока швидкість збіжності, яка з лишком компенсує ускладнення обчислень на кожній ітерації. Недоліком методу є те, що він сходиться при досить жорстких припущеннях.
Методи штрафних функцій
Як видно з попередніх розглядів, наявність обмежень істотно ускладнює завдання пошуку екстремуму функції. Майже всі викладені методи вирішення екстремальних задач включали спеціальні складні процедури, що враховують наявність обмежень (наприклад, проектування). У цьому сенсі в особливу групу виділялися методи ...
