Superlinear convergence of nonlinear conjugate gradient method and scaled memoryless BFGS method based on assumptions about the initial point. (English) Zbl 1433.90192
Summary: The Perry nonlinear conjugate gradient method and scaled memoryless BFGS method are two quasi-Newton methods for unconstrained minimization. All convergence theory in the literature assume existence of a minimizer and bounds on the objective function in a neighbourhood of the minimizer. These conditions cannot be checked in practice. The motivation of this work is to derive a convergence theory where all assumptions can be verified, and the existence of a minimizer and its superlinear rate of convergence are consequences of the theory. Only the basic versions of these methods without line search are considered. The theory is simple in the sense that it contains as few constants as possible.
MSC:
| 90C53 | Methods of quasi-Newton type |
| 65K05 | Numerical mathematical programming methods |
| 90C30 | Nonlinear programming |
Keywords:
Perry nonlinear conjugate gradient; scaled memoryless BFGS; unconstrained optimization; quasi-Newton methodSoftware:
SCALCGReferences:
| [1] | Ciarlet, P. G., Linear and Nonlinear Functional Analysis with Applications (2013), SIAM: SIAM Philadelphia · Zbl 1293.46001 |
| [2] | Nocedal, J.; Wright, S. J., Nonlinear Optimization (2006), Springer: Springer New York · Zbl 1104.65059 |
| [3] | Perry, A., A modified conjugate gradient algorithm., Oper. Res., 26, 49, 1073-1078 (1978) · Zbl 0419.90074 |
| [4] | Yamashita, N., Sparse quasi-Newton updates with positive definite matrix completion, Math. Prog., 115, 1-30 (2008) · Zbl 1151.90059 |
| [5] | Andrei, N., Scaled conjugate gradient algorithms for unconstrained optimization, Comput. Optim. Appl., 38, 401-416 (2007) · Zbl 1168.90608 |
| [6] | S.H. Lui, S. Nataj, Superlinear convergence of the methods of Broyden and BFGS based on assumptions about the initial point, Submitted for publication (2019). · Zbl 1433.90192 |
| [7] | Nataj, S., Topics in quasi-Newton and space-time spectral methods (2019), University of Manitoba, Ph.D. thesis |
| [8] | Dennis, J. E.; Schnabel, R., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1996), SIAM: SIAM Philadelphia · Zbl 0847.65038 |
| [9] | Kato, T., A Short Introduction to Perturbation Theory for Linear Operators (1982), Springer-Verlag: Springer-Verlag New York · Zbl 0493.47008 |
| [10] | Dai, Y. H.; Liao, L. Z., New conjugacy conditions and related nonlinear conjugate gradient methods, Appl. Math. Optim., 43, 87-101 (2001) · Zbl 0973.65050 |
| [11] | Yao, S.; He, D.; Shi, L., An improved Perry conjugate gradient method with adaptive parameter choice, Numer. Alg., 78, 1255-1269 (2018) · Zbl 1396.65099 |
| [12] | Oren, S. S.; Luenberger, D. G., Self-Scaling variable metric (SSVM) algorithms, Part I: criteria and sufficient conditions for scaling a class of algorithms, Manag. Sci., 4, 20, 845-862 (1974) · Zbl 0316.90064 |
| [13] | Oren, S. S.; Spedicato, E., Optimal conditioning of self-scaling variable metric algorithms, Math. Program., 10, 70-90 (1976) · Zbl 0342.90045 |
| [14] | Babaie-Kafaki, S., A modified scaling parameter for the memoryless BFGS updating formula, Numer. Alg., 72, 425-433 (2016) · Zbl 1342.90227 |
| [15] | Decker, D. W.; Kelley, C. T., Broyden’s method for a class of problems having singular jacobian at the root, SIAM J. Numer. Anal., 22, 3, 566-574 (1985) · Zbl 0583.65022 |
| [16] | Lewis, A. S.; Overton, M. L., Nonsmooth optimization via quasi-Newton methods, Math. Prog., 141, 135-163 (2013) · Zbl 1280.90118 |
| [17] | Qi, L.; Sun, J., A nonsmooth version of Newton’s method, Math. Program, 58, 353-367 (1993) · Zbl 0780.90090 |
| [18] | Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and Real Computation (1998), Springer-Verlag: Springer-Verlag New York |
| [19] | Yakoubsohn, J. C., A class of methods for solving nonlinear simultaneous equations, J. Complexity, 15, 239-281 (1999) · Zbl 0944.65061 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
