Estimation of Spectral Bounds in Gradient Algorithms

详细信息    查看全文

• 作者：L. Pronzato (1)
  A. Zhigljavsky (2)
  E. Bukina (1)
  
• 关键词：Estimation of leading eigenvalues ; Arcsine distribution ; Gradient algorithms ; Conjugate gradient ; Fibonacci numbers ; 65F10 ; 65F15
• 刊名：Acta Applicandae Mathematicae
• 出版年：2013
• 出版时间：October 2013
• 年：2013
• 卷：127
• 期：1
• 页码：117-136
• 全文大小：866KB
• 参考文献：1. Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141鈥?48 (1988) CrossRef
  2. Embrechts, P., Kl眉ppelberg, C., Mikosch, T.: Modelling Extremal Events. Springer, Berlin (1997) CrossRef
  3. Fischer, B., Reichel, L.: A stable Richardson iteration method for complex linear systems. Numer. Math. 54, 225鈥?42 (1988) CrossRef
  4. Forsythe, G.E.: On the asymptotic directions of the / s-dimensional optimum gradient method. Numer. Math. 11, 57鈥?6 (1968) CrossRef
  5. Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)
  6. Hall, P., Heyde, C.C.: Martingale Limit Theory and Its Applications. Academic Press, New York (1980)
  7. Hestenes, M.H., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. 49, 409鈥?36 (1952) CrossRef
  8. Krasnosel鈥檚kii, M.A., Krein, S.G.: An iteration process with minimal residues. Mat. Sb. 31(4), 315鈥?34 (1952) (in Russian)
  9. Meurant, G.: The block preconditioned conjugate gradient method on vector computers. BIT Numer. Math. 24, 623鈥?33 (1984) CrossRef
  10. Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia (1992) CrossRef
  11. Paige, C.C., Saunders, M.A.: Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal. 12(4), 617鈥?29 (1975) CrossRef
  12. Podvigina, O.M., Zheligovsky, V.A.: An optimized iterative method for numerical solution of large systems of equations based on the extremal property of zeros of Chebyshev polynomials. J. Sci. Comput. 12(4), 433鈥?64 (1976) CrossRef
  13. Pronzato, L., Zhigljavsky, A.: Gradient algorithms for quadratic optimization with fast convergence rates. Comput. Optim. Appl. 50(3), 597鈥?17 (2011) CrossRef
  14. Pronzato, L., Wynn, H.P., Zhigljavsky, A.: Renormalised steepest descent in Hilbert space converges to a two-point attractor. Acta Appl. Math. 67, 1鈥?8 (2001) CrossRef
  15. Pronzato, L., Wynn, H.P., Zhigljavsky, A.A.: Asymptotic behaviour of a family of gradient algorithms in 鈩?sup class="a-plus-plus"> / d and Hilbert spaces. Math. Program., Ser. A 107, 409鈥?38 (2006) CrossRef
  16. Pronzato, L., Wynn, H.P., Zhigljavsky, A.A.: A dynamical-system analysis of the optimum / s-gradient algorithm. In: Pronzato, L., Zhigljavsky, A.A. (eds.) Optimal Design and Related Areas in Optimization and Statistics, pp. 39鈥?0. Springer, Berlin (2009). Chap.聽3 CrossRef
  17. Saad, Y.: Practical use of polynomial preconditionings for the conjugate gradient method. SIAM J. Sci. Stat. Comput. 6(4), 865鈥?81 (1985) CrossRef
  18. Saad, Y.: Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics, Philadelphia (2008)
  19. Slater, B.: Gaps and steps for the sequence / n胃 mod 1. Math. Proc. Camb. Philos. Soc. 63, 1115鈥?123 (1967) CrossRef
  20. Tal-Ezer, H.: Polynomial approximation of functions of matrices and applications. J. Sci. Comput. 4(1), 25鈥?0 (1989) CrossRef
  21. van der Vorst, H.A.: Iterative Methods for Large Linear Systems. Utrecht University, Utrecht (2000)
  22. Zhigljavsky, A., Pronzato, L., Bukina, E.: An asymptotically optimal gradient algorithm for quadratic optimization with low computational cost. Optim. Lett. (2012). doi:10.1007/s11590-012-0491-7
  
• 作者单位：L. Pronzato (1)
  A. Zhigljavsky (2)
  E. Bukina (1)
  
  1. Laboratoire I3S, B芒t. Euclide, Les Algorithmes, CNRS/Universit茅 de Nice-Sophia Antipolis, 2000 route des lucioles, BP 121, 06903, Sophia Antipolis cedex, France
  2. School of Mathematics, Cardiff University, Senghennydd Road, Cardiff, CF24 4YH, UK
  
• ISSN：1572-9036

文摘

We consider the solution of linear systems of equations Ax=b, with A a symmetric positive-definite matrix in 鈩?sup class="a-plus-plus"> n脳n , through Richardson-type iterations or, equivalently, the minimization of convex quadratic functions (1/2)(Ax,x)鈭?b,x) with a gradient algorithm. The use of step-sizes asymptotically distributed with the arcsine distribution on the spectrum of A then yields an asymptotic rate of convergence after k<n iterations, k鈫掆垶, that coincides with that of the conjugate-gradient algorithm in the worst case. However, the spectral bounds m and M are generally unknown and thus need to be estimated to allow the construction of simple and cost-effective gradient algorithms with fast convergence. It is the purpose of this paper to analyse the properties of estimators of m and M based on moments of probability measures 谓 k defined on the spectrum of A and generated by the algorithm on its way towards the optimal solution. A precise analysis of the behavior of the rate of convergence of the algorithm is also given. Two situations are considered: (i)聽the sequence of step-sizes corresponds to i.i.d. random variables, (ii)聽they are generated through a dynamical system (fractional parts of the golden ratio) producing a low-discrepancy sequence. In the first case, properties of random walk can be used to prove the convergence of simple spectral bound estimators based on the first moment of 谓 k . The second option requires a more careful choice of spectral bounds estimators but is shown to produce much less fluctuations for the rate of convergence of the algorithm.