подолати, наприклад, якщо одержувану за формулою (10) чергову точку проектувати на безліч Х. Якщо позначити операцію проектування х на безліч Х через Рх (х), то відповідний ітеративний процес має вигляд
хk + 1=Рх (хk + ak f 1 (хk))
Отриманий метод носить назву методу проекції градієнта. Крок ak в методі (12) може вибиратися різними способами (наприклад, як у методі якнайшвидшого підйому). Стаціонарна точка цього процесу є рішенням задачі (4) у разі увігнутою функції f (x), а в загальному випадку потрібне додаткове дослідження.
Недоліком методу проекції градієнта є необхідність проведення операції проектування, яка в загальному випадку еквівалентна деякій задачі пошуку екстремуму. Однак, коли Х є кулею, параллелепипедом, гиперплоскостью, півпростором або ортантом, задача проектування вирішується просто і в явному вигляді.
Ще одним різновидом градієнтних методів є метод умовного градієнта, який також призначений для вирішення екстремальних задач з обмеженнями. Суть його полягає у вирішенні допоміжної задачі максимізації на безлічі Х лінійної функції б f 1 (xk), x - xk с, що представляє собою головну частину приросту функції f (x) у точці хk. Ця допоміжна завдання може бути непростим, але якщо Х задається лінійними обмеженнями, то вона являє собою задачу лінійного програмування, яка вирішується за кінцеве число кроків стандартними методами (наприклад, симплекс-методом). Якщо рішення допоміжної задачі знайдено, то наступне наближення для вихідної задачі будується за формулою
Якщо безліч Х опукле, то хk + 1 k Х. Крок ak вибирається з умови максимального зростання функції f (x) або будь-яким іншим способом, що забезпечує зростання f (x). На практиці зазвичай вирішують допоміжну завдання не точно, а наближено. У процесі (13) напрямок руху не збігається з градієнтом функції f (x) у точці хk, але визначається ним, так як його компоненти беруться в якості коефіцієнтів лінійної цільової функції допоміжної задачі.
Методи можливих напрямків
Ідея методів можливих напрямків, близька до ідеї градієнтних методів для задач з обмеженнями, полягає в наступному: на кожній ітерації визначається допустиме напрямок на безлічі Х, вздовж якого функція f (x) зростає (такий напрямок називається можливим напрямком зростання функції f (x)), і по ньому вчиняється крок. Фактично в методі проекції градієнта і в методі умовного градієнта ми знаходимо такі напрямки. Однак там вихідним було визначення градієнта, а допустиме напрямок визначалося по ньому однозначно. У методах ж можливих напрямків вихідним пунктом є опис всіх допустимих напрямів і вибір з них такого, вздовж якого функція f (x) зростає і бажано якнайшвидшим чином.
Розглянемо варіант методу можливих напрямків стосовно до задачі максимізації f (x) на множині (3), де R=R n. Нехай ми маємо k-е наближення хk до вирішення цього завдання, і для побудови наступного наближення поставимо допоміжну задачу: максимізувати u при обмеженнях
б f 1 (xk), AС $ u, бg1 (xk), AС $ u, k Ik | aj | # 1, j=1, 2, _, n,
де={i | 1 # i # m, gi (xk)=0}, a=(a1, _, an).
Це завдання представляє собою завдання лінійного програмування в (n + 1)-вимірному просторі векторів (a, u). Безліч планів замкнуто, обмежена і н...
