Градиенттік құлдилау әдістері

Градиенттік құлдилау әдістері.

 

Табиғатта минимум табу есебіне ұқсас, әртүрлі құбылысты байқауға

болады. Мысалы, котлованның  жағалауынан түбіне судын ағуы .Котлован

жағасы, ойысы, дөңесі, қырлары жоқ тегіс дейік. Онда су әрбір нүктеде

жағалаудың ең үлкен айналма бағытымен төмен қарай жылжиды. Ең тез

құлдилау бағыты функцияның ең көп кему бағытына сәйкес келетінін білеміз.

Математикалық анализ кусынан белгілі: қандайда бір нүктесінде f(x) скаляр

функцияның градиенті  функция өсу жағына қарай бағытталған және деңгей

сызықтарына ортогональды (деңгей сызықтары дегеніміз  нүктесі арқылы

өтетін f(x) функциясының тұрақты мәнінің беттері). Ендеше, біз функцияның

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

Градиентке қарама – қарсы  вектор антиградиент -f’(xк)-ны, яғни f(x)

функциясының ең тез кему жағына қарай бағытталған векторды қарастырамыз, сондықтан құлдилау әдісінде хк нүктесінен осы бағытпен қозғаламыз. Қозғалыс бағыты антиградиентпен сәйкес келетін немесе құлдилау әдісіндегі жалпы формулада Sк = f '(xк ) болса, онда әдіс градиенттік құлдилау әдісі деп аталады. хк нүктесіндегі f(x) функциясының антигредиеттін Sк құлдилау бағыты ретінде таңдап ала отырып,

 

(3)

 

түріндегі итерациялық процесске келеміз. Мұндағы,

Бұл процесс координаттық формада былай жазылады:

 

            (4)

 

қадамды таңдаудың бірнеше жолы бар, соның ішінде ең көп тарағаны екі

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

 

  (5)

 

теңсіздігі орындалады, бірақ бұл дегеніміз қажетті минимум нүктесіне жету

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

Осыны қарапайым мысалмен түсіндіре кетейік.

1-мысал. f(x)= →min есебін шешейік, мұндағы a – қандай да бір оң сан.

 

      

 

 

 

 

 

- тұрақты болса,  онда процесс жинақталады, егер  ;

     үшін, процесс жинақсыз.

Егер     деп алсақ, онда х1=-х0 , х2=х0 , х3=-х0, т.с.с.

Процесс жинақсыз, бірақ  бұл кезде аргументтің мәні, ендеше

функцияның да мәні қайталанады.

Мұндай түрдегі жинақталмауды  қайталану (зацикливание) деп атайды.

Градиенттік құлдилау әдісінде қадамды бөлуде к a шамасы мына теңсіздік

орындалатындай етіп таңдалынады:

 

           (6)

 

мұндағы 0<ε<1 – еркін таңдап алынған тұрақты (барлық итерация үшін бірдей). Бұл шарт алдыңғы (5) шартқа қарағанда қадам таңдауда қатаң қойылған, бірақ екеуінің мағынасы бірдей: итерациядан итерацияға функция кеміп отыруы керек. (1) процессте қадамды (6) теңсіздікті қанағаттандыратындай етіп таңдасақ, онда процесс былай жүреді:

• барлық итерация үшін α>0 санын бірдей етіп таңдаймыз.
• к-шы итерацияда (6) теңсіздіктің орындалуын αк=α болғанда

тексереміз.

Егер орындалса, αк=α деп алып, келесі итерацияға өтеміз. Егер

орындалмаса, онда αк қадамды теңсіздік орындалмайынша бөле береміз.

Градиенттік құлдилау әдісінің геометриялық мағынасы: 10-суретте

көрсетілген:

Х* нүктесінде минимумы бар f(x) функциясының деңгей сызықтары

көрсетілген.

 

 

 

 сынықтары деңгей сызықтарына ортогональ.

 

 

Кез-келген қандай да бір бастапқы нүктені таңдап аламыз. Осы нүктеде

