ПӘннің ОҚУ-Әдістемелік кешені «Технологиялық процесстерді оңтайландыру әдістері»


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



бет64/95
Дата18.12.2019
өлшемі5,43 Mb.
#53747
1   ...   60   61   62   63   64   65   66   67   ...   95
Байланысты:
21ad3594-56e4-11e5-884b-f6d299da70eeУМК новое по МОТП каз (умм)


Дәріс №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,...),



рк векторы – ол яғни бағыттас болып келеді, ал λк||рк|| ға - адымның шамасы болып табылады. Егер ||рк|| =1 болса, онда адымның шамасы тең,ал түсiру векторның ұзындығы бiрлiкке тең болады. Айтып ескеретін болсақ кейде λк вектордың ұзындық рк тәуелсiз адымды болады.

Бұл жерде 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с деп аталады



Формуласы

(1)
яғни әрбiр итерациядағы түсiруiн бағыт - бұл хк тiң ағымдағы нүкте есептеп шығарылуын антиградиент деп атайды.


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


хкнын 4 ағымдағы векторына суретке нүктеге сәйкес келетін нүктеде мақсаттық функцияның мәнi А бiрлiгіне сәйкес болады. Мәнi бар деңгей сызығын 1-ε менін қабылдап, шаманың жеткiлiктi екенін қараймыз. Жанында аз және бұл деңгей сызықтары жеткiлiктiсімен қатарлас санасамыз. Тек қана x1 лер кiшiсi мәнi бар деңгей сызығына ауысу өзгерiсте С нүктенi бередi, нүкте ал тек қана х2 өзгерiсте арқылы хАС шебер қашықтықты В деп белгiлеймiз.

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



Әрб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 (6-шы сурет) ортогональ болады.


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

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

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

2. х2 дiң нүктесімен емес, керісінше градиент бойынша (7-шi сурет) х2д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нде жатады.


3. Градиенттердiң кездесетiн әдiсi

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


1. р0 = -g0 антиградиент бойынша алға адым басу,
2. pk+1 = -gk+1 + βkpk, где βк = (gk+', gk+') / (gk, gk).
Бұл не не бiлдiредi

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

Бұл және түсiрудi бағыт болады р1= -g1 β0 g0, бiз мына - g1 градиент орынымызға қолданамыз

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

содан соңы β1= (g2, g2) / (g1 ,g1) и р2 = -g2 + β1 p1 жане т.с.с.
4.Координат бойынша түсiру әдiсі

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

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

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

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

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

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

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



Достарыңызбен бөлісу:
1   ...   60   61   62   63   64   65   66   67   ...   95




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет