An asymptotically optimal gradient algorithm for quadratic optimization with low computational cost |
| |
Authors: | Anatoly Zhigljavsky Luc Pronzato Elena Bukina |
| |
Affiliation: | 1. School of Mathematics, Cardiff University, Cardiff, CF24 4YH, UK 2. Laboratoire I3S, CNRS-UNS, 2000 route des Lucioles, B.P. 121, 06903, Sophia Antipolis, France
|
| |
Abstract: | We consider gradient algorithms for minimizing a quadratic function in ${mathbb{R}^n}$ with large n. We suggest a particular sequence of step-sizes and demonstrate that the resulting gradient algorithm has a convergence rate comparable with that of Conjugate Gradients and other methods based on the use of Krylov spaces. When the matrix is large and sparse, the proposed algorithm can be more efficient than the Conjugate Gradient algorithm in terms of computational cost, as k iterations of the proposed algorithm only require the computation of O(log k) inner products. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|