қарастырып отырған функцияның градиентін есептейміз. Градиентке қарсы

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

Енді әрі қарай жаңа алынған нүктеде процедураны қайталаймыз:

функцияның градиентін осы нүктеде есептейміз, сосын қарама-қарсы бағытта

қадам жасаймыз. Осылай есептеу процесін жүргізе береміз. Процесті мақсат

функциясының ең кіші мәнін алғанша жүргіземіз.

Егер қарастырып отырған  облыс ішінде функция минимумына жетсе,

онда бұл нүктеде градиент нөлге тең және бұл да оптимизациялау процесінің

аяқталғанын көрсетеді. Градиенттік құлдилау әдісінде құлдилау

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

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

етпейтіндей етіп азайту дұрыс. Бұл градиенттік әдістің модификациясында тез құлдилау әдісі қарастырылады.

 

 

Тез құлдилау әдісі және оның алгоритмі.

 

Алдында қарастырғандай итерациядан  итерацияға f(x) функциясының

кемуін қамтамасыз ететін барлық итерация үшін қандай да бір тұрақты қадам

шамасын таңдауға болады екен. Бірақ бұл кезде қадам өте аз болады, яғни

минимум нүктесінде жету үшін көп итерация жүргізу қажет деген сөз. Екінші

жағынан, әрбір қадамда мақсат функциясының градиентін есептеу процессті

жай жүргізуге әкеледі. Себебі, градиентті есептеу функциясының өз мәнін

есептеуге қарағанда күрделі операция. Сондықтан айнымалы қадамды

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

антиградиент бағытында аз қадам жасамай, керісінше функция кемімейінше

қозғала береміз. Алынған бағытта минимум нүктесіне жетіп, қайтадан

функцияның градиентін есептейміз және т.с.с. Яғни есептеу процесін дәл

алдындағыдай жүргізе береміз. Бұл кезде градиент тек қозғалу бағытын

өзгерткенде ғана есептелінеді. Тез құлдилау әдісінде әрбір итерацияда

қадамы қозғалыс бағытына қарай бағытталған f(x) функциясының минимум

шартынан алынады:

 

   

 

Бұл әдісте әрбір итерацияда бірөлшемді минимизация есебін шығаруға

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

 

      f(x)=C2

     f(x)=C3

   C1>C2>C3

Бұл әдістің градиенттік құлдилау әдісінен айырмашылығы хк нүктесінен қозғалыс бағыты хк+1 нүктесіндегі сызық деңгейін жанап өтеді. х0, х1, х2,...,хк, ... нүктелер тізбегі ирек қозғалыс (зигзаг) түрінде х* нүктесіне жақындайды және бұл иректер өзара перпендикуляр.

Негізінен, қадам функцияны бойынша минимумдау шартынан

алынады.

 

 

cондықтан                         

 

    Сонымен, екі бірдей итерацияда құлдилау бағыты өзара ортогональ.

 

Тез құлдилау әдісі әрбір қадамда бірөлшемді минимизация (7) есебін

шешудің күрделі есептеуін береді. Сондада бұл әдіс ең тиімді қадаммен

қозғалысты қамтамасыз еткендіктен машиналық операциялар санында ұтымды болады. (7) есепті шешу f(x) функциясының өзін есептеумен байланысты, ал негізгі машина уақыты оның градиенттік f’(x) – ті есептеуге кетеді.

 

Градиенттік әдістердің жинақталуы

 

Жоғарыда қарастырылған барлық градиенттік әдістерде хк нүктелер

тізбегі f(x) функциясының стационар нүктесіне жинақталады.

Теорема 1. Егер f(x) функциясы төменнен шенелген және оның градиенті

Липшиц шартын қанағаттандырса және мәнін

жоғарыда айтылғандай жолдармен таңдасақ, онда х0 бастапқы нүктесі қандай

болғанда да, к шексіздікке ұмтылғанда болады (к→∞);

Бұл теореманың дәлелдеуін қарастырмаймыз [4].

Хк+1=хк-άк f’(xк) схемасын практикада жүзеге асырғанда, егер барлық і үшін

