Convergence Rates for Conditional Gradient Sequences Generated by Implicit Step Length Rules
Author:
- J. C. DunnJDJ. C. Dunn
- 1 September 1980
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Control and Optimization
- Vol. 18 (5) , 473-487
Abstract
Conditional gradient algorithms with implicit line minimization and Goldstein–Armijo step length rules are considered for the problem $\min _\Omega F$ with $\Omega $ a bounded convex subset of a real Banach space. When the Fréchet derivative $F'$ is uniformly continuous on $\Omega $, the iterates $x_n $ generated by any of the algorithms comprise an “extremizing” sequence in the sense that the quantity, $\langle {F'(x_n ),x_n } \rangle - \inf _{y \in \Omega } \langle {F'(x_n ),y} \rangle $, converges to zero as $n \to \infty $. This ensures that every limit point of $\{ x_n \} $ is an extremal, and for compact $\Omega $ it then follows that $\{ x_n \} $ converges to the set of extremals in $\Omega $. Weak counterparts of these results are also established. Convergence rate estimates are derived for convex F and Lipschitz continuous $F'$. These estimates are closely related to results obtained in an earlier investigation of two explicit step length formulas for conditional gradient methods. Once again, the growth rate of the function $a(\sigma ) = \inf \{ \rho = \langle {F'(\xi ),x - \xi } \rangle \mid x \in \Omega ,\| {x - \xi } \| \geqq \sigma \} $ at an extremal $\xi $, determines how rapidly the functional values $F(x_n )$ converge to $\inf _\Omega F$.
Keywords
This publication has 6 references indexed in Scilit:
- Rates of Convergence for Conditional Gradient Algorithms Near Singular and Nonsingular ExtremalsSIAM Journal on Control and Optimization, 1979
- An Historical Survey of Computational Methods in Optimal ControlSIAM Review, 1973
- On the continuity of the minimum set of a continuous functionJournal of Mathematical Analysis and Applications, 1967
- Minimization of functions having Lipschitz continuous first partial derivativesPacific Journal of Mathematics, 1966
- On Newton's methodNumerische Mathematik, 1965
- On Steepest DescentJournal of the Society for Industrial and Applied Mathematics Series A Control, 1965