×

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