Convergence rate estimates for the gradient differential inclusion
Osman Güler · Optimization methods & software · 2005
Let f: H→ℝ∪{∞} be a proper, lower semi-continuous, convex function in a Hilbert space H. The gradient differential inclusion is x′(t)∈−∂ f(x(t)), x(0)=x, where and where ∂ f(x(t)) is the subdifferential of f at the point x(t). If f is Gâteaux differentiable, the inclusion is the differential equation x′(t)=−f′(x(t)), which is the continuous version of the steepest descent method for minimizing f on H. Even if f is not differentiable, the inclusion has a unique solution {x(t): t>0} which converges weakly to a minimizer of f if such a minimizer exists. In general, the inclusion can be interpreted as the the continuous version of the proximal point method for minimization f on H. There is a remarkable similarity between the behavior of the inclusion and its discrete counterparts as well in the methods used in both cases. As a simple consequence of our previous results on the proximal point method, we prove the convergence rate estimate f(x(t))−f(u)≤(1/2t)||u−x||2−(1/2t)||u−x(t)||2−(t/2)||∂ f 0(x(t))||2, where ∂ f 0(x(t)) is the least norm element of ∂ f(x(t)). If f has a minimizer x*, this implies f(x(t))−f(x*)=O(1/t), a result due to Brézis. If x(t) converges strongly to x*, we give a better estimate .