Newton—Goldstein convergence rates for convex constrained minimization problems with singular solutions

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 − ξ∥² 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 Ω =ℒ ¹{[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 → ∞.