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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم لونبرگ-مارکارد روشی است برای یافتن کمینه یک تابع غیر خطی چند متغیره که به عنوان یک روش استاندارد برای حل مسئله کمینه مربعات برای توابع غیرخطی درآمده است.[۱]

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

مسئله[ویرایش]

m تابع f_1,\cdots,f_mاز n پارامتر p_1,\cdots,p_n که m \ge n داده شده‌اند. برای آسانی از نمادگذاری برداری برای هر دوی تابع‌ها و پارامترها استفاده می‌کنیم.

\mathbf{f^T}=(f_1,\cdots,f_m) و \mathbf{p^T}=(p_1,\cdots,p_n)

مساله کمترین مربعات شامل جستن بردار پارامترهای \mathbf{p} است که برای آن تابع هزینه

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

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

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

f_i(\mathbf{p})=y_i-c(t_i|\mathbf{p})

کمینه گردد.

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

راه حل[ویرایش]

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

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

\mathbf{f(p+q)\approx f(p)+Jq}

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

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

(\mathbf{J^TJ})\mathbf{q}=-\mathbf{J^Tf}

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

(\mathbf{J^TJ}+\lambda)\mathbf{q}=-\mathbf{J^Tf}

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

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

منابع[ویرایش]

  1. H.D. Mittelmann. The Least Squares Problem. [web page] http://plato.asu.edu/topics/problems/nlolsq.html, Jul. 2004. [Accessed on 4 Aug. 2004.]
  1. H.D. Mittelmann. The Least Squares Problem. [web page] http://plato.asu.edu/topics/problems/nlolsq.html, Jul. 2004. [Accessed on 4 Aug. 2004.]

جستارهای وابسته[ویرایش]