3.3. Градиенттік түсу әдісі. Жылдам түсу әдісі

 кеңістігінің  жиынындағы  айнымалылы функциясының минимумын анықтау есебінің қойылымы бірөлшемді функцияның минимум анықтау есебіннің қойылымынан айырмашылығы жоқ. Егер  болса, онда  функциясының шартсыз экстремумы туралы айтылды деген сөз.

 функциясының шартсыз экстремум  есебін шешу үшін  функциясының бірінші ретті туындысын есептеуге негізделген жуық әдістер кеңінен қолданылады [1], [6], [8], [12]-[15]. Мұндай әдістерді әдетте градиенттік әдістер деп атайды. Градиенттік әдістердің бірі – градиенттік түсу әдісін қарастырайық.

Айталық,  функциясы  кеңістігінде дөңес және дифференциалданатын функция болсын. Оның минимум нүктесі  анықтау қажет.

Градиенттік түсу әдісін қарастырайық[1], [12]. Әдіс бастапқы жуықтауды, яғни бірқатар  нүктесін таңдап алуды қажет етеді.  бастапқы жуықтауын таңдап алудың жалпы ережесі жоқ. Геометриялық, физикалық және басқа да бейнелеулер арқылы минимум нүктесінің орналасу облысы туарлы ақпарат бар болса, онда бастапқы жуықтау  нүктесін осы облысқа жақынырақ таңдап алады.

Бірқатар бастапқы  нүктесі таңдап алынған деп есептейміз. Онда градиенттік түсу әдісі келесі ереже бойынша  тізбегін құруға әкеледі:

         (16)

(16) формуладағы  қадам ұзындығы немесе градиенттік түсу әдісінің қадамы деп аталады.

Егер  болса, онда  қадамын  болатындай етіп таңдап алу керек.

Егер  болса, онда  - стационар нүкте. Бұл жағдайда (16) процесс тоқтатылады және қажет болған жағдайда  нүктесі  функциясының минимумы болатын немесе болмайтындығын анықтау үшін  нүктесінің маңайында функцияның сипаттамасына қосымша зерттеу жүргізіледі. Дербес жағдайда, егер  дөңес функция болса, онда стационарлық нүктедегі тиімділік критериі бойынша әрқашан минимум нүктесі болады.

(16) әдістегі  қадамын таңдап алудың әртүрлі әдістері бар.  қадамын таңдап алуға байланысты әртүрлі градиенттік түсу әдісін алуға болады. Тәжірибеде  қадамын таңдап алудың жиі кездесетін тәсілдерін келтірейік.

1) Қадамды бөлу әдісі. Тәжірибеде өте аз  қадамы, функцияның монотонды кему шарты орындалатындай етіп аңдап алынады:

, .

Бұл шарт бұзылған жағдайда  қадамын, шарт орындалғанша бөлшектейді. Одан кейін келесі итерацияны есептеуге көшеміз.

2) Жылдам түсу әдісі. Антиградиентке бағытталған

сәулесінде, бір айнымалылы ,  функция енгіземіз және

, .                   (17)

шартынан  қадамын анықтаймыз. (16) және (17) формулалар жылдам түсу әдісі деп аталады.  қадамын анықтау үшін әрбір қадамда бірөлшемді минимизация есебі (17) шешіледі. Ол үшін алдыңғы тарауда қарастырылған әдістерді қолдануға болады.

(17) шартпен анықталған  шамасының бар екенің және айқын түрде жазылуы мүмкін екенің көрсеттенің мысал қарастырайық.

Мысалы, айталық келесі квадраттық функция берілсін:

,                 (18)

мұндағы А – өлшемі  болатын симметриялық теріс емес анықталған матрица; ,  – -де анықталған векторлар;  – -дегі скаляр көбейтінді.

 - дөңес функция және оның туындысы ,  формуласымен есептелінеді. Сондықтан бұл жағдайда (6) әдіс келесі түрде болады:

Сонымен, (18) түрдегі функция үшін градиенттік түсу әдісі  түріндегі сызықтық алгебралық теңдеулер жүйесін шешудің итерациялық әдісіне болып шығады.

 қадамы келесі формула бойынша анықталады

