-
Previous Article
A modified Fletcher-Reeves-Type derivative-free method for symmetric nonlinear equations
- NACO Home
- This Issue
-
Next Article
Improved convergence properties of the Lin-Fukushima-Regularization method for mathematical programs with complementarity constraints
Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions
1. | State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, P.O. Box 2719, Beijing 100080 |
2. | Graduate School of Informatics, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto, 606-8501, Japan |
  This paper is dedicated to Professor Masao Fukushima on occasion of his 60th birthday.
References:
[1] |
R. Byrd and J. Nocedal, A tool for the analysis of quasi-Newton methods with application to unconstrained optimization, SIAM Journal on Numerical Analysis, 26 (1989), 727-739.
doi: 10.1137/0726042. |
[2] |
R. Byrd, J. Nocedal and Y. Yuan, Global convergence of a class of quasi-Newton methods on convex problems, SIAM Journal on Numerical Analysis, 24 (1987), 1171-1190.
doi: 10.1137/0724077. |
[3] |
M. H. Cheng and Y. H. Dai, A new sparse quasi-Newton update method, Research report, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 2010. |
[4] |
Y. H. Dai, Convergence properties of the BFGS algorithm, SIAM Journal on Optimization, 13 (2003), 693-701.
doi: 10.1137/S1052623401383455. |
[5] |
Y. H. Dai, A perfect example for the BFGS method, Research report, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 2010. |
[6] |
Y. H. Dai and N. Yamashita, Analysis of sparse quasi-Newton updates with positive definite matrix completion, Research report, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 2007. |
[7] |
J. E. Dennis, Jr. and J. J. Moré, Quasi-Newton method, motivation and theory, SIAM Review, 19 (1977), 46-89.
doi: 10.1137/1019005. |
[8] |
R. Fletcher, An optimal positive definite update for sparse Hessian matrices, SIAM Journal on Optimization, 5 (1995), 192-218.
doi: 10.1137/0805010. |
[9] |
M. Fukuda, M. Kojima, K. Murota and K. Nakata, Exploiting sparsity in semidefinite programming via matrix completion I: General frameworks, SIAM Journal on Optimization, 11 (2000), 647-674.
doi: 10.1137/S1052623400366218. |
[10] |
A. Griewank and Ph. L. Toint, On the unconstrained optimization of partially separable objective functions, in "Nonlinear Optimization 1981" (ed. M. J. D. Powell), Academic Press (London), (1982), 301-312. |
[11] |
D. H. Li and M. Fukushima, On the global convergence of BFGS method for nonconvex unconstrained optimization problems, SIAM Journal on Optimization, 11 (2001), 1054-1064.
doi: 10.1137/S1052623499354242. |
[12] |
D. H. Li and M. Fukushima, A modified BFGS method and its global convergence in nonconvex minimization, Journal of Computational and Applied Mathematics, 129 (2001), 15-35.
doi: 10.1016/S0377-0427(00)00540-9. |
[13] |
D. C. Liu and J. Nocedal, On the limited memory BFGS method for large scale optimization, Mathematical Programming, 45 (1989), 503-528.
doi: 10.1007/BF01589116. |
[14] |
W. F. Mascarenhas, The BFGS algorithm with exact line searches fails for nonconvex functions, Mathematical Programming, 99 (2004), 49-61.
doi: 10.1007/s10107-003-0421-7. |
[15] |
J. Nocedal, Updating quasi-Newton matrices with limited storage, Mathematics of Computation, 35 (1980), 773-782.
doi: 10.1090/S0025-5718-1980-0572855-7. |
[16] |
M. J. D. Powell, Some global convergence properties of a variable metric algorithm for minimization without exact line searches, in "Nonlinear Programming, SIAM-AMS Proceedings Vol. IX" (eds. R. W. Cottle and C. E. Lemke), SIAM, Philadelphia, PA, (1976), 53-72. |
[17] |
D. C. Sorensen, Collinear scaling and sequential estimation in sparse optimization algorithm, Mathematical Programming Study, 18 (1982), 135-159. |
[18] |
P. L. Toint, On sparse and symmetric matrix updating subject to a linear equation, Mathematics of Computation, 31 (1977), 954-961.
doi: 10.1090/S0025-5718-1977-0455338-4. |
[19] |
N. Yamashita, Sparse quasi-Newton updates with positive definite matrix completion, Mathematical Programming, 115 (2008), 1-30.
doi: 10.1007/s10107-007-0137-1. |
[20] |
Y. Yuan, "Numerical Methods for Nonlinear Programming," Shanghai Scientific & Technical Publishers, 1993 (in Chinese). |
show all references
References:
[1] |
R. Byrd and J. Nocedal, A tool for the analysis of quasi-Newton methods with application to unconstrained optimization, SIAM Journal on Numerical Analysis, 26 (1989), 727-739.
doi: 10.1137/0726042. |
[2] |
R. Byrd, J. Nocedal and Y. Yuan, Global convergence of a class of quasi-Newton methods on convex problems, SIAM Journal on Numerical Analysis, 24 (1987), 1171-1190.
doi: 10.1137/0724077. |
[3] |
M. H. Cheng and Y. H. Dai, A new sparse quasi-Newton update method, Research report, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 2010. |
[4] |
Y. H. Dai, Convergence properties of the BFGS algorithm, SIAM Journal on Optimization, 13 (2003), 693-701.
doi: 10.1137/S1052623401383455. |
[5] |
Y. H. Dai, A perfect example for the BFGS method, Research report, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 2010. |
[6] |
Y. H. Dai and N. Yamashita, Analysis of sparse quasi-Newton updates with positive definite matrix completion, Research report, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 2007. |
[7] |
J. E. Dennis, Jr. and J. J. Moré, Quasi-Newton method, motivation and theory, SIAM Review, 19 (1977), 46-89.
doi: 10.1137/1019005. |
[8] |
R. Fletcher, An optimal positive definite update for sparse Hessian matrices, SIAM Journal on Optimization, 5 (1995), 192-218.
doi: 10.1137/0805010. |
[9] |
M. Fukuda, M. Kojima, K. Murota and K. Nakata, Exploiting sparsity in semidefinite programming via matrix completion I: General frameworks, SIAM Journal on Optimization, 11 (2000), 647-674.
doi: 10.1137/S1052623400366218. |
[10] |
A. Griewank and Ph. L. Toint, On the unconstrained optimization of partially separable objective functions, in "Nonlinear Optimization 1981" (ed. M. J. D. Powell), Academic Press (London), (1982), 301-312. |
[11] |
D. H. Li and M. Fukushima, On the global convergence of BFGS method for nonconvex unconstrained optimization problems, SIAM Journal on Optimization, 11 (2001), 1054-1064.
doi: 10.1137/S1052623499354242. |
[12] |
D. H. Li and M. Fukushima, A modified BFGS method and its global convergence in nonconvex minimization, Journal of Computational and Applied Mathematics, 129 (2001), 15-35.
doi: 10.1016/S0377-0427(00)00540-9. |
[13] |
D. C. Liu and J. Nocedal, On the limited memory BFGS method for large scale optimization, Mathematical Programming, 45 (1989), 503-528.
doi: 10.1007/BF01589116. |
[14] |
W. F. Mascarenhas, The BFGS algorithm with exact line searches fails for nonconvex functions, Mathematical Programming, 99 (2004), 49-61.
doi: 10.1007/s10107-003-0421-7. |
[15] |
J. Nocedal, Updating quasi-Newton matrices with limited storage, Mathematics of Computation, 35 (1980), 773-782.
doi: 10.1090/S0025-5718-1980-0572855-7. |
[16] |
M. J. D. Powell, Some global convergence properties of a variable metric algorithm for minimization without exact line searches, in "Nonlinear Programming, SIAM-AMS Proceedings Vol. IX" (eds. R. W. Cottle and C. E. Lemke), SIAM, Philadelphia, PA, (1976), 53-72. |
[17] |
D. C. Sorensen, Collinear scaling and sequential estimation in sparse optimization algorithm, Mathematical Programming Study, 18 (1982), 135-159. |
[18] |
P. L. Toint, On sparse and symmetric matrix updating subject to a linear equation, Mathematics of Computation, 31 (1977), 954-961.
doi: 10.1090/S0025-5718-1977-0455338-4. |
[19] |
N. Yamashita, Sparse quasi-Newton updates with positive definite matrix completion, Mathematical Programming, 115 (2008), 1-30.
doi: 10.1007/s10107-007-0137-1. |
[20] |
Y. Yuan, "Numerical Methods for Nonlinear Programming," Shanghai Scientific & Technical Publishers, 1993 (in Chinese). |
[1] |
Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237 |
[2] |
Rouhollah Tavakoli, Hongchao Zhang. A nonmonotone spectral projected gradient method for large-scale topology optimization problems. Numerical Algebra, Control and Optimization, 2012, 2 (2) : 395-412. doi: 10.3934/naco.2012.2.395 |
[3] |
Hong Seng Sim, Chuei Yee Chen, Wah June Leong, Jiao Li. Nonmonotone spectral gradient method based on memoryless symmetric rank-one update for large-scale unconstrained optimization. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021143 |
[4] |
Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control and Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018 |
[5] |
Shummin Nakayama, Yasushi Narushima, Hiroshi Yabe. Memoryless quasi-Newton methods based on spectral-scaling Broyden family for unconstrained optimization. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1773-1793. doi: 10.3934/jimo.2018122 |
[6] |
Basim A. Hassan. A new type of quasi-newton updating formulas based on the new quasi-newton equation. Numerical Algebra, Control and Optimization, 2020, 10 (2) : 227-235. doi: 10.3934/naco.2019049 |
[7] |
Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial and Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149 |
[8] |
Gaohang Yu. A derivative-free method for solving large-scale nonlinear systems of equations. Journal of Industrial and Management Optimization, 2010, 6 (1) : 149-160. doi: 10.3934/jimo.2010.6.149 |
[9] |
Yigui Ou, Wenjie Xu. A unified derivative-free projection method model for large-scale nonlinear equations with convex constraints. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021125 |
[10] |
Boling Guo, Guoli Zhou. Finite dimensionality of global attractor for the solutions to 3D viscous primitive equations of large-scale moist atmosphere. Discrete and Continuous Dynamical Systems - B, 2018, 23 (10) : 4305-4327. doi: 10.3934/dcdsb.2018160 |
[11] |
Ke Wei, Jian-Feng Cai, Tony F. Chan, Shingyu Leung. Guarantees of riemannian optimization for low rank matrix completion. Inverse Problems and Imaging, 2020, 14 (2) : 233-265. doi: 10.3934/ipi.2020011 |
[12] |
Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103 |
[13] |
Danuta Gaweł, Krzysztof Fujarewicz. On the sensitivity of feature ranked lists for large-scale biological data. Mathematical Biosciences & Engineering, 2013, 10 (3) : 667-690. doi: 10.3934/mbe.2013.10.667 |
[14] |
Mahmut Çalik, Marcel Oliver. Weak solutions for generalized large-scale semigeostrophic equations. Communications on Pure and Applied Analysis, 2013, 12 (2) : 939-955. doi: 10.3934/cpaa.2013.12.939 |
[15] |
Philippe Bonneton, Nicolas Bruneau, Bruno Castelle, Fabien Marche. Large-scale vorticity generation due to dissipating waves in the surf zone. Discrete and Continuous Dynamical Systems - B, 2010, 13 (4) : 729-738. doi: 10.3934/dcdsb.2010.13.729 |
[16] |
Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing. Journal of Industrial and Management Optimization, 2014, 10 (1) : 113-129. doi: 10.3934/jimo.2014.10.113 |
[17] |
Suli Zou, Zhongjing Ma, Xiangdong Liu. Auction games for coordination of large-scale elastic loads in deregulated electricity markets. Journal of Industrial and Management Optimization, 2016, 12 (3) : 833-850. doi: 10.3934/jimo.2016.12.833 |
[18] |
Bo You, Chengkui Zhong, Fang Li. Pullback attractors for three dimensional non-autonomous planetary geostrophic viscous equations of large-scale ocean circulation. Discrete and Continuous Dynamical Systems - B, 2014, 19 (4) : 1213-1226. doi: 10.3934/dcdsb.2014.19.1213 |
[19] |
Masataka Kato, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Effect of energy-saving server scheduling on power consumption for large-scale data centers. Journal of Industrial and Management Optimization, 2016, 12 (2) : 667-685. doi: 10.3934/jimo.2016.12.667 |
[20] |
Bo You, Chunxiang Zhao. Approximation of stationary statistical properties of the three dimensional autonomous planetary geostrophic equations of large-scale ocean circulation. Discrete and Continuous Dynamical Systems - B, 2020, 25 (8) : 3183-3198. doi: 10.3934/dcdsb.2020057 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]