نمایش مبدأ برای جستجوی خط

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

رویکرد جستجوی خطی ابتدا یک [[:en:Descent_direction|جهت نزولی (descent direction)]] را که در جهت آن تابع هدف <math>f</math> کاهش می‌یابد، پیدا می‌کند، سپس اندازه گام را محاسبه می‌کند که تعیین کند چقدر در جهت نزولی حرکت کند تا به مینیمم برسد. جهت نزولی را می‌توان با روش‌های مختلفی مانند روش [[گرادیان کاهشی|نزول گرادیان]] یا روش شبه نیوتنی محاسبه کرد. اندازه گام را می‌توان دقیقاً یا به‌طور غیر دقیق تعیین کرد.

== نحوه کاربرد ==
نمونه ای از روش گرادیان که از جستجوی خطی در مرحله ۴ استفاده می‌کند، در زیر آمده‌است:
# شمارشگر تکرار را روی <math>\displaystyle k=0</math> تنظیم کنید و یک حدس اولیه <math>\mathbf{x}_0</math> برای مینیمم بزنید.
# مراحل را تکرار کنید:
# جهت نزول <math>\mathbf{p}_k</math> را محاسبه کنید.
#  <math>\displaystyle \alpha_k</math> را برای به حداقل رساندن تابع <math>h(\alpha_k)=f(\mathbf{x}_k+\alpha_k\mathbf{p}_k)</math> روی<math>\alpha_k\in\mathbb R_+</math> انتخاب کنید.
# بوسیله <math>\mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{p}_k</math> ، و <math display="inline"> k=k+1</math> به روز رسانی کنید
# تا وقتیکه <math>\|\nabla f(\mathbf{x}_{k+1})\|</math> < tolerance.

در مرحله (۴) جستجوی خطی، الگوریتم تحت شرایطی می‌تواند ''دقیقاً'' ''h'' را با حل <math>h'(\alpha_k)=0</math>، مینیمم کند، و در صورت عدم برقراری آن شرایط، ''h را'' به حد کافی ''به‌طور تقریبی کاهش دهد''. یکی از نمونه روش‌های حل بوسیله <math>h'(\alpha_k)=0</math>، [[روش گرادیان مزدوج|روش گرادیان مزدوج است]]. استفاده از روش حل به‌طور تقریبی، جستجوی خطی غیر دقیق نامیده می‌شود و ممکن است به روش‌های مختلفی مانند [[:en:Backtracking_line_search|جستجوی خطی عقب‌گرد]] یا با استفاده از [[:en:Wolfe_conditions|شرایط Wolfe]] انجام شود.

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

== الگوریتم‌ها ==
=== روش‌های جستجوی مستقیم ===
در این روش‌ها، یک بازه که مینیمم در آن وجود دارد را انتخاب می‌کنیم و در ادامه سعی می‌کنیم با کاهش دادن طول بازه، به مینیمم نزدیک شده و در نهایت به قدری بازه را کوچک کنیم که تقریب خوبی از مینیمم حاصل شود. برای این کار، ابتدا باید بازه ای انتخاب شود که مینیمم در این بازه قرار داشته باشد، بنابراین الگوریتم باید نقاط ''x'' <sub>1</sub> و ''x'' <sub>2</sub> را به گونه‌ای مشخص کند که مینیمم مورد نظر بین آنها باشد. سپس در این بازه دو نقطه دیگر، ''x'' <sub>3</sub> و ''x'' <sub>4</sub> را در نظر می‌گیریم و با محاسبه <math>f(x)</math> در این ۲ نقطهٔ درونی، تصمیم می‌گیریم که چگونه طول بازه را کاهش دهیم (در این قسمت ''x'' <sub>1</sub> و ''x'' <sub>2</sub> نقاط مرزی بازه اند و ''x'' <sub>3</sub> و ''x'' <sub>4</sub> نقاط درونی، لذا باید برای کوچک کردن طول بازه، یکی از نقاط مرزی ''x'' <sub>1</sub> یا ''x'' <sub>2</sub> را حذف کنیم که یکی از نقاط ''x'' <sub>3</sub> یا ''x'' <sub>4</sub> به‌جای آن نقطه مرزی شود)، برای این کار مقدارهای تابع هدف بدست آمده در نقاط درونی با یکدیگر مقایسه می‌شوند و نقطهٔ مرزی مجاور با نقطه درونی ای که مقدار تابع هدف بزرگ‌تری دارد، حذف می‌شود. در مراحل بعدی، فقط یک نقطه درونی اضافی باید محاسبه شود. برای نحوه تقسیم بازه، رویکردهای متفاوتی مطرح می‌شوند که یکی از آن‌ها الگوریتم<ref>{{Cite book|first1=M. J.|last1=Box|first2=D.|last2=Davies|first3=W. H.|last3=Swann|title=Non-Linear optimisation Techniques|publisher=Oliver & Boyd|year=1969}}</ref> [[:en:Golden-section search|جستجوی نسبت طلایی]] است که به‌ویژه ساده و مؤثر است، زیرا نسبت‌های بازه بدون توجه به نحوه ادامه جستجو حفظ می‌شوند:

: <math>\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)</math>

: <math>\varphi=\frac{1}{2}(1+\sqrt 5) \approx 1.618</math>

== جستارهای وابسته ==
* [[:en:Golden-section search|جستجوی نسبت طلایی]]
* [[:en:Hyperparameter optimization#Grid%20search|جستجوی شبکه ای]]
* [[:en:Learning_rate|نرخ یادگیری]]
* [[:en:Pattern search (optimization)|جستجوی الگو (بهینه‌سازی)]]
* [[روش وتری]]

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

== بیشتر خواندن ==
* {{cite book|first=J. E. , Jr.|last=Dennis|first2=Robert B.|last2=Schnabel|chapter=Globally Convergent Modifications of Newton's Method|title=Numerical Methods for Unconstrained Optimization and Nonlinear Equations|url=https://archive.org/details/numericalmethods0000denn|location=Englewood Cliffs|publisher=Prentice-Hall|year=1983|isbn=0-13-627216-9|pages=[https://archive.org/details/numericalmethods0000denn/page/111 111]–154}}
* {{cite book|first=Jorge|last=Nocedal|first2=Stephen J.|last2=Wright|chapter=Line Search Methods|title=Numerical Optimization|url=https://archive.org/details/numericaloptimiz0000noce|location=New York|publisher=Springer|year=1999|isbn=0-387-98793-2|pages=[https://archive.org/details/numericaloptimiz0000noce/page/n59 34]–63}}
* {{cite book|first=Wenyu|last=Sun|first2=Ya-Xiang|last2=Yuan|chapter=Line Search|title=Optimization Theory and Methods: Nonlinear Programming|location=New York|publisher=Springer|year=2006|isbn=0-387-24975-3|pages=71–117}}
{{الگوریتم‌های بهینه‌سازی}}
[[رده:روش‌های بهینه‌سازی]]