Resource-Aware Discretization of Accelerated Optimization Flows

We denote by ${\mathbb{R}}$ and $\mathbb{R}_{>0}$ the sets of real and positive real numbers, resp. All vectors are column vectors. We denote their scalar product by $\langle\cdot,\cdot\rangle$. We use $\left\lVert\cdot{}\right\rVert$ to denote the $2$-norm in Euclidean space. Given $\mu\in\mathbb{R}_{>0}$, a continuously differentiable function $f$ is $\mu$-strongly convex if $f(y)-f(x)\geq\langle\nabla f(x),y-x\rangle+\frac{\mu}{2}\left\lVert x-y\right\rVert^{2}$ for $x$, $y\in{\mathbb{R}}^{n}$. Given $L\in\mathbb{R}_{>0}$ and a function $f:X\rightarrow Y$ between two normed spaces $(X,\left\lVert\cdot{}\right\rVert_{X})$ and ($Y,\left\lVert\cdot{}\right\rVert_{Y}$), $f$ is $L$-Lipschitz if $\left\lVert f(x)-f(x^{\prime})\right\rVert_{Y}\leq L\left\lVert x-x^{\prime}\right\rVert_{X}$ for $x$, $x^{\prime}\in X$. The functions we consider here are continuously differentiable, $\mu$-strongly convex and have $L$-Lipschitz continuous gradient. We refer to the set of functions with all these properties by $\mathcal{S}_{\mu,L}^{1}({\mathbb{R}}^{n})$. A function $f:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}$ is positive definite relative to $x_{*}$ if $f(x_{*})=0$ and $f(x)>0$ for $x\in{\mathbb{R}}^{n}\setminus\{x_{*}\}$.

Our work builds on ideas from resource-aware control to develop discretizations of continuous-time accelerated flows. Here, we provide a brief exposition of its basic elements and refer to [24, 25] for further details.

Given a controlled dynamical system $\dot{p}=X(p,u)$, with $p\in{\mathbb{R}}^{n}$ and $u\in{\mathbb{R}}^{m}$, assume we are given a stabilizing continuous state-feedback $\mathfrak{k}:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}^{m}$ so that the closed-loop system $\dot{p}=X(p,\mathfrak{k}(p))$ has $p_{*}$ as a globally asymptotically stable equilibrium point. Assume also that a Lyapunov function $V:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}$ is available as a certificate of the globally stabilizing nature of the controller. Here, we assume this takes the form

for all $p\in{\mathbb{R}}^{n}$. Although exponential decay of $V$ along the system trajectories is not necessary, we restrict our attention to this case as it arises naturally in our treatment.

Suppose we are given the task of implementing the controller signal over a digital platform, meaning that the actuator cannot be continuously updated as prescribed by the specification $u=\mathfrak{k}(p)$. In such case, one is forced to discretize the control action along the execution of the dynamics, while making sure that stability is still preserved. A simple-to-implement approach is to update the control action periodically, i.e., fix $h>0$, sample the state as $\{p(kh)\}_{k=0}^{\infty}$ and implement

This approach requires $h$ to be small enough to ensure that $V$ remains a Lyapunov function and, consequently, the system remains stable. By contrast, in resource-aware control, one employs the information generated by the system along its trajectory to update the control action in an opportunistic fashion. Specifically, we seek to determine in a state-dependent fashion a sequence of times $\{t_{k}\}_{k=0}^{\infty}$, not necessarily uniformly spaced, such that $p_{*}$ remains a globally asymptotically stable equilibrium for the system

The main idea to accomplish this is to let the state sampling be guided by the principle of maintaining the same type of exponential decay (1) along the new dynamics. To do this, one defines triggers to ensure that this decay is never violated by prescribing a new state sampling. Formally, one sets $t_{0}=0$ and $t_{k+1}=t_{k}+\operatorname{step}(p(t_{k}))$, where the stepsize is defined by

We refer to the criteria as event-triggering or self-triggering depending on whether the evaluation of the function $b$ requires monitoring of the state $p$ along the trajectory of (2) (ET) or just knowledge of its initial condition $\hat{p}$ (ST). The more stringent requirements to implement event-triggering lead to larger stepsizes versus the more conservative ones characteristic of self-triggering. In order for the state sampling to be implementable in practice, the inter-event times $\{t_{k+1}-t_{k}\}_{k=0}^{\infty}$ must be uniformly lower bounded by a positive minimum inter-event time, abbreviated MIET. In particular, the existence of a MIET rules out the existence of Zeno behavior, i.e., the possibility of an infinite number of triggers in a finite amount of time.

Depending on how the evolution of the function $V$ is examined, we describe two types of triggering conditions¹¹1In both cases, for a given $z\in{\mathbb{R}}^{n}$, we let $p(t;\hat{p})$ denote the solution of $\dot{p}(t)=X(p(t),\mathfrak{k}(\hat{p}))$ with initial condition $p(0)=\hat{p}$.: {LaTeXdescription}

In this case, $b^{\operatorname{d}}$ is defined as an upper bound of the expression $\frac{d}{dt}V(p(t;\hat{p}))+\frac{\sqrt{\mu}}{4}V(p(t;\hat{p}))$. This definition ensures that (1) is maintained along (2);

In this case, $b^{\operatorname{p}}$ is defined as an upper bound of the expression $V(p(t;\hat{p}))-e^{-\frac{\sqrt{\mu}}{4}t}V(\hat{p})$. Note that this definition ensures that the integral version of (1) is maintained along (2). In general, the performance-based trigger gives rise to stepsizes that are at least as large as the ones determined by the derivative-based approach, cf. [26]. This is because the latter prescribes an update as soon as the exponential decay is about to be violated, and therefore, does not take into account the fact that the Lyapunov function might have been decreasing at a faster rate since the last update. Instead, the performance-based approach reasons over the accumulated decay of the Lyapunov function since the last update, potentially yielding longer inter-sampling times.

A final point worth mentioning is that, in the event-triggered control literature, the notion of resource to be aware of can be many different things, beyond the actuator described above, including the sensor, sensor-controller communication, communication with other agents, etc. This richness opens the way to explore more elaborate uses of the sampled information beyond the zero-order hold in (2), something that we also leverage later in our presentation.

In this section, we study the asymptotic convergence of heavy-ball dynamics with displaced gradient. Interestingly, for $a$ sufficiently small, this dynamics enjoys the same convergence properties as the dynamics (4), as the following result shows.

In this section we propose a discretization of the continuous heavy-ball dynamics based on resource-aware control. To do so, we employ the approaches to trigger design described in Section II-B on the dynamics $X^{a}_{\operatorname{hb}}$, whose forward-Euler discretization corresponds to the modified zero-order hold (8) of the heavy-ball dynamics.

Our starting point is the characterization of the asymptotic convergence properties of $X^{a}_{\operatorname{hb}}$ developed in Section IV-A. The trigger design necessitates of bounding the evolution of the Lyapunov function $V$ in (III.1) for the continuous-time heavy-ball dynamics with displaced gradient along its zero-order hold implementation. However, this task presents the challenge that the definition of $V$ involves the minimizer $x_{*}$ of the optimization problem itself, which is unknown (in fact, finding it is the ultimate objective of the discrete-time algorithm we seek to design). In order to synthesize computable triggers, this raises the issue of bounding the evolution of $V$ as accurately as possible while avoiding any requirement on the knowledge of $x_{*}$. The following result, whose proof is presented in Appendix A, addresses this point.

The importance of Proposition IV.4 stems from the fact that the triggering conditions defined by $b^{\operatorname{d}}_{\#}$, $\#\in\{\operatorname{ET},\operatorname{ST}\}$, can be evaluated without knowledge of the optimizer $x_{*}$. We build on this result next to establish an upper bound for the performance-based triggering condition.

Propositions IV.4 and IV.5 provide us with the tools to determine the stepsize according to the derivative- and performance-based triggering criteria, respectively. For convenience, and following the notation in (3), we define the stepsizes

for $\#\in\{\operatorname{ET},\operatorname{ST}\}$. Observe that, as long as $\hat{p}\neq p_{*}=[x_{*},0]^{T}$ and $0\leq a\leq a^{*}_{1}$, we have $C_{\#}(\hat{p};a)<0$ for $\#\in\{\operatorname{ST},\operatorname{ET}\}$ and, as a consequence, $b^{\operatorname{d}}_{\#}(\hat{p},0;a)<0$. The ET/ST terminology is justified by the following observation: in the ET case, the equation defining the stepsize is in general implicit in $t$. Instead, in the ST case, the equation defining the stepsize is explicit in $t$. Equipped with this notation, we define the variable-stepsize algorithm described in Algorithm 1, which consists of following the dynamics (8) until the exponential decay of the Lyapunov function is violated as estimated by the derivative-based ($\diamond={\operatorname{d}}$) or the performance-based ($\diamond={\operatorname{p}}$) triggering condition. When this happens, the algorithm re-samples the state before continue flowing along (8).

Here we characterize the convergence properties of the derivative- and performance-based implementations of the Displaced-Gradient Algorithm. In each case, we show that algorithm is implementable (i.e., it admits a MIET) and inherits the convergence rate from the continuous-time dynamics. The following result deals with the derivative-based implementation of Algorithm 1.