استراتژی جستجوی خطی در بهینه سازی، یکی از دو رویکرد تکراری پایه ای برای یافتن مینیمم محلی x ∗ است با یک تابع هدف f : R n → R . رویکرد دیگر منطقه اعتماد است.
رویکرد جستجوی خطی ابتدا یک جهت نزولی ( descent direction ) را که در جهت آن تابع هدف f کاهش می یابد، پیدا می کند، سپس اندازه گام را محاسبه می کند که تعیین کند چقدر در جهت نزولی حرکت کند تا به مینیمم برسد. جهت نزولی را می توان با روش های مختلفی مانند روش نزول گرادیان یا روش شبه نیوتنی محاسبه کرد. اندازه گام را می توان دقیقاً یا به طور غیر دقیق تعیین کرد.
نمونه ای از روش گرادیان که از جستجوی خطی در مرحله ۴ استفاده می کند، در زیر آمده است:
• شمارشگر تکرار را روی k = 0 {\displaystyle \displaystyle k=0} تنظیم کنید و یک حدس اولیه x 0 {\displaystyle \mathbf {x} _{0}} برای مینیمم بزنید.
• مراحل را تکرار کنید:
• جهت نزول p k {\displaystyle \mathbf {p} _{k}} را محاسبه کنید.
• α k {\displaystyle \displaystyle \alpha _{k}} را برای به حداقل رساندن تابع h ( α k ) = f ( x k + α k p k ) {\displaystyle h ( \alpha _{k} ) =f ( \mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k} ) } روی α k ∈ R + {\displaystyle \alpha _{k}\in \mathbb {R} _{+}} انتخاب کنید.
• بوسیله x k + 1 = x k + α k p k {\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}} ، و k = k + 1 {\textstyle k=k+1} به روز رسانی کنید
• تا وقتیکه ‖ ∇ f ( x k + 1 ) ‖ {\displaystyle \|\nabla f ( \mathbf {x} _{k+1} ) \|} < tolerance.
در مرحله ( ۴ ) جستجوی خطی، الگوریتم تحت شرایطی می تواند دقیقاً h را با حل h ′ ( α k ) = 0 ، مینیمم کند، و در صورت عدم برقراری آن شرایط، h را به حد کافی به طور تقریبی کاهش دهد. یکی از نمونه روش های حل بوسیله h ′ ( α k ) = 0 ، روش گرادیان مزدوج است. استفاده از روش حل به طور تقریبی، جستجوی خطی غیر دقیق نامیده می شود و ممکن است به روش های مختلفی مانند جستجوی خطی عقب گرد یا با استفاده از شرایط Wolfe انجام شود.
مانند سایر روش های بهینه سازی، جستجوی خطی ممکن است با تبرید شبیه سازی شده ترکیب شود تا به آن اجازه دهد از مینیمم های موضعی عبور کند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفرویکرد جستجوی خطی ابتدا یک جهت نزولی ( descent direction ) را که در جهت آن تابع هدف f کاهش می یابد، پیدا می کند، سپس اندازه گام را محاسبه می کند که تعیین کند چقدر در جهت نزولی حرکت کند تا به مینیمم برسد. جهت نزولی را می توان با روش های مختلفی مانند روش نزول گرادیان یا روش شبه نیوتنی محاسبه کرد. اندازه گام را می توان دقیقاً یا به طور غیر دقیق تعیین کرد.
نمونه ای از روش گرادیان که از جستجوی خطی در مرحله ۴ استفاده می کند، در زیر آمده است:
• شمارشگر تکرار را روی k = 0 {\displaystyle \displaystyle k=0} تنظیم کنید و یک حدس اولیه x 0 {\displaystyle \mathbf {x} _{0}} برای مینیمم بزنید.
• مراحل را تکرار کنید:
• جهت نزول p k {\displaystyle \mathbf {p} _{k}} را محاسبه کنید.
• α k {\displaystyle \displaystyle \alpha _{k}} را برای به حداقل رساندن تابع h ( α k ) = f ( x k + α k p k ) {\displaystyle h ( \alpha _{k} ) =f ( \mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k} ) } روی α k ∈ R + {\displaystyle \alpha _{k}\in \mathbb {R} _{+}} انتخاب کنید.
• بوسیله x k + 1 = x k + α k p k {\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}} ، و k = k + 1 {\textstyle k=k+1} به روز رسانی کنید
• تا وقتیکه ‖ ∇ f ( x k + 1 ) ‖ {\displaystyle \|\nabla f ( \mathbf {x} _{k+1} ) \|} < tolerance.
در مرحله ( ۴ ) جستجوی خطی، الگوریتم تحت شرایطی می تواند دقیقاً h را با حل h ′ ( α k ) = 0 ، مینیمم کند، و در صورت عدم برقراری آن شرایط، h را به حد کافی به طور تقریبی کاهش دهد. یکی از نمونه روش های حل بوسیله h ′ ( α k ) = 0 ، روش گرادیان مزدوج است. استفاده از روش حل به طور تقریبی، جستجوی خطی غیر دقیق نامیده می شود و ممکن است به روش های مختلفی مانند جستجوی خطی عقب گرد یا با استفاده از شرایط Wolfe انجام شود.
مانند سایر روش های بهینه سازی، جستجوی خطی ممکن است با تبرید شبیه سازی شده ترکیب شود تا به آن اجازه دهد از مینیمم های موضعی عبور کند.
wiki: جستجوی خط