Modify the linear search formula in the BFGS method to achieve global convergence.

Subject Areas : Statistics

S.A.R. Hosseini Dehmiry ¹ , M. Hamzehnejad ²

1 - Department of Mathematics, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran
2 - Department of Mathematics, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran

Received: 2018-02-18 Accepted : 2019-02-27 Published : 2019-12-22

Keywords: همگرایی سراسری, روش BFGS, بهینه‌سازی نامقید, روش‌شبه‌نیوتون, روش نیوتون,

Abstract :

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.

References:

 

[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.