Кіріспе
Сызықтық емес ең кіші квадраттар мәселелерін шешуге қолданылатын алгоритм. Математика және информатикада Левенберг-Маркардт алгоритмі (LMA немесе LM), сондай-ақ демпферленген ең кіші квадраттар (DLS) әдісі деп те аталады, сызықтық емес ең кіші квадраттар мәселелерін шешу үшін қолданылады. Мұндай минимизациялау мәселелері ең кіші квадраттар қисығына сәйкестік кезінде жиі туындайды. LMA Гаусс-Ньютон алгоритмі (GNA) мен градиенттік түсу әдісі арасында кезекті түрде қолданылады. LMA, GNA-ға қарағанда сенімдірек, яғни көп жағдайда ол соңғы минимумнан қашық болса да шешім табады. Жақсы қасиеттері бар функциялар мен дұрыс бастапқы параметрлер үшін LMA, GNA-дан баяу жұмыс істейді. LMA сенімді аймақ тәсілін қолдана отырып, Гаусс-Ньютон алгоритмі ретінде де қарастырылуы мүмкін. Алгоритмді алғаш 1944 жылы Кеннет Левенберг жариялаған, бірақ басқа итеративтік оңтайландыру алгоритмдері сияқты, LMA да тек жергілікті минимумды табады, ол міндетті түрде глобальдық минимум емес.
In mathematics and computing, the Levenberg–Marquardt algorithm (LMA or just LM), also known as the damped least squares (DLS) method, is used to solve non linear least squares problems. These minimization problems arise especially in least squares curve fitting. The LMA interpolates between the Gauss–Newton algorithm (GNA) and the method of gradient descent. The LMA is more robust than the GNA, which means that in many cases it finds a solution even if it starts very far off the final minimum. For well behaved functions and reasonable starting parameters, the LMA tends to be slower than the GNA. LMA can also be viewed as Gauss–Newton using a trust region approach. The algorithm was first published in 1944 by Kenneth Levenberg, However, like other iterative optimization algorithms, the LMA finds only a local minimum, which is not necessarily the global minimum.
Түсірткі параметрін таңдау
Әртүрлі аз-көп эвристикалық аргументтер \lambda демпингтік параметрі үшін ең жақсы таңдауды анықтау үшін ұсынылған. Кейбір таңдаулар алгоритмнің жергілікті конвергенциясын қамтамасыз ететін теориялық дәлелдер бар; алайда, бұл таңдаулар алгоритмнің жаһандық конвергенциясын ең тік түсетін тәсілдің жағымсыз қасиеттеріне, атап айтқанда, оптимумға жақын өте баяу конвергенцияға ұшыратуы мүмкін. Кез келген таңдаудың абсолюттік мәні бастапқы мәселенің қаншалықты дұрыс масштабталғанына байланысты. Маркардт \lambda 0 мәнінен және \nu > 1 коэффициентінен бастауды ұсынды. Бастапқыда бастапқы нүктеден бір қадам жасап, \lambda 0 демпинг коэффициентімен және екіншісі \lambda 0 / \nu арқылы қалдықтардың квадраттар қосындысын есептеу және анықтау. Егер екеуі де бастапқы нүктеден нашар нәтиже берсе, демпинг \nu көбейту арқылы біртіндеп ұлғаяды, кез келген k үшін \lambda 0\nu^k жаңа демпинг коэффициентімен жақсы нүкте табылғанша. Егер \lambda / \nu демпинг коэффициентін пайдалану қалдықтардың квадратын азайтатын болса, онда бұл \lambda-ның жаңа мәні ретінде қабылданады (және жаңа оңтайлы нүкте осы демпинг коэффициентімен алынған нүкте ретінде қабылданады) және процесс жалғасады; егер \lambda / \nu нашар нәтиже берсе, бірақ \lambda жақсы нәтиже берсе, онда \lambda өзгеріссіз қалады және жаңа оңтайлы нүкте \lambda демпинг коэффициентімен алынған мән ретінде қабылданады. Демпинг параметрін басқарудың тиімді стратегиясы, «кешіктірілген сыйлық» деп аталатын стратегия, әрбір жоғары қадам үшін параметрін аздап ұлғайту және әрбір төмен қадам үшін үлкен мөлшерде азайтудан тұрады. Бұл стратегияның мақсаты – оптимизацияның басында тым тез төмен жылжудан аулақ болу, соның салдарынан келесі итерацияларда қол жетімді қадамдарды шектеу және конвергенцияны баяулату. Екінші ретті туынды өте күрделі өрнек болуы мүмкін болғандықтан, оны шекті айырмашылықпен алмастыру ыңғайлы болуы мүмкін, бұл алгоритммен есептелген және оны есептеу үшін бір ғана қосымша функцияны бағалау қажет. Шекті айырмашылық қадамын таңдау алгоритмнің тұрақтылығына әсер етуі мүмкін, ал шамамен 0,1 мәні әдетте жалпы жағдайда орынды.
If use of the damping factor \lambda / \nu results in a reduction in squared residual, then this is taken as the new value of \lambda (and the new optimum location is taken as that obtained with this damping factor) and the process continues; if using \lambda / \nu resulted in a worse residual, but using \lambda resulted in a better residual, then \lambda is left unchanged and the new optimum is taken as the value obtained with \lambda as damping factor. An effective strategy for the control of the damping parameter, called delayed gratification, consists of increasing the parameter by a small amount for each uphill step, and decreasing by a large amount for each downhill step. The idea behind this strategy is to avoid moving downhill too fast in the beginning of optimization, therefore restricting the steps available in future iterations and therefore slowing down convergence. Since the second order derivative can be a fairly complex expression, it can be convenient to replace it with a finite difference approximation
where and have already been computed by the algorithm, therefore requiring only one additional function evaluation to compute The choice of the finite difference step can affect the stability of the algorithm, and a value of around 0.1 is usually reasonable in general.