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

Розглянемо задачу

У(и) -» М ; « є 17 с Еп, (4.44)

де множина І/ не обов'язково співпадає з усім простором Еп, а

функція Ли)єС1(У).

Безпосереднє застосування градієнтного методу у випадку IIФЕП може призвести до ускладнень, оскільки точка щ+1 придеякому к може і не належати до ІЗ. Але це ускладнення легко усувається, якщо кожну одержану точку     - акТ (ик ) для кожного к

проектувати на множину ІЗ. В результаті одержимо метод проекції градієнта.

Нехай и0^1/ - деяке початкове наближення. Далі будемо будувати послідовність {ик } за правилом

иш = Ри(ик-ак3\ик)),   к = 1,2,..., (4.45)

де ак - додатній кроковий множник. Якщо ІЗ  - випукла

замкнута множина і спосіб вибору  {ак}  в (4.45) заданий, то

послідовність   {иі}буде  однозначно визначатися умовою (4.45).

Зокрема коли II = Е" метод (4.45) перетворюються в градієнтний метод.

Якщо в (4.45) на деякій ітерації виявилось ик+1 = ик (це може статися коли 3(иі) = 0), то процес (4.45) завершують. В цьому випадку точка ик задовольняє необхідний умові оптимальності, і для з'ясування того, чи дійсно ик є розв'язком задачі (1) треба провести додаткові дослідження. Зокрема, якщо 3{и) - випукла функція, то така точка ик є розв'язком задачі (1).

Кроковий множник можна вибирати за тими ж правилами, що і у звичайному градієнтному методі. Методом проекції градієнта звичайно користуються лише в тих випадках, коли проекція точки на множину легко визначається. Наприклад, коли множина С/ є кулею в Еп, паралелепіпедом, гіперплощиною, на півпростором або додатнім

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

Розглянемо випадок сильно випуклою функції, вважаючи, що в методі (4.45) ак являється сталою.

Теорема. Нехай ІЗ - випукла замкнена множина, функція 3(и) є С1'1 (£/) і сильно випукла на ІЗ . Нехай 0 < а < 2[й32, де // -стала випуклості ( тобто така стала, що випуклою на ІЗ є функція 3(и) + /ф/|2), Ь- стала Ліпшиця. Тоді послідовність {ик}, яка одержана за допомогою (4.45) при сек=а (й=1,2,...) , сходиться до точки мінімуму и,, причому справедлива оцінка

\щ -и,| <|и0 -и.\(д(а)У,  к = 1,2,... (4.46)

де д(а) = (1 - 2ца+а2її )1/2,  0 < д(а) < 1. Доведення.

Введемо відображення

^м=Р[;(и-аі/'(»))

що діє з ІЗ в ІЗ. Покажемо, що воно є стискаючим при 0 < а < 2рЬ~2. Маємо

\Аи - Ау\2 = \Ри (и -аЗ'(и)) -Ри (V-ск/'(у))|2 <

й \и - аГ (и) - V - о/Чу)|2 = \и - у|2 + а2^") - У (у)|2 --2{/'(и)-У,(^),и-У><|и-у|2(1-2^а+а2/,2) = ?(а)|и-у|2 Тобто

|Ли-Лу|2 =^(а)|и-у|2,  и,ує(У. (4.47)

Так як 0 < а < 2іц£~2, то 0 < #(«) < 1. Це означає, що відображення є стискаючим. Відзначимо також, що замкнута множина ІЗ а Еп   являє  собою  повний  метричний  простір з метрикою

р(и, v) = |« — у|. А це дає змогу скористатися принципом стискаючих

відображень. Метод (4.45) при ак=а являється відомим процесомпошуку нерухомої точки и, стискаючого відображення А, для якої и, = Лм,. Відомо, що така точка «, існує, єдина і ІікАщ -«,1=0.

к—кс' '

З (4.47) випливає, що

\щ-к\^о-К-кНа^' Ут>к. Звідси при т —> со одержимо оцінку (3). Так як и. =Ри (и,-аЗу («,))> то «, точка мінімума функції 3(и) на множині ІЗ . Теорема доведена.