جستجوی خط

استراتژی جستجوی خطی در بهینه‌سازی، یکی از دو رویکرد تکراری پایه ای برای یافتن مینیمم محلی $\mathbf {x} ^{*}$ است با یک تابع هدف $f:\mathbb {R} ^{n}\to \mathbb {R}$ . رویکرد دیگر منطقه اعتماد است.

رویکرد جستجوی خطی ابتدا یک جهت نزولی (descent direction) را که در جهت آن تابع هدف $f$ کاهش می‌یابد، پیدا می‌کند، سپس اندازه گام را محاسبه می‌کند که تعیین کند چقدر در جهت نزولی حرکت کند تا به مینیمم برسد. جهت نزولی را می‌توان با روش‌های مختلفی مانند روش نزول گرادیان یا روش شبه نیوتنی محاسبه کرد. اندازه گام را می‌توان دقیقاً یا به‌طور غیر دقیق تعیین کرد.

نحوه کاربرد

نمونه ای از روش گرادیان که از جستجوی خطی در مرحله ۴ استفاده می‌کند، در زیر آمده‌است:

1. شمارشگر تکرار را روی $\displaystyle k=0$ تنظیم کنید و یک حدس اولیه $\mathbf {x} _{0}$ برای مینیمم بزنید.
2. مراحل را تکرار کنید:
3. جهت نزول $\mathbf {p} _{k}$ را محاسبه کنید.
4. $\displaystyle \alpha _{k}$ را برای به حداقل رساندن تابع $h(\alpha _{k})=f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})$ روی$\alpha _{k}\in \mathbb {R} _{+}$ انتخاب کنید.
5. بوسیله $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}$ ، و ${\textstyle k=k+1}$ به روز رسانی کنید
6. تا وقتیکه $\|\nabla f(\mathbf {x} _{k+1})\|$ < tolerance.

در مرحله (۴) جستجوی خطی، الگوریتم تحت شرایطی می‌تواند دقیقاً h را با حل $h'(\alpha _{k})=0$، مینیمم کند، و در صورت عدم برقراری آن شرایط، h را به حد کافی به‌طور تقریبی کاهش دهد. یکی از نمونه روش‌های حل بوسیله $h'(\alpha _{k})=0$، روش گرادیان مزدوج است. استفاده از روش حل به‌طور تقریبی، جستجوی خطی غیر دقیق نامیده می‌شود و ممکن است به روش‌های مختلفی مانند جستجوی خطی عقب‌گرد یا با استفاده از شرایط Wolfe انجام شود.

مانند سایر روش‌های بهینه‌سازی، جستجوی خطی ممکن است با تبرید شبیه‌سازی شده ترکیب شود تا به آن اجازه دهد از مینیمم‌های موضعی عبور کند.

الگوریتم‌ها

روش‌های جستجوی مستقیم

در این روش‌ها، یک بازه که مینیمم در آن وجود دارد را انتخاب می‌کنیم و در ادامه سعی می‌کنیم با کاهش دادن طول بازه، به مینیمم نزدیک شده و در نهایت به قدری بازه را کوچک کنیم که تقریب خوبی از مینیمم حاصل شود. برای این کار، ابتدا باید بازه ای انتخاب شود که مینیمم در این بازه قرار داشته باشد، بنابراین الگوریتم باید نقاط x ₁ و x ₂ را به گونه‌ای مشخص کند که مینیمم مورد نظر بین آنها باشد. سپس در این بازه دو نقطه دیگر، x ₃ و x ₄ را در نظر می‌گیریم و با محاسبه $f(x)$ در این ۲ نقطهٔ درونی، تصمیم می‌گیریم که چگونه طول بازه را کاهش دهیم (در این قسمت x ₁ و x ₂ نقاط مرزی بازه اند و x ₃ و x ₄ نقاط درونی، لذا باید برای کوچک کردن طول بازه، یکی از نقاط مرزی x ₁ یا x ₂ را حذف کنیم که یکی از نقاط x ₃ یا x ₄ به‌جای آن نقطه مرزی شود)، برای این کار مقدارهای تابع هدف بدست آمده در نقاط درونی با یکدیگر مقایسه می‌شوند و نقطهٔ مرزی مجاور با نقطه درونی ای که مقدار تابع هدف بزرگ‌تری دارد، حذف می‌شود. در مراحل بعدی، فقط یک نقطه درونی اضافی باید محاسبه شود. برای نحوه تقسیم بازه، رویکردهای متفاوتی مطرح می‌شوند که یکی از آن‌ها الگوریتم جستجوی نسبت طلایی است که به‌ویژه ساده و مؤثر است، زیرا نسبت‌های بازه بدون توجه به نحوه ادامه جستجو حفظ می‌شوند:

${\frac {1}{\varphi }}(x_{2}-x_{1})=x_{4}-x_{1}=x_{2}-x_{3}=\varphi (x_{2}-x_{4})=\varphi (x_{3}-x_{1})=\varphi ^{2}(x_{4}-x_{3})$

$\varphi ={\frac {1}{2}}(1+{\sqrt {5}})\approx 1.618$

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

• جستجوی نسبت طلایی
• جستجوی شبکه ای
• نرخ یادگیری
• جستجوی الگو (بهینه‌سازی)
• روش وتری

بیشتر خواندن

• Dennis, J. E. , Jr.; Schnabel, Robert B. (1983). "Globally Convergent Modifications of Newton's Method". Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice-Hall. pp. 111–154. ISBN 0-13-627216-9.
• Nocedal, Jorge; Wright, Stephen J. (1999). "Line Search Methods". Numerical Optimization. New York: Springer. pp. 34–63. ISBN 0-387-98793-2.
• Sun, Wenyu; Yuan, Ya-Xiang (2006). "Line Search". Optimization Theory and Methods: Nonlinear Programming. New York: Springer. pp. 71–117. ISBN 0-387-24975-3.