4. Көп өлшемді іздеу әдістері

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

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

1. Гаусс-Зейдель әдісі

Гаусс-Зейдель әдісі айнымалылардың кезектесіп өзгеруінің бұрынғы әдістерінің принципіне негізделген. Оның идеясы келесідей тұжырымдалады: бастапқы нүктеден бірінші айнымалы арқылы қадам жүргізіледі, егер ол «сәтті» болса келесі айнымалыға көшеді. Егер қадам «сәтсіз» болатын болса, қадам қарама-қарсы бағытта жүргізіледі. Бұл

процедура барлық бағытта тек қана «сәтсіз» қадамдар болғанға дейін қайталана береді. Бұл жағдайда қадам мөлшері кішірейеді. Іздеу қадам мөлшерінің абсолютті шамасы берілген дәлдіктен кіші болғанға дейін жалғаса береді.

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

Осылайша, әдістің алгоритмі келесідей болады:

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

2. нүктесінде екіншіден басқа барлық координаттарды белгілей отырып, 1-ді x₂ бойынша қайталайды. Осылай x_n-ға дейін жалғасады. Алгоритм циклі n – әр координат бойымен бір өлшемді оңтайландырудың еселенген операциясынан кейін аяқталады. Әрі қарай мақсатты функциясының мәні алдыңғысынан аз болатын нүктелерін ала отырып, циклді қайталайды.

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

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

2. Хук және Дживс әдісі

Бұл әдісті Гаусс-Зейдель әдісінің модификациясы ретінде қарастыруға болады. Әдістің идеясы келесідей: бастапқы нүктеден Гаусс-Зейдель әдісінің бір итерациясы жүргізіледі; функцияның жөнделген мәні алынған жерде, уақытша бастапқы (негізгі) нүкте орналасады. Осыдан кейін іздеуді екі негізгі нүктені қосатын түзу бойымен жүргізеді. Бұл іздеуді бір өлшемді іздеу әдістерінің кез-келгенімен жүргізеді. Мақсатты функцияның минимал шамасы бар нүктені тауып, ол жерден Гаусс-Зейдель әдісінің тағы бір итерациясын жүргізеді. Ары қарайғы іздеу екі соңғы негізгі нүктелерді қосатын түзу

бойымен іске асады және осылай жалғаса береді.

Хук және Дживс әдісінің қарапайым модификациясын қарастырайық. Процедураға циклды түрде қайталанатын екі этап кіреді: негізгі нүкте айналасындағы зерттеушілік іздеу және үлгі бойынша іздеу.

1. Зерттеушілік іздеу. бастапқы негізгі нүктесі және әркоординатасы бойынша өсім беріледі. Негізгі нүктедегі мақсатты функцияның шамасы есептеледі. Ары қарай циклдік тәртіппен әр координата өзгертіледі:

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

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

2. Үлгі бойынша іздеу жәненүктелерін қосатын бағыт бойымен жүзеге асады. Қадамдар «сәтті» болғанға дейін бір немесе бірнеше қадамдар жасалынады, яғни, мақсатты функцияның жақсартылуына алып келеді. Қадамдардың шамасы әдеттежәнеарасындағы арақашықтыққа тең, яғни:

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

Хук және Дживс әдісінің кемшілігі Гаусс-Зейдель әдісіндегі секілді оның «жыралы» функцияларды оңтайландыру кезіндегі нашар жинақтылығы. Ол зерттеушілік іздеу деңгейінде алгоритмнің қисынсыз тоқтатылуына алып келуі мүмкін.