ISSN:
1432-0606
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract Convergence rates of Newton-Goldstein sequences are estimated for convex constrained minimization problems with singular solutionsξ, i.e., solutions at which the local quadratic approximationQ(ξ, x) to the objective functionF grows more slowly than ∥x − ξ∥2 for admissible vectorsx nearξ. For a large class of iterative minimization methods with quadratic subproblems, it is shown that the valuesr n =F(x n )−infΩ F are of orderO(n −1/3) at least. For the Newton—Goldstein method this estimate is sharpened slightly tor n =O(n −1/2) when the second Fréchet differentialF″ is Lipschitz continuous and the admissible set Ω is bounded. Still sharper estimates are derived when certain growth conditions are satisfied byF or its local linear approximation atξ. The most surprising conclusion is that Newton—Goldstein sequences can convergesuperlinearly to a singular extremalξ when〈F′(ξ), x − ξ〉 ≥ A∥x − ξ∥ v for someA 〉 0, somev ∈ (2,2.5) and allx in Ω nearξ, and that this growth condition onF′(ξ) is entirely natural for a nontrivial class of constrained minimization problems on feasible sets Ω =ℒ 1{[0,1],U} withU a uniformly convex set in ℝ d . Feasible sets of this kind are commonly encountered in the optimal control of continuous-time dynamical systems governed by differential equations, and may be viewed as infinite-dimensional limits of Cartesian product setsU k in ℝ kd . Superlinear convergence of Newton—Goldstein sequences for the problem (Ω,F) suggests that analogous sequences for increasingly refined finite-dimensional approximation (U kd ,F k ) to (Ω,F) will exhibit convergence properties that are in some sense “uniformly good” ink ask → ∞.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01449042
Permalink