(і=1,2,...n)     шарты орындалатын болса, онда итерацияны  тоқтатамыз.

Мұндағы, δ - минимум табу дәлдігін сипаттайтын, қандай да берілген

сан.

Бұл теореманың шартында градиенттік құлдилаудың жинақталу

жылдамдығын бағалау мүмкін емес, біз f(x) функциясы қатты дөңес болған

жағдайда бағалаймыз.

Қатты дөңес деп екі рет үздіксіз дифференциалданған, екінші ретті

туындысының матрицасы кез-келген x, yRn үшін

 

шартын қанағаттандыратын функцияны атайды, мұндағы қандай да бір сандар.

Теорема 2. f(x) – қатты дөңес функция, ал {xк} тізбегі әдісі бойынша құрылсын, ал қадамы

 

 

 

шартынан алынсын. Онда {xк} тізбегі минимум нүктесіне геометриялық

прогрессия жылдамдығымен жетеді, , яғни неғұрлым үлкен к үшін

тенсіздігі орындалады. Теореманың дәлелдеуін [1]

әдебиеттен табуға болады.

Жыралар эффектісі. Релаксациялық әдістер. Екінші теорема

тұжырымынан градиентті әдістер q еселігі геометриялық прогрессия

жылдамдығымен жинақталатынын тапқан болатынбыз. q – f”(x) матрицасының максимум және минимум өзіндік санынан М және m – нен тәуелді.

Егер  онда q саны 1-ге жақын және градиенттік әдістер нашар

жинақтала бастайды. Бұл геометриялық тұрғыдан жақсы түсіндірілген және

әдебиеттерге «жыралар эффектісі» ретінде танымал. Егер М және m сандары

бір-бірінен қатты ерекшеленсе, онда f(x)=const деңгей бетінің көрінісі иірімдік құрылымды болады (f(x)-тің максимум табу есептерінде сәйкес қатты иірімдер болады).

Осы айтылғандарды түсіндіру үшін мысал қарастырайық.

2-мысал. f(x)=(х1)2 + 16(х2)2 функциясын қарастырайық. Оның деңгей

сызығы х1 осі бойымен созылған. Берілген жағдайда екінші ретті туынды

матрицасы тұрақты:

 

 

Ең кіші, ең үлкен меншікті сандары сәйкес 2 және 32-ге тең, яғни бір-бірінен

айырмашылығы көп. Градиенттік әдіс траекториясы жыраның «түбіне»

жеткілікті шапшаң, тез құлдилаумен және содан соң жәй ирек тәріздес

қозғалыспен минимум нүктеге  жақындаумен сипатталады.

Бұндай жағдайдан шығудың жолдарының бірі мақсат функциясының

тәуелсіз айнымалыларының масштабтарын өзгерту болып табылады. Осы

тәсілді келесі мысалмен түсіндірейік. f(x) функциясы мынадай түрде берілсін.

 

    (8)

 

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

 

         (9)

 

Өзіміздің мысалға оралайық. Біз қозғалысты х0={2,2}T нүктесінен бастадық, осы нүктедегі градиентті құраушылар

 

     

 

ерекшеленетін болғандықтан, бағыттан минимум x*={0.0}T нүктесіне

ауытқитын құлдилау бағытын алған болатынбыз. Берілген жағдайда (9)

айнымалыларын ауыстыру мына түрде болады:

 

 

Жаңа координаталарда  минимумдап отырған функция   түрінде

болады. нүктелерінде градиент векторы минимум

нүктесіне бағытталған, ал деңгей сызығы шеңбер болады (12-сурет).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Қортынды

 

Сонымен, градиенттік әдістер  қарапайым және сипаттамасы

әртүрлі функцияларды минимизациялау үшін қолданылады. Олардың жетістігі осында. Бірақ олар жәй жинақталады, егер минимумдап отырған функцияның екінші ретті туындысына нашар шарт қойылатын болса. Бұл f(x)-тың күрделі құрылымында – «жыра» немесе «иірім» болуына байланысты.