یک روش تندترین کاهش بدون جستجوی خطی برای حل مسائل بهینه‌سازی نامقید
محورهای موضوعی : آمار
1 - دانشکده ریاضی، دانشگاه یزد، یزد، ایران
کلید واژه: Steepest descent method, Unconstrained optimization problem, Line search, Double parameter scaled quasi-Newton formula,
چکیده مقاله :
در این مقاله به حل مسئله بهینه سازی نامقید با استفاده از یک روش تندترین کاهش بدون استفاده از الگوریتم‌های جستجوی خطی میپردازیم. ابتدا یک فرمول شبه نیوتن مقیاس بندی شده دو پارامتری برای محاسبه تقریبی از ماتریس هسی ارائه می‌دهیم. تقریب به دست آمده از این فرمول، یک ماتریس معین مثبت است که در رابطه سکانت استاندارد صدق می‌نماید. همچنین نشان می‌دهیم که بزرگترین مقدار ویژه این ماتریس از تعداد متغیرهای مسئله بیشتر نخواهد بود. سپس با استفاده از این فرمول شبه نیوتن مقیاس بندی شده دو پارامتری، فرمول صریحی برای محاسبه طول گام در روش تندترین کاهش ارائه می‌شود و بنابراین این روش نیازی به استفاده از روش‌های تقریبی برای محاسبه طول گام نخواهد داشت. نتایج عددی به دست آمده از اجرای الگوریتم در محیط نرم افزاری متلب بر روی برخی مسائل بهینه سازی ارائه شده است. این نتایج کارایی روش ارائه شده نسبت به سایر روش‌های موجود را نشان می‌دهد.
In this paper, we solve unconstrained optimization problem using a free line search steepest descent method. First, we propose a double parameter scaled quasi Newton formula for calculating an approximation of the Hessian matrix. The approximation obtained from this formula is a positive definite matrix that is satisfied in the standard secant relation. We also show that the largest eigen value of this matrix is not greater than the number of variables of the problem. Then, using this double parameter scaled quasi Newton formula, an explicit formula for calculating the step length in the steepest descent method is presented and therefore, this method does not require the use of approximate methods for calculating step length. The numerical results obtained from the implementation of the algorithm in MATLAB software environment are presented for some optimization problems. These results show the efficiency of the proposed method in comparison with other existing methods.
[1] W. Cheng, D. Li. Spectral scaling bfgs method. Journal of Optimization Theory and Applications 146(2): 305–319 (2010)
[2] J. Barzilai, J.M. Borwein. Two-point step size gradient methods. IMA Journal of Numerical Analysis 8: 141–148 (1988)
[3] F. Biglari, M.A. Hassan, W.J. Leong. New quasi-Newton methods via higher order tensor models. Journal of Computational and Applied Mathematics 235(8): 2412–2422 (2011)
[4] F. Biglari, M. Solimanpur. Scaling on the spectral gradient method. Journal of Optimization Theory and Applications 158(2): 626–635 (2013)
[5] Y.H. Xiao, Q.Y. Wang, D. Wang. Notes on the Dai-Yuan-Yuan modified spectral gradient method. Journal of omputational and Applied Mathematics 234(10): 2986–2992 (2010)
[6] B. Zhou, L. Gao, Y.H. Dai. Gradient methods with adaptive step sizes. Computational Optimization and Applications 35(1): 69–86 (2006)
[7] H. Liu, Z. Liu, X. Dong. A new adaptive Barzilai and Borwein method for unconstrained optimization. Optimization Letters 12: 845–873(2018)
[8] C.D. Maranas, C.A. Floudas. A deterministic global optimization approach for molecular structure determination, Journal of Chemical Physics 100(2): 1247–1261 (1994)
