نمایش مبدأ برای الگوریتم لونبرگ-مارکوارت

'''الگوریتم لونبرگ-مارکوارت''' روشی است برای یافتن کمینه یک تابع غیر خطی چند متغیره که به عنوان یک روش استاندارد برای [[حل مسئله]] [[کمینه مربعات]] برای توابع غیرخطی درآمده است.<ref>H.D. Mittelmann. The Least Squares Problem. [web page] http://plato.asu.edu/topics/problems/nlolsq.html {{Webarchive|url=https://web.archive.org/web/20051215005909/http://plato.asu.edu/topics/problems/nlolsq.html |date=۱۵ دسامبر ۲۰۰۵ }}, Jul. 2004. [Accessed on 4 Aug. 2004.]</ref>

الگوریتم لونبرگ-مارکوارت (LMA) بین [[الگوریتم گاوس-نیوتون]] (GNA) و روش [[گرادیان کاهشی]] [[درون‌یابی|درونیابی]] می‌کند. LMA از GNA مقاوم‌تر است، که یعنی در بسیاری مواقع، حتی اگر بسیار دورتر از کمینه نهایی شروع کرده باشد، جوابی را پیدا می‌کند. از دیگر سو، برای تابع‌های خوشرفتار و پارامترهای آغازین معقول، LMA کمی کندتر از GNA است. LMA پرطرفدارترین الگوریتم برازش خم است و کاربران کمی ممکن است به روش‌های دیگر برازش خم نیاز پیدا کنند.

== مسئله ==
<math>m</math> [[تابع]] <math>f_1,\cdots,f_m</math>از <math>n</math> پارامتر <math>p_1,\cdots,p_n</math> که <math>m \ge n</math> داده شده‌اند. برای آسانی از نمادگذاری [[بردار|برداری]] برای هر دوی تابع‌ها و [[پارامتر]]ها استفاده می‌کنیم.

: <math>\mathbf{f^T}=(f_1,\cdots,f_m)</math> و <math>\mathbf{p^T}=(p_1,\cdots,p_n)</math>

مسئله [[کمترین مربعات]] شامل جستن [[بردار]] پارامترهای <math>\mathbf{p}</math> است که برای آن تابع هزینه

: <math>S(\mathbf{p})=\mathbf{f^Tf}=\sum_{i=1}^m{[f_i(\mathbf{p})]}^2</math>

کمینه می‌شود.

کاربرد اصلی در مسئله برازش خم کمترین مربعات است: مجموعه‌ای از جفت‌های تجربی داده به فرم <math>(t_i,y_i)</math> در دست است، می‌خواهیم <math>\mathbf{p}</math> پارامترهای خم مدل <math>c(t|\mathbf{p})</math> را به گونه‌ای [[بهینه]] کنیم که مجموع مربعات انحراف‌ها

: <math>f_i(\mathbf{p})=y_i-c(t_i|\mathbf{p})</math>

[[کمینه]] گردد.

(صحبتی دربارهٔ نمادگذاری: ما از حرف <math>x</math> به خاطر اینکه برخی اوقات به جای <math>p</math> و برخی اوقات به جای <math>t</math> استفاده می‌شود خودداری می‌کنیم)

== راه حل ==
مانند سایر الگوریتم‌های کمینه‌سازی عددی، الگوریتم لونبرگ-مارکارد یک رویه تکراری است. برای شروع کمینه‌سازی، کاربر باید یک حدس آغازین برای بردار <math>\mathbf{p}</math> پارامترها ارائه کند. در بسیاری مواقع یک حدس ناآگاهانه استاندارد مانند <math>\mathbf{p^T}=(1,1,\cdots,1)</math> به خوبی کار می‌کند. در جاهای دیگر، الگوریتم تنها وقتی کار می‌کند که حدس آغازین تا حدی به جواب نهایی نزدیک باشد.

در هر گام تکرار، بردار <math>\mathbf{p}</math> پارامترها با یک تخمین جدید <math>\mathbf{p+q}</math> جایگزین می‌شود. برای دستیابی به <math>\mathbf{q}</math> توابع <math>f_i(\mathbf{p+q})</math> با خطی‌سازیشان

: <math>\mathbf{f(p+q)\approx f(p)+Jq}</math>

تخمین زده می‌شوند که <math>\mathbf{J}</math> [[ژاکوبین]] <math>\mathbf{f}</math> در <math>\mathbf{p}</math> است.

در یک کمینه مجموع مربعات <math>S</math>، داریم <math>\nabla_qS=0</math>. با خطی‌سازی بالا، از این به معادله زیر می‌رسیم

: <math>(\mathbf{J^TJ})\mathbf{q}=-\mathbf{J^Tf}</math>

که <math>\mathbf{q}</math> را می‌توان از آن با وارون کردن <math>\mathbf{J^TJ}</math> بدست آورد. کلید LMA جایگزینی این معادله با «نسخه میراشده» آن است

: <math>(\mathbf{J^TJ}+\lambda)\mathbf{q}=-\mathbf{J^Tf}</math>

[[ضریب میرایی]] نامنفی <math>\lambda</math> در هر تکرار تنظیم می‌شود. اگر کاهش <math>S</math> تند بود مقدار کوچک‌تری به آن می‌دهیم که الگوریتم را به GNA نزدیکتر می‌کند، اما اگر یک تکرار کاهش ناکافی نشان داد <math>\lambda</math> را افزایش داده و یک گام را نزدیکتر به جهت نزول گرادیانی برمی‌داریم. ضریب میرایی مشابهی در [[ساماندهی تیخونوف]] دیده می‌شود که در حل مسائل خطی کژنمود سودمند است.

اگر یک طول قدم بازیابی شده یا کاهش مجموع مربعات برای آخرین مجموعه پارامترهای <math>\mathbf{p}</math>از مقادیر از پیش تعیین شده کمتر باشند تکرار پایان می‌یابد و آخرین بردار پارامتر <math>\mathbf{p}</math> به عنوان جواب در نظر گرفته می‌شود.

== منابع ==
{{پانویس}}

== جستارهای وابسته ==
* [[برنامه‌ریزی غیرخطی]]

{{الگوریتم‌های بهینه‌سازی}}

[[رده:الگوریتم‌های آماری]]
[[رده:الگوریتم‌های بهینه‌سازی]]
[[رده:روش‌های بهینه‌سازی]]
[[رده:کمترین مربعات]]