Головна |
Розглянемо задачу максимізації функції f(х), коли обмеження на область зміни змінних хвідсутні. Пошук екстремального значення функції f(х)можна починати з будь-якого допустимого розв'язку, наприклад, з точки хk = (x1k; ...; хпk).
Градієнтом Ñf(x) функції f(х)в точці хk називається вектор, координатами якого є значення в цій точці частинних похідних першого порядку відповідної змінної, тобто
Градієнт функції в цій точці вказує напрямок найшвидшого зростання функції f (х).
Переміщення з точки хk вздовж градієнту в нову точку хk+1 відбувається по прямій, рівняння якої
. (1)
де lk-числовий параметр, від величини якого залежить довжина кроку переміщення . Величина lk, при якій досягається найбільший приріст функції, може бути визначена з необхідної умови екстремуму функції
(2)
Чергову точку хk+1 визначаємо після обчислення параметру lk(для цього підставляємо значення lkв формулу (1) на пошуковій траєкторії). В цій (хk+1) точці знову знаходимо градієнт, а рух відбувається даліпо прямійхk+2 = хk+1 + lk+1Ñf(xk+1) у напрямку нового градієнту Ñf (xk+2) до точки хk+2, в якій досягається найбільше значення функції f(х)в цьому напрямку і т. д. Розв'язування триватиме доти, поки не буде досягнута точка х*, в якій градієнт функції дорівнює нулю. В цій точці х* цільова функція f(х*) і буде набувати максимального значення.
Приклад 1. Нехай потрібно визначити точку максимуму функції , коли процес розв'язування розпочинається з точки x0 = (4;4).
Розв'язування. Знайдемо частинні похідні функції f(x)
; .
Градієнт функції в точці х0 буде
.
Перемістимось з точки х0вздовж градієнту Ñf(х0) в нову точку х1:
х1 = x0 + λ0 Ñf (х0) = (4; 4) + l0 (-6; -4) = (4 - 6 l0; 4 - 4 l0).
Градієнт функції в точці х1 дорівнює
Ñf (х1) = [2 - 2 (4 - 6l0); 4 - 2 (4 - 4l0)] = (- 6 +12l0; - 4 + 8l0).
З необхідної умови екстремуму одержуємо рівняння
, звідки = 0,5.
Оскільки , то знайдене значення х1 є точкою максимуму функції Ñf (х1).
Враховуючи = 0,5, визначимо координати точки х1 на пошуковій траєкторії
х1= (4 - 6·0,5; 4 - 4·0,5) = (1; 2)
та градієнт Ñf (х1)в цій точці х1 Ñf (х1) = (2 - 2·1; 4 - 2·2) = (0; 0).
Оскільки градієнт Ñf (x1) має нульові координати, робимо висновок про те, що х1 = (1; 2) є точкою, в якій цільова функція досягає максимального значення f(х1) = 2·1+ 4·2 - 1- 4 = 5 (в початковій точці f(x0) = - 8).
На мал. 1 наведена графічна інтерпретація даної задачі.
Мал. 1.