Дәріс №014. Сөзсiз ықшамдаудың әдiстерi

Сұрақтар:

1. 
   Градиент әдiстерi
   
2. 
   Әдiстің параллелге қатысты
   
3. 
   Градиенттердiң кездесетiн әдiсi
   
4. 
   Координат бойынша түсiру әдiсі
   

1.Градиент әдiстерi

Функцияныңшектеулі минимумының iздестiруiнiң әдiстерi көп айнымалы жоқ болғанда. F (x ) тың функциясының минимизациялауының итерациялық әдiстерi вектор тiзбектiң құрастыруларында тұрады, яғни ол x0, x1дiң нүктелерi ......, F (x1 ) F (x0 ) жане.. > F (xk).Кез келген мұндай әдiспен түсiрудi әдiс деп аталады. Табиғи, минимумның нүктесiне алынатын нүктелер тiзбегiнiң жинақтылығы қамтамасыз етуi керек, яғни адымдардың саны ар жағында минимумның нүктесiн байланысты алынуға немесе оған жақын адымдардың тиiстi санында жеткiлiктi мүмкiндiк беретiн әдiстерi қаралады.

Өкiнiшке орай, неше сөзi керектi мөлшерде жақын адымдардың санының шексiз үлкеюiнде бұл жерде қолдануға болмайды. Бұл қасиеттiң теория жағынан алғанда барлық қиын әдiстерi мынадаларға ие болады, бiрақ үлкен өлшем есептерiндегi минимумға iс жүзiнде жақындық компьютердегi сандарды көрсетудi қателiкпен шартталған есептеулердiң қателерiмен шектеледi. Сондықтан нақты компьютер бағдарламаларының өңдеуiнiң жанында мәлiметтердiң тиiстi түрлерi таңдай есептеудiң хабарлары екi еселенген дәлдiк болады.

Итерациялық тiзбектiң құрастырулары үшiн x0нiң бастапқы жуықтауы таңдалуы керек. Бұл шектеулерi бар есептердегi мүмкiндік нүкте болуы керек, шек қойылмай есептерде теория жағынан алғанда кез келген нүкте болады. Мақсаттық функцияның мiнез-құлығы туралы барлық бар мәлiметтi орынды қолдану жақынырақ минимумның нүктесiне x0дi таңдау үшiн F x қолданамыз.

Бастапқы жуықтау алынғаннан кейiн, екi шешiм қабылдау керек одан өтуден бұрын келесi нүктеге екi шешiм қабылдау керек:

1. Нүктеге мақсаттық функцияның кiшi мәнiмен x0нен кеткен бағыт таңдау (бағыт түсiруі);

2. Бағыт түсiруі бойынша Шаға шамасын анықтау. {хк } Түрінде итерациялық нүктелер тiзбегi түсiруiн кез келген әдiсте жазып ала алады: х^к+'=х^к + λ_кp_к,(к = 0, 1,...),

Бұл жерде _p ^k _{=( p} ^k _{, p} ^k _{) —} р^к вектордың ұзындығы болып табылады

Түсiрудiң әдiстерi вектор р^к ды құрылысының процедуралары және есептеуі ерекшеленедi. Жанында бұл алған нүктелердiң ендi (соңғы ) бiр немесе екi соңғысы қолданыла алады.

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

Жанында ең болмаса аз адым жеткiлiктi, бiз мақсаттық функцияның кему қамтамасыз ететiн тек қана бағыт қызықтыра алады. Мақсаттық функцияның туындыларының бiрiншi бөлiндiлерiн үздiксiздiк жори және х олардың кез келген нүктесiнде Тэйлор оның қатарластыруы қолданамыз F(x + λр) ≈ F(x) + λ(g, p).Х олардың нүкте есептеп шығарылған функция g— градиент болады. Функция F(x + λр) - F(x) < 0 терiс скалярлық көбейтуде осылай анықталады. Сонымен, түсiрудiң бағыты антиградиентоммен өткiр бұрыш құрауы керек. Бұл қорытынды әдiл және шектеулерi бар есептер үшiн, бiрақ жанында аз адым жеткiлiктi шектеудiң бiрi де бұзбау үшiн анда әлi қосымша талап етiледi.

Бәрi мұндай бағыттар (қолайлы ) қолайлы деп аталады. Түсiрудiң бойымен алынуға мүмкiндiк беретiн әдiстерi - Zoutendijk G қолайлы бағыттар, Зойтендейк демек.)бағыттардың әдiстерiмен анықталады.

Градиент әдiсі кезектi нүкте әрбiр адым бойымен анықталатын әдiс деп аталады

Сурет. 4. Деңгей сызығы және антиградиент

Туындылардың бөлiндiлерi үшiн мынадай теңдiктi аламыз:дF/дх₁ = - ε /Δ₁ и дF/дх₂ = -ε/Δ₂..

6-шы сурет. Жедел түсiрудi ирек траектория

2. Параллелге қатысты әдіс
Алгоритм келесiлерден тұрады:

1. _х⁰нiң нүктелерi сияқты екi адымга iстеймiз (6-шы сурет)одан тезiрек түсiру әдiсін және _х²дiң нүктесiн аламыз.

2. _х² дiң нүктесімен емес, керісінше градиент бойынша (7-шi сурет) _х²дiң бағыты бойынша анықтаймыз.

3. Бағыт функцияның минимумының нүктесiн сияқты x3 табамыз және онда градиенттi есептеймiз.

4. Егер олар орындамаса, есептiң аяқтауын шарт тексеремiз және, 1-шi тармақты x0 орынымызға x3тердi пайдалана қайталаймыз.

Пысықтау нүктелер ендi туралы мәлiмет тезiрек түсiру әдiсiнде сақталмай ешқалай қолданылмады. Әдiсте параллел қатысты пысықтау нүктелер есте сақтауы керек, олар өйткенi түсiрудi бағыттың таңдауы үшiн қолданылады. Жинақтылықтың үдеуi үшiн бұл минимумның iздестiруiн процесс алған мәлiметке қолданудың идеялары ықшамдаудың көп әдiстерi негiзiнде жатады.

Градиент емес, түсiрудi бұрынғы бағыты бар оның сызықты комбинация бұл әдiстiң идеясы түсiру аттап бассаң бағыт ретiнде градиент емес қолданылатындай етiп. Егер итерацияның k-шысына түсiрудi бағыттың ҚРынан кейiн белгiлесе, онда ҚРдың векторларының тiзбегi төмендегiше салады: 1. яғни алғашқы қадам градиент бойынша iстеймiз,

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

Бұл және түсiрудi бағыт болады р¹= -g¹ – β₀ g⁰, бiз мына - g¹ градиент орынымызға қолданамыз

P1 минимумның нүктесi, g² онда дейiн бағытында градиент есептеуге жетуi керек.

содан соңы β₁= (g², g²) / (g¹ ,g¹) и р² = -g² + β₁ p¹ жане т.с.с.
4.Координат бойынша түсiру әдiсі

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

1. х⁰бастапқы нүктесiнде барлық координата xi ден басқа бекiтемiз.

2. Мақсаттық функцияның жанында минимумға жететiн ^х₁дiң мәнi анықтаймыз. Бұл бiр өлшемдi есептер, өйткенi барлық айнымалы ^х₁ден басқа бекiткен.

3. ^х₂ ден басқа, ^х₁дiң табылған координатасын бекiтемiз.

4. ^х₂ мақсаттық функцияның минимумының шартынан және тағы басқаларды анықтаймыз барлық координатаны аз болғанша.

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

1 Екiншi рет әдiстерi туралы.