Monotone inclusions, acceleration, and closed-loop control. (English) Zbl 1539.37104
Summary: We propose and analyze a new dynamical system with a closed-loop control law in a Hilbert space \(\mathcal{H}\), aiming to shed light on the acceleration phenomenon for monotone inclusion problems, which unifies a broad class of optimization, saddle point, and variational inequality (VI) problems under a single framework. Given an operator \( A : \mathcal{H} \rightrightarrows \mathcal{H}\) that is maximal monotone, we propose a closed-loop control system that is governed by the operator \( I - (I + \lambda(t)A)^{-1}\), where a feedback law \(\lambda(\cdot)\) is tuned by the resolution of the algebraic equation \( \lambda(t) \| (I+\lambda(t)A)^{-1} x(t) - x(t) \|^{p-1} = \theta\) for some \(\theta > 0\). Our first contribution is to prove the existence and uniqueness of a global solution via the Cauchy-Lipschitz theorem. We present a simple Lyapunov function for establishing the weak convergence of trajectories via the Opial lemma and strong convergence results under additional conditions. We then prove a global ergodic convergence rate of \(O(t^{-(p+1)/2})\) in terms of a gap function and a global pointwise convergence rate of \(O(t^{-p/2})\) in terms of a residue function. Local linear convergence is established in terms of a distance function under an error bound condition. Further, we provide an algorithmic framework based on the implicit discretization of our system in a Euclidean setting, generalizing the large-step hybrid proximal extragradient framework. Even though the discrete-time analysis is a simplification and generalization of existing analyses for a bounded domain, it is largely motivated by the aforementioned continuous-time analysis, illustrating the fundamental role that the closed-loop control plays in acceleration in monotone inclusion. A highlight of our analysis is a new result concerning pth-order tensor algorithms for monotone inclusion problems, complementing the recent analysis for saddle point and VI problems.
MSC:
37N40 | Dynamical systems in optimization and economics |
37N35 | Dynamical systems in control |
90C25 | Convex programming |
90C60 | Abstract computational complexity for mathematical programming problems |
93B52 | Feedback control |
49M37 | Numerical methods based on nonlinear programming |
68Q25 | Analysis of algorithms and problem complexity |