4.5. Метод умовного градієнта

Цей метод застосовується для розв'язання задачі

3(и)^>М;   иєі/, (4.48)

де ІЗ - випукла замкнута, обмежена множина з Еп, функція 3(и)^С\и).

Нехай      є ІЗ - деяке початкове наближення.   Якщо відоме к-е наближення     є ІЗ (к £ 0), то приріст функції 3(и) в точці можна представити у вигляді

3(и)-3(ик) = (3'(ик),и-ик)+0(\и-ик\).

Візьмемо головну лінійну частину цього прирощення

Зк{и)={3\ик),и-щ)і (4.49)

і визначимо допоміжне наближення «* з умов

«* є и, МЗк(и) = Зк(ик) = (3\ик),ик-щ). (4.50)

Оскільки множина замкнута і обмежена, а лінійна функція

Зк(и) неперервна, то точка «* з (4.50) завжди існує. Якщо таких

точок кілька, оберемо будь-яку з них.

Відзначимо випадки, коли розв'язання задачі (4.50) записується в явному вигляді. Якщо

ІЗ = ^і = (и1 ,...,и"):аі <и' <Д, / = 1,...,л|- и-вимірний паралелепіпед, то функція

1=1

або

і=і

очевидно, досягає своєї нижньої грані на ІЗ в точці

— —1        —п

Иі =(Иі,...,Иі),

де

Л'("*)>0' "* ]д, Л'К)<°;

у випадку 3и,(ик) = 0, виникає невизначеність і в якості и* можна взяти будь-яке число з відрізка [а(, Д ] (зазвичай беруть и* = а(, або Иі = Д, або и'і =(а( + Д)/2. Якщо (7 = {и е 2?я : |и-у0| < г} - куля

радіусу г з центром в точці у0 , то за допомогою нерівності Коші-Буняковського

{ЗХик),и} = {3'(ик),и-г0} + {ЗХик),у»)>

НЛ«*)к+(Ли*и), и^и,

маємо іік = у0 -гЗХщ)\3\щ)\ \

Зрозуміло, що так просто одержати наближення и* вдається далеко не завжди, і замість точного розв'язку задачі (4.50) часто задовольняються визначенням деякого наближеного розв'язку. Будемо припускати, що він визначається з наступних умов:

Припустимо, що точка «*, яка задовольняє умовам (4.51) вже відома. Тоді наступне (к +1) — е наближення будемо шукати у вигляді

В силу випуклості множини І/ завжди щ+1 е 17.

Відзначимо, що для «* — ик (це може статися, наприклад, коли ,/'("*) = 0) маємо икл1=щ незалежно від способу вибору ак в (4.52). Якщо при цьому и* була визначена з умови (4.50), то маємо

всіх иє17.

А це означає, що точка ик задовольняє необхідній умові мінімуму в задачі (4.48). В цьому випадку ітерації завершуються.

Способи вибору крокового множника ак аналогічні способам вибору кроку в градієнтному методі.

 

(4.51)

(4.52)

 

для