A Continuous-Time Perspective on Optimal Methods for Monotone Equation Problems
share
We study rescaled gradient dynamical systems in a Hilbert space ℋ, where implicit discretization in a finite-dimensional Euclidean space leads to high-order methods for solving monotone equations (MEs). Our framework can be interpreted as a natural generalization of celebrated dual extrapolation method <cit.> from first order to high order via appeal to the regularization toolbox of optimization theory <cit.>. More specifically, we establish the existence and uniqueness of a global solution and analyze the convergence properties of solution trajectories. We also present discrete-time counterparts of our high-order continuous-time methods, and we show that the p^th-order method achieves an ergodic rate of O(k^-(p+1)/2) in terms of a restricted merit function and a pointwise rate of O(k^-p/2) in terms of a residue function. Under regularity conditions, the restarted version of p^th-order methods achieves local convergence with the order p ≥ 2. Notably, our methods are optimal since they have matched the lower bound established for solving the monotone equation problems under a standard linear span assumption <cit.>.
READ FULL TEXT