Кіріспе
Оптимизация алгоритмі
Оптимизацияда сызықты іздеу – бұл мақсатты функцияның жергілікті минимумдарын табуға арналған негізгі итеративті тәсіл. Ол ең бастысы, мақсатты функцияның азаятыны бағытты анықтап, содан кейін осы бағыт бойынша қанша қадам жасау керектігін анықтайтын қадам өлшемін есептейді. Бағытты анықтау үшін градиенттік төмендеу сияқты әр түрлі әдістерді немесе квази-Ньютон әдісін қолдануға болады. Қадам өлшемі нақты немесе шамамен анықталуы мүмкін.
Бір өлшемді сызық іздеу
f – бір өлшемді функция, және оның унимодальды екенін, яғни берілген [a,z] аралығында тек бір ғана жергілікті минимум x* бар екенін қарастырайық. Бұл f функциясы [a,x*] аралығында қатаң түрде кемитінін және [x*,z] аралығында қатаң түрде өсетінін білдіреді. Мұндай жағдайда (шамамен) минимум нүктесін табудың бірнеше тәсілі бар.
Нөлдік реттік әдістер
Нөлдік реттік әдістер тек функцияның мәнін бағалауды қолданады (яғни, мән оракулы), туындыларды емес: Үштік іздеу: a<b<c<z болатын b, c екі нүктені таңдаңыз. Егер f(b)≤f(c) болса, онда x* [a,c] аралығында болуы керек; егер f(b)≥f(c) болса, онда x* [b,z] аралығында болуы керек. Екі жағдайда да іздеу аралығын кішірек аралықпен алмастыруға болады. Егер b, c нүктелерін аралықтың ортасына жақын таңдасақ, аралық әр итерацияда ~1/2-ге қысқарады, бірақ әр итерацияда екі функцияның мәнін бағалау қажет. Сондықтан, әдіс жылдамдығымен сызықтық конвергенцияға ие. Егер b, c нүктелерін a, b, c, z бөлінісінде тең ұзындықтағы үш аралықты құратындай етіп таңдасақ, онда аралық әр итерацияда 2/3-ке қысқарады, сондықтан әдіс жылдамдығымен сызықтық конвергенцияға ие. Фибоначчи іздеу: Бұл үштік іздеудің нұсқасы, онда b, c нүктелері Фибоначчи тізбегіне сүйене отырып таңдалады. Әр итерацияда тек бір функцияның мәнін бағалау қажет, өйткені екінші нүкте бұрынғы аралықтың соңғы нүктесі болған. Сондықтан, әдіс жылдамдығы бойынша сызықтық конвергенцияға ие. Алтын қима іздеу: Бұл b, c нүктелері алтын қатынасқа сүйене отырып таңдалған нұсқа. Тағы да, әр итерацияда тек бір функцияның мәнін бағалау қажет, және әдіс жылдамдығы бойынша сызықтық конвергенцияға ие. Бұл қатынас нөлдік реттік әдістердің арасында ең оңтайлысы. Нөлдік реттік әдістер өте жалпылама – олар туындылануды немесе тіпті үздіксіздікті талап етпейді.
Ternary search: pick some two points b,c such that a<b<c<z. If f(b)≤f(c), then x* must be in [a,c]; if f(b)≥(c), then x* must be in [b,z]. In both cases, we can replace the search interval with a smaller one. If we pick b,c very close to the interval center, then the interval shrinks by ~1/2 at each iteration, but we need two function evaluations per iteration. Therefore, the method has linear convergence with rate If we pick b,c such that the partition a,b,c,z has three equal length intervals, then the interval shrinks by 2/3 at each iteration, so the method has linear convergence with rate Fibonacci search: This is a variant of ternary search in which the points b,c are selected based on the Fibonacci sequence. At each iteration, only one function evaluation is needed, since the other point was already an endpoint of a previous interval. Therefore, the method has linear convergence with rate Golden section search: This is a variant in which the points b,c are selected based on the golden ratio. Again, only one function evaluation is needed in each iteration, and the method has linear convergence with rate This ratio is optimal among the zero order methods. Zero order methods are very general they do not assume differentiability or even continuity.
Бірінші реттік әдістер
Бірінші реттік әдістер f функциясы үздіріссіз дифференциалданады және біз f-ті ғана емес, сонымен қатар оның туындысын да есептей аламыз деп қарастырады. Бiсекцiя әдісі f функциясының туындысын интервалдың ортасында, c нүктесінде есептейді: егер f'(c) = 0 болса, онда бұл минимум нүктесі; егер f'(c) > 0 болса, онда минимум [a, c] аралығында болуы керек; егер f'(c) < 0 болса, онда минимум [c, z] аралығында болуы керек. Бұл әдістің сызықтық жуықтасуы 0,5 шамасына тең.
Бұрыштық орнату әдістері
Көгерісті сәйкестендіру әдістері f функциясының қандай да бір аналитикалық түрі бар деп есептеу арқылы сызықтық емес конвергенцияға қол жеткізуге тырысады, мысалы, шекті дәрежелі көпмүшелік. Әр итерацияда f (немесе оның туындысы) мәні белгілі болатын "жұмыс нүктелерінің" жиынтығы болады. Осы нүктелер негізінде белгілі мәндерге сәйкес келетін көпмүшелік есептеліп, оның минимум аналитикалық түрде табылады. Минималды нүкте жаңа жұмыс нүктесі болады, содан кейін келесі итерацияға өтіледі:
Ньютон әдісі – қисықтарды сәйкестендіру әдісінің ерекше жағдайы, онда қисық f функциясының бірінші және екінші туындыларын пайдаланып құрастырылған екінші дәрежелі көпмүшелік болып табылады. Егер әдіс дегенерацияланбаған жергілікті минимумға (оң екінші туындысы бар) жеткілікті жақыннан басталатын болса, онда ол квадраттық конвергенцияға ие болады. Regula falsi – функцияны екінші дәрежелі көпмүшелікке сәйкестендіретін тағы бір әдіс, бірақ ол бірінші туындыны екі нүктеде қолданады, ал емес, бір нүктедегі бірінші және екінші туындыларды. Егер әдіс дегенерацияланбаған жергілікті минимумға жеткілікті жақыннан басталатын болса, онда ол кубтық сәйкестікке ие болады, яғни сызықтық емес конвергенциясы C ретімен шамаланады. Кубтық сәйкестік соңғы екі нүктедегі функцияның мәндерін және оның туындысын пайдаланып үшінші дәрежелі көпмүшелікке сәйкестендіріледі. Егер әдіс дегенерацияланбаған жергілікті минимумға жеткілікті жақыннан басталатын болса, онда ол квадраттық конвергенцияға ие болады. Көгерісті сәйкестендіру әдістері жергілікті минимумға жеткілікті жақыннан басталатын болса, сызықтық емес конвергенцияға ие болады, бірақ басқа жағдайларда айырылуы мүмкін. Қорғалған көгерісті сәйкестендіру әдістері қисықтарды сәйкестендіру әдісімен қатар сызықтық конвергенция әдісін бір мезгілде орындайды. Олар әр итерацияда қисықтарды сәйкестендіру әдісімен табылған нүкте, қорғау әдісімен сақталған интервалға жеткілікті жақын екенін тексереді; егер жақын болмаса, келесі итерацияны есептеу үшін қорғау әдісі қолданылады.
Жергілікті минимумдарды жеңу
Басқа оңтайландыру әдістері сияқты, сызықты іздеу әдісін де симуляциялық оттырумен біріктіріп, жергілікті минимумдардан асып өтуге болады.