تصحیح فرمول جستجوی خطی در روش BFGS برای رسیدن به همگرایی سراسری
محورهای موضوعی : آمارسید علیرضا حسینی دهمیری 1 , منصوره حمزه نژاد 2
1 - گروه ریاضی، دانشگاه ولی‌عصر(عج) رفسنجان، رفسنجان، ایران
2 - گروه ریاضی، دانشگاه ولی‌عصر(عج) رفسنجان، رفسنجان، ایران
کلید واژه: Newton method, BFGS method, unconstrained optimization, Quasi-Newton method, Global convergence,
چکیده مقاله :
مسائل برنامه‌ریزی غیرخطی در گروه مسائل پرکاربرد بهینه‌سازی در دنیای واقعی قرار دارند. تابع هدف این گونه از مسائل، علاوه بر غیرخطی بودن، در بیشتر موارد غیرمحدب است. این در حالی است که برای تضمین همگرایی سراسری در الگوریتم‌هایی که بر اساس روش نیوتن برای حل این مسائل پیشنهاد شده‌اند، عموماً شرط تحدب الزامی است. در این بین روش‌های شبه نیوتن بدلیل استفاده از تقریب ماتریس هسی یا وارون آن دارای محبوبیت بیشتری هستند. هر چند که در این الگوریتم‌ها برای تقریب این ماتریس فقط از اطلاعات گرادیان استفاده می‌شود. یکی از کاربردی‌ترین الگوریتم‌های شبه‌نیوتون در حل مسایل برنامه‌ریزی غیرخطی روش BFGS می‌باشد. این مقاله یک ایده‌ی جدید برای جستجوی خطی در روش BFGS ارائه داده و ثابت می‌کند که استفاده از این تکنیک، همگرایی سراسری را برای مسائل کلی بدون نیاز به هیچ شرط اضافه‌ای به دنبال خواهد داشت. در نهایت، کارایی الگوریتم پیشنهاد شده به صورت عددی مورد ارزیابی قرار گرفته است.
Nonlinear programming problems belong to the realm of commonly used optimization problems. In most cases, the objective function of such problems is non-convex. However, to guarantee global convergence in the algorithms proposed based on Newton's method to solve these problems, a convexity condition is generally required. Meanwhile, the quasi-Newton techniques are more popular because they use an approximation of the Hessian matrix or its inverse. However, in these algorithms, only gradient information is used to approximate this matrix. One of the most applicable quasi-Newton algorithms in solving nonlinear programming problems is the BFGS method. This paper presents a new idea for a linear search in the BFGS method. It proves that using this technique will lead to global convergence for general problems without the need for any additional conditions. Finally, the performance of the proposed algorithm is evaluated numerically.
[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.
