A quasi-Newton method with optimal R-order without independence assumption
Please always quote using this URN:urn:nbn:de:0296-matheon-3514
- Quasi-Newton methods based on least change secant updating formulas that solve linear equations $Ax=b$ in $n=\dim(x)=\dim(b)$ steps can be expected to solve corresponding smooth nonlinear systems $n$-step quadratically, i.e. with an $r$-order of $\rho = 2^{1/n} = 1 + 1/n +O(1/n^2)$. The best rate one can possibly expect on general problems is given by the positive root $\rho_n$ of $\rho^n(\rho -1)=1$, for which $\rho_n-1 = \ln(n)/n + O(1/n^2)$. To show that this upper bound is actually achieved one usually has to impose a priori some kind of linear independence condition on the sequence of steps taken by the quasi-Newton iteration in question. Without any such assumptions we establish in this paper the convergence order $\rho_n$ for the two-sided rank one formula proposed by Schlenkrich et al in \cite{SGW06}. It requires the evaluation of adjoint vectors, is invariant with respect to linear transformations on the variable domain and combines the properties of bounded deterioration and heredity.
Author: | Andreas Griewank, Sebastian Schlenkrich, Andrea Walther |
---|---|
URN: | urn:nbn:de:0296-matheon-3514 |
Referee: | Peter Deuflhard |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2006/06/09 |
Release Date: | 2006/06/09 |
Tag: | |
Institute: | Humboldt-Universität zu Berlin |
MSC-Classification: | 46-XX FUNCTIONAL ANALYSIS (For manifolds modeled on topological linear spaces, see 57Nxx, 58Bxx) / 46Nxx Miscellaneous applications of functional analysis [See also 47Nxx] / 46N10 Applications in optimization, convex analysis, mathematical programming, economics |
Preprint Number: | 340 |