Article Sidebar

Submitted
Apr 26, 2017
Published
Apr 1, 2012
Download
PDF
Statistic
Read Counter : 540 Download : 268

Main Article Content

Abstract

Based on the idea of maximum determinant positive definite matrix completion, Yamashita proposed a sparse quasi-Newton update, called MCQN, for unconstrained optimization problems with sparse Hessian structures. Such an MCQN update keeps the sparsity structure of the Hessian while relaxing the secant condition. In this paper, we propose an alternative to the MCQN update, in which the quasi-Newton matrix satisfies the secant condition, but does not have the same sparsity structure as the Hessian in general. Our numerical results demonstrate the usefulness of the new MCQN update with the BFGS formula for a collection of test problems. A local and superlinear convergence analysis is also provided for the new MCQN update with the DFP formula.

 

 

Keywords

Large-scale Matrix completion Quasi-Newton methods Secant condition Sparsity Unconstrained optimization.

Article Details

References

  1. BYRD, R. and NOCEDAL, J. 1989. A tool for the analysis of quasi-Newton methods with application to unconstrained optimization. SIAM Journal on Numerical Analysis, 26: 727-739.
  2. DAI, Y.H. and YAMASHITA, N. 2007. Analysis of sparse quasi-Newton updates with positive definte matrix completion. Research report, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing.
  3. DENNIS, J.E. and SCHNABEL, R.B. 1983. Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall Inc., New Jersey.
  4. FLETCHER, R. 1995. An optimal positive definite update for sparse Hessian matrices. SIAM Journal on Optimization, 5: 192-218.
  5. FUKUDA, M., KOJIMA, M., MUROTA, K. and NAKATA, K. 2000. Exploiting sparsity in semidefinite programming via matrix completion I: General frameworks. SIAM Journal on Optimization, 11: 647-674.
  6. GRIEWANK, A. and TOINT, Ph.L. 1982a. Partitioned variable metric updates for large structure optimization problems. Numerische Mathematik, 39: 119-137.
  7. GRIEWANK, A. and TOINT, Ph.L. 1982b. Local convergence analysis of partitioned quasi-Newton updates. Numerische Mathematik, 39: 429-448.
  8. GRIEWANK, A. and TOINT, Ph.L. 1984. Numerical experiments with partially separable optimization problems. Numerical Analysis: Proceedings Dundee 1983 (Lecture Notes in Mathematics 1066) (D.F. GRIFFITHS, ed.), Springer Verlag, (Berlin). Pp. 203-220.
  9. GOULD, N.I.M. and TOINT, Ph.L. 2003. CUTEr, a constrained and unconstrained testing environment: revisited. ACM Trans. Math. Softw., 29: 373-394.
  10. LIU, D.C. and NOCEDAL, J. 1989. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45: 503-528.
  11. MORÉ, J.J., GARBOW, B.S. and HILLSTROM, K.E. 1981. Testing Unconstrained Optimization Software. ACM Trans. Math. Softw., 7: 17-41.
  12. NOCEDAL, J. 1980. Updating quasi-Newton matrices with limited storage. Mathematics of Computation, 35: 773-782.
  13. NOCEDAL, J. and WRIGHT, S.J. 1999. Numerical Optimization, Springer, New York.
  14. SORENSEN, D.C. 1982. Collinear scaling and sequential estimation in sparse optimization algorithm. Mathematical Programming Study, 18: 135-159.
  15. TOINT, Ph.L. 1977. On sparse and symmetric matrix updating subject to a linear equation. Mathematics of Computation, 31: 954-961.
  16. YAMASHITA, N. 2008. Sparse quasi-Newton updates with positive definite matrix completion. Mathematical Programming, 115: 1-30.