.                  (19)

Сонымен, (18) түрдегі квадраттық функция үшін жылдам түсу әдісі (16) және (19) формулалар арқылы  тізбегін құруға әкеледі.

3) Липщиц тұрақтысы бар әдіс. Айталық,  функциясы, яғни  функциясы және  градиенті кез келген  үшін Липшиц шартын қанағаттандырсын: , мұндағы  Липшиц тұрақтысы.

Егер  тұрақтысы белгілі болса, онда (16) формуладағы  үшін келесі шартты қанағаттандыратын кез келген санды алуға болады:

,

мұндағы ,  - әдіс параметрі болып табылатын оң сндар.

Дербес жағдайда, ,  болғанда, (16) формуладан  тұрақты қадамы бар әдіс аламыз. Осыдан, егер  - үлкен шама немесе өрескел қателіктер арқылы алынған болса, онда  қадамы аз шама болады және әдіс берілген функцияның минимумына ақырын жинақталатын болады.

Әдетте, градиенттік түсу әдісінің аяқталу шарты ретінде  градиентінің нөлге жақындығы, яғни келесі теңсіздіктің орындалуы алынады:

немесе

,                     (20)

мұндағы  - берілген жеткілікті аз шама. Егер қандай да бір  қадамда осы екі шарттын біреуі орындалса, онда ,  жуық теңдіктері орындалады. Онда берілген функцияның минимум нүктесі  дәлдікпен табылды деп айтады.

Мысал 1.  кеңістігінде

функциясының қадамды бөлу градиенттік түсу әдісімен минимизацияланыз. Есептеуді  болғанда тоқтату керек.

Шешуі. Бастапқы жуықтауды  және  деп алып, келесі тізбекті құрамыз:

,

Есептеулер нәтижесін 3-кестеге жазамыз

Кесте 3.

Функция мәндері

Сонымен, .

Мысал 2. Шартсыз минимизациялау есебі берілген:

.

 - нүктесі бастапқы жуықтау. Жылдам түсу әдісінің екі итерациясын жасаныз.

Шешуі. 1-қадам.  болғанда (16) формула келесі түрде болады:

.

 функциясының градиентін немесе туындысын анықтаймыз:

.

 нүктесіндегі  мәнің есептейміз:

.

 болғандағы  қадамын анықтау үшін  функциясын құрамыз:

.

 нүктесін табамыз және осыған бастапқы жуықтау  және  туындысының мәндерін қоямыз:

.

Табылған нүктені

,

функцияға қойсақ, онда

.

 функциясының дөңестігін пайдаланып,  шартынан -ді анықтаймыз: , осыдан

.

Жылдам түсу әдісі бойынша бірінші қадамды орындаймыз:

.

Бірінші жуықтау  нүктесі табылды. Әрі қарай, егер есеп шартында шешімді анықтау дәлдігі туралы айтылған болса, онда итерацияның әрбір қадамында (20) шарттағы градиент нормасын  есептеу керек болады. Сондықтан алдымен  нүктесіндегі  функциясының градиентін анықтаймыз

,

одан кейін  мәнін есептейміз:

.

2-қадам.  болғанда (16) формула келесі түрде болады

 болғандағы  қадамын анықтау үшін  функциясын құрамыз:

.

 нүктесін табамыз және осыған бірінші жуықтау  және  туындысының мәндерін қоямыз:

.

Табылған нүктені

,

функцияға қойсақ, онда

.

 функциясының дөңестігін пайдаланып,  шартынан -ді анықтаймыз: , осыдан

.

Жылдам түсу әдісі бойынша екінші қадамды орындаймыз:

.

Екінші жуықтау  нүктесі анықталыд. найдена.  нүктесіндегі  функциясының градиентін анықтаймыз

,

одан кейін  мәнін есептейміз:

.

Әрбір қадамдағы мәндердің азаюы, әдістің берілген функцияның минимумына жинақталады деген қорытынды тұжырым жасауға мүмкіндік береді. Яғни бастапқы жықтау  нүктесі дұрыс таңдап алынған, яғни  функциясының минимумына өте жақын орналасқан.