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

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

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

مسئله

${\displaystyle m}$ تابع ${\displaystyle f_{1},\cdots ,f_{m}}$از ${\displaystyle n}$ پارامتر ${\displaystyle p_{1},\cdots ,p_{n}}$ که ${\displaystyle m\geq n}$ داده شده‌اند. برای آسانی از نمادگذاری برداری برای هر دوی تابع‌ها و پارامترها استفاده می‌کنیم.

${\displaystyle \mathbf {f^{T}} =(f_{1},\cdots ,f_{m})}$ و ${\displaystyle \mathbf {p^{T}} =(p_{1},\cdots ,p_{n})}$

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

${\displaystyle S(\mathbf {p} )=\mathbf {f^{T}f} =\sum _{i=1}^{m}{[f_{i}(\mathbf {p} )]}^{2}}$

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

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

${\displaystyle f_{i}(\mathbf {p} )=y_{i}-c(t_{i}|\mathbf {p} )}$

کمینه گردد.

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

راه حل

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

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

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

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

در یک کمینه مجموع مربعات ${\displaystyle S}$، داریم ${\displaystyle \nabla _{q}S=0}$. با خطی‌سازی بالا، از این به معادله زیر می‌رسیم

${\displaystyle (\mathbf {J^{T}J} )\mathbf {q} =-\mathbf {J^{T}f} }$

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

${\displaystyle (\mathbf {J^{T}J} +\lambda )\mathbf {q} =-\mathbf {J^{T}f} }$

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

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

منابع

1. H.D. Mittelmann. The Least Squares Problem. [web page] http://plato.asu.edu/topics/problems/nlolsq.html بایگانی‌شده در ۱۵ دسامبر ۲۰۰۵ توسط Wayback Machine, Jul. 2004. [Accessed on 4 Aug. 2004.]

جستارهای وابسته

• برنامه‌ریزی غیرخطی