American Institute of Mathematical Sciences

Advanced
  • 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
2011, 1(1): 61-69. doi: 10.3934/naco.2011.1.61

Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions

Yuhong Dai 1, and  Nobuo Yamashita 2,

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

Received  September 2010 Revised  September 2010 Published  February 2011

In this paper, we briefly review the extensions of quasi-Newton methods for large-scale optimization. Specially, based on the idea of maximum determinant positive definite matrix completion, Yamashita (2008) proposed a new sparse quasi-Newton update, called MCQN, for unconstrained optimization problems with sparse Hessian structures. In exchange of the relaxation of the secant equation, the MCQN update avoids solving difficult subproblems and overcomes the ill-conditioning of approximate Hessian matrices. A global convergence analysis is given in this paper for the MCQN update with Broyden's convex family assuming that the objective function is uniformly convex and its dimension is only two.
    This paper is dedicated to Professor Masao Fukushima on occasion of his 60th birthday.
Keywords: Quasi-Newton method, global convergence., large-scale optimization, positive definite matrix completion, sparsity.
Mathematics Subject Classification: Primary: 90C53, 90C0.
Citation: Yuhong Dai, Nobuo Yamashita. Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 61-69. doi: 10.3934/naco.2011.1.61
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.  Google Scholar

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

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

[4]

Y. H. Dai, Convergence properties of the BFGS algorithm, SIAM Journal on Optimization, 13 (2003), 693-701. doi: 10.1137/S1052623401383455.  Google Scholar

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

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

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

[8]

R. Fletcher, An optimal positive definite update for sparse Hessian matrices, SIAM Journal on Optimization, 5 (1995), 192-218. doi: 10.1137/0805010.  Google Scholar

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

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

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

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

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

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

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

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

[17]

D. C. Sorensen, Collinear scaling and sequential estimation in sparse optimization algorithm, Mathematical Programming Study, 18 (1982), 135-159.  Google Scholar

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

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

[20]

Y. Yuan, "Numerical Methods for Nonlinear Programming," Shanghai Scientific & Technical Publishers, 1993 (in Chinese). Google Scholar

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.  Google Scholar

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

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

[4]

Y. H. Dai, Convergence properties of the BFGS algorithm, SIAM Journal on Optimization, 13 (2003), 693-701. doi: 10.1137/S1052623401383455.  Google Scholar

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

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

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

[8]

R. Fletcher, An optimal positive definite update for sparse Hessian matrices, SIAM Journal on Optimization, 5 (1995), 192-218. doi: 10.1137/0805010.  Google Scholar

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

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

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

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

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

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

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

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

[17]

D. C. Sorensen, Collinear scaling and sequential estimation in sparse optimization algorithm, Mathematical Programming Study, 18 (1982), 135-159.  Google Scholar

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

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

[20]

Y. Yuan, "Numerical Methods for Nonlinear Programming," Shanghai Scientific & Technical Publishers, 1993 (in Chinese). Google Scholar

[1]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems - B, 2020, 25 (8) : 3183-3198. doi: 10.3934/dcdsb.2020057

 Impact Factor: 

Tools

Metrics

  • PDF downloads (68)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences