错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Complexity Analysis Based on Tuning the Viscosity Parameter of the Su-Boyd-Candès Inertial Gradient Dynamics

  • Samir Adly,
  • Hedy Attouch

摘要

In a Hilbert setting, our study focuses on the dynamical system introduced by Su-Boyd-Candès as a low resolution ODE of Nesterov’s accelerated gradient method (NAG). This inertial system, denoted by ( A V D ) α ${\mathrm{(AVD)}}_{\alpha }$ , is driven by the gradient of the function f $f$ to be minimized, and is damped with an asymptotic vanishing coefficient of the form α / t $\alpha /t$ , with α 3 $\alpha \geq 3$ . Taking α $\alpha $ large enough plays a crucial role in the asymptotic convergence properties of the trajectories. For a general convex function f $f$ , taking α > 3 $\alpha >3$ guarantees the asymptotic convergence rate of the values o ( 1 / t 2 ) $o \left ( 1/t^{2} \right )$ , as well as the convergence of the trajectories towards optimal solutions. For strongly convex f $f$ , the asymptotic rate of convergence is of order 1 / t 2 α 3 $1/t^{\frac{2\alpha }{3}} $ , which increases with α $\alpha $ . To analyze the effect of the parameter α $\alpha $ in the convergence properties of ( A V D ) α ${\mathrm{(AVD)}}_{\alpha }$ , we show that a judicious time scaling of ( A V D ) α ${\mathrm{(AVD)}}_{\alpha }$ produces trajectories close to those of the continuous steepest descent method associated with f $f$ when α $\alpha $ is sufficiently large. This limiting process involves a singular perturbation property, as we move from a second-order evolution equation to a first-order one. This transition enables us to understand the change in the rate of convergence from 1 / t $1/t$ to 1 / t 2 $1/t^{2}$ between the steepest descent method and (NAG). Based on a complexity analysis over a finite time interval, new results are obtained regarding the optimal tuning of the parameter α $\alpha $ and the involved constants C α $C_{\alpha }$ in the estimations. Numerical experiments have been conducted to illustrate and confirm the theoretical results.