تصحیح فرمول جستجوی خطی در روش BFGS برای رسیدن به همگرایی سراسری
الموضوعات :سید علیرضا حسینی دهمیری 1 , منصوره حمزه نژاد 2
1 - گروه ریاضی، دانشگاه ولی‌عصر(عج) رفسنجان، رفسنجان، ایران
2 - گروه ریاضی، دانشگاه ولی‌عصر(عج) رفسنجان، رفسنجان، ایران
الکلمات المفتاحية: Newton method, BFGS method, unconstrained optimization, Quasi-Newton method, Global convergence,
ملخص المقالة :
مسائل برنامه‌ریزی غیرخطی در گروه مسائل پرکاربرد بهینه‌سازی در دنیای واقعی قرار دارند. تابع هدف این گونه از مسائل، علاوه بر غیرخطی بودن، در بیشتر موارد غیرمحدب است. این در حالی است که برای تضمین همگرایی سراسری در الگوریتم‌هایی که بر اساس روش نیوتن برای حل این مسائل پیشنهاد شده‌اند، عموماً شرط تحدب الزامی است. در این بین روش‌های شبه نیوتن بدلیل استفاده از تقریب ماتریس هسی یا وارون آن دارای محبوبیت بیشتری هستند. هر چند که در این الگوریتم‌ها برای تقریب این ماتریس فقط از اطلاعات گرادیان استفاده می‌شود. یکی از کاربردی‌ترین الگوریتم‌های شبه‌نیوتون در حل مسایل برنامه‌ریزی غیرخطی روش BFGS می‌باشد. این مقاله یک ایده‌ی جدید برای جستجوی خطی در روش BFGS ارائه داده و ثابت می‌کند که استفاده از این تکنیک، همگرایی سراسری را برای مسائل کلی بدون نیاز به هیچ شرط اضافه‌ای به دنبال خواهد داشت. در نهایت، کارایی الگوریتم پیشنهاد شده به صورت عددی مورد ارزیابی قرار گرفته است.
[1] Branke, J., et al. (2005). Practical Approaches to Multi-Objective Optimization, Internationales Begegnungs- und Forschungszentrum (IBFI).
[2] Broyden, C. G. (1970). The convergence of a class of double-rank minimization algorithms 1. general considerations.IMA Journal of Applied Mathematics,6(1): 76-90.
[3] Byrd, R. H. and J. Nocedal (1989). A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM Journal on Numerical Analysis, 26(3): 727-739.
[4] Davidon, W. C. (1991). Variable metric method for minimization. SIAM Journal on Optimization, 1(1): 1-17.
[5] Henningsen, A. and O. Toomet (2011). maxLik: A package for maximum likelihood estimation in R.Computational Statistics,26(3): 443-458.
[6] Powell, M. J. (1976). Some global convergence properties of a variable metric algorithm for minimization without exact line searches. Nonlinear programming, 9(1): 53-72.
[7] Mascarenhas, W. F. (2004). The BFGS method with exact line searches fails for non-convex objective functions.Mathematical Programming, 99(1): 49-61.
[8] Nocedal, J. and S. Wright (2006). Numericaloptimization, Springer Science & Business Media.
[9] G. Yuan, Z. Sheng, B. Wang, W. Hu, and C. Li (2018). The global convergence of a modified BFGS method for nonconvex functions, Journal of Computational and Applied Mathematics, 327: 274–294.
