Метод проекції градієнта.

Розглянемо задачу мінімізації функції , для випадку, коли . Безпосередньо застосувати градієнтний метод неможливо, оскільки при деякому n точка може не належати U. Однак цього легко уникнути, якщо кожний одержаний член послідовності (3.1) проектувати на множину U. В результаті ми прийдемо до методу проекції градієнту.

Для описання цього методу нам будуть потрібні додаткові відомо­сті.

Означення 1. Проекцією точки на множину називається точка , що задовольняє умову

де - відстань від точки u, до множини U.

Якщо u єU, то очевидно, що Неважко на­вести приклади множин U, коли проекція точки на множину не існує або визначається неєдиним чином. Наступну теорему сформулю­ємо без доведення.

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

при будь яких

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

де . Існують різні способи вибору величини у рівності, і в залежності від цього можна одержати різні ва­ріанти методу проекції градієнта. Зокрема, можна вибирати з умов

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

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