Ansys Whiplash Simulation

Whiplash Gradient Descent Dynamics

Subhransu S. Bhattacharjee∗and Ian R. Petersen∗.

Abstract

In this paper, we propose the Whiplash Inertial Gradient dynamics, a closed-loop optimization method that utilises gradient information, to find the minima of a cost function in finite-dimensional settings. We introduce the symplectic asymptotic convergence analysis for the Whiplash system for convex functions. We also introduce relaxation sequences to explain the non-classical nature of the algorithm and an exploring heuristic variant of the Whiplash algorithm to escape saddle points, deterministically. We study the algorithm’s performance for various costs and provide a practical methodology for analyzing convergence rates using integral constraint bounds and a novel Lyapunov rate method. Our results demonstrate polynomial and exponential rates of convergence for quadratic cost functions.

Index Terms

Gradient descent; Feedback systems; Finite-dimensional optimization; Non-linear dynamics; Lyapunov Method; Unconstrained optimization; Heuristic Optimization

1. Introduction

In this paper, we study the continuous optimization of finite-dimensional, unconstrained problems. We revisit classical optimization theories at the heart of popular deep learning algorithms. While studying these algorithms, we consider finite-dimensional global minimization problems with optima at x∗∈X, such that in finite dimension

X∈Rd F(X),

where f : Rd 7→R. These problems arise in fields such as deep learning, economics, and physics. With stochastic gradient approaches facing information bottlenecks , it is important to revisit deterministic approaches to understand ways to improve modern optimization tools from both practical and theoretical perspectives. Second- order methods which are significantly faster often tend to be computationally infeasible. Thus, we look back at first-order gradient methods which are computationally cheap and deterministic in nature.

Treating optimization algorithms as differential equations have been done in the past, where the stable points of the gradient flow system are the optimal points of the cost function . In our approach, we make use of non-linear systems theory frameworks to analyze algorithms in continuous-time as well as tuning their behaviour in discrete-time in order to introduce novel methods with wider practicality in the context of systems theory and numerical analysis. In order to systematise the treatment we primarily consider the gradient function as the black box oracle for continuous functions introduced by Nemirovsky .

A. Motivation

In the field of continuous optimization, black box models are prevalent in settings with scarce computational resources where learning about the global geometry of a function is not feasible. In most situations, a descent direction is necessary for a gradient descent method, making the computation of a function’s gradient necessary.

Beyond the computational complexities involved in finding the gradient of the function itself, black box methods allow for finding mathematically optimal convergence of iterative processes used for optimization. While global optimization is the true goal for such methods, the optimization of convex functions is inherently simpler because finding a single minimum within a comparatively uniform geometry is achievable using just the gradient information.

2

In black box methods, we consider computational models that make queries to an oracle that contain a finite- dimensional vector map of the entire linear span of gradients of a cost function . While various methods of convex optimization has evolved, including the optimal convex method, by accelerating the process, as shown by Nesterov , it still happens to be an area of active research. One of the reasons for the use of black box models in continuous optimization is to handle the variety of non-convex problems encountered in the context of deep learning and robotics. Non-convex problems require a diverse set of approaches, but assuming local convexity is the predominant way to prove convergence in most scenarios. While modern optimization uses stochastic methods to solve such problems , deterministic methods are constructive when it comes to designing new methods for optimization, as the convergence analysis is far simpler.

Treating optimization methods as dynamical systems allows for tuning the parameters in order to scale the flow leading to faster convergence , which can later be converted to discrete algorithms using discretization methods. A variational approach developed by Wilson et al. describes a generalized Lyapunov analysis framework for continuous-time systems. They showed that this technique of estimate sequences is equivalent to a family of Lyapunov functions in both continuous and discrete-time. This framework has led to the use of carefully designed time-scaled energy functions as a standard method to prove convergence rates for optimization algorithms, which can be studied as continuous-time inertial gradient flow dynamical systems. Shi et al.

demonstrate that it is impractical to use discrete schemes to find discrete Lyapunov functions. Since, Su et al. showed the Nesterov’s method had a dynamical system equivalent, we know that treating optimization algorithms as dynamical systems make them easier to analyse their properties in high-resolution. Although it is much more feasible in continuous time, the task of finding such energy functions is nevertheless complicated.

Depending upon the structure of the terms involved (often such terms are time-varying and non-linear), and can only be derived vaguely using physical energy-based motivations. As a method to bypass this problem, Attouch et al. introduced a closed-loop method as a heuristic design based on physical analogies. They used a parametric manufactured solution for a particular cost function to consider a specific family of dynamical systems. However, this method is limited from a control-theoretic perspective as it does not provide any energy function to prove the cost function’s convergence rate.

The task of finding appropriate Lyapunov functions becomes challenging for closed-loop ODEs, which use damping coefficients because the damping terms depend on the system’s dynamics and not just on the function, leading to non-classical behavior such as accelerated phases followed by attenuating oscillations. Our study aims to provide a generalized numerical energy-based framework to find the strength of convergence for unconstrained convex optimization problems using a certain class of closed-loop gradient flow control systems using nonlinear feedback systems theory.

B. Contribution

This paper is an extended culmination of the conference papers: and . In , we introduced the Whiplash Inertial Gradient dynamics as born out of the motivation to treat optimization algorithms as dynamical systems and perform control system analyses to find a novel method that is non-classical in nature from the accelerated gradient methods. It is significantly faster than other deterministic algorithms by a magnitude of 105 for the same choice of step-size for the Rosenbrock’s function. In , we introduced relaxation sequences, which defined the characteristics of the Whiplash dynamics in discrete-time and the novel convergence rate methodology, the Lyapunov Rate method, which is an alternative to finding convergence rates using complicated Lyapunov arguments which are difficult to find. To accomplish this, we introduce for convex functions, an asymptotic convergence framework built on certain generalised assumptions which allow for proving the bounded nature of the terms of the Lyapunov function, by exploiting the bounded nature of the globally asymptotic system’s solutions. We have shown numerical convergence results for this method, verified using the Whiplash inertial gradient system both in scalar and vector settings for quadratic cost functions.

In this paper, we add to the combined literature presented in the earlier papers and integrate them cohesively geared towards the numerical analysis methods and the novel relaxation sequence methods. Beyond that the

Contributions Of This Paper Are:

1) Numerical results involving near saddle point behaviors and numerical convergence for multidimensional

3

functions have been introduced in §3-D, adding to the previous numerical results1 already introduced for convex costs and Rosenbrock’s function. 2) In addition to the previously introduced results, we have also introduced multiple new lemmas (4, 8, 9) and theorems (2, 4, 5) that explain the concept of relaxation sequences (in §4-B), asymptotic loose bound (in §5-A) and numerical rates (§5-D), as well as justifications to the results obtained which were not found in the previous papers.

3) Finally, we have introduced the Whiplash exploration algorithm in §3-E, which uses a momentum sequence based stopping criterion and uses a heuristic termination and restart scheme to drive out of saddle points by exploiting both the first and zeroth order oracles.

C. Organisation

This paper has been structured into five more sections going forward. Section 2 discusses the preliminaries and notations necessary to understand the work, including basic properties and prerequisites in the field of convex analysis. In Section 3, we have introduced the Whiplash gradient descent method - the formulation, discretization, the algorithm, and numerical results in a variety of scenarios. We also introduce the novel Whiplash exploration algorithm motivated from the numerical results and insights obtained from the behaviour of naive methods. This algorithm is heuristic and deterministic and escapes saddle points. In Section 4, we introduce the convergence analyses, including various theoretical results to showcase the convergence rates.

We also introduce our novel relaxation sequences for L-smooth functions and their characteristics like the absolute convergence. In Section 5, we introduce the numerical convergence analysis (envelope method) of the closed-loop gradient flow systems by introducing an asymptotic loose bound (which acts as an extension of the O notation), an integral anchor method and the Lyapunov Rate method (already introduced in ). We provide a verification of our analysis for the Whiplash gradient descent dynamics using this methodology. In Section 6, we conclude our exposition by discussing the shortcomings of our approach, and some areas of future work in the field of global optimization using the control framework.

A. Preliminaries

A central aspect of analyzing gradient-based learning methods is to make necessary assumptions for a class of problems. One such assumption is the Lipschitz continuity of the gradient of the cost function, where there exists a constant L, termed as the Lipschitz constant, such that:

(1)

where ∥.∥indicates the ℓ2 or the Euclidean norm. We assume this condition for our cost functions throughout our analysis unless specified otherwise. When we discuss iterative gradient schemes in optimization, a sufficient condition for learning the gradient of such a cost function is to take a small enough step-size s such that:

(2)

We assume the cost function f(x) is such that f : Rd 7→R is a twice continuously differentiable convex function

Such That For All Ε ∈[0, 1] :

f(ϵx + (1 −ϵ)y) ≤ϵf(x) + (1 −ϵ)f(y).

(3)

This relation implies that Jensen’s inequality holds f(y) ≥f(x) + ⟨∇f(x), y −x⟩.

(4)

Rearranging (4), we have the global under-estimator of the convex function f(x) where both x, y ∈R , we

F(X) −F(Y) ≤⟨∇F(X), X −Y⟩

.

(5)

1Unless mentioned otherwise, the x-axis of all graphs denotes time in seconds. All numerical experiments can be found here.

4

For L-smooth convex functions (which have Lipschitz continuous gradient), where we choose the step-size as

F(Y) ≤F(X) + ⟨∇F(X), Y −X⟩+ L

2 ∥y −x∥2.

(6)

We will additionally consider the Polyak-Łojasiewicz (PŁ) inequality, which implies weak invexity , which is a local criterion of strict convexity. If we prove convergence for the PŁ condition, it would naturally hold for a stronger convexity criterion. The PŁ inequality is satisfied if the following holds for some λ > 0 and every

F(X) −F ∗≤1

2λ∥∇f(x)∥2.

(7)

We use the Cauchy-Schwarz and mean value theorems in our study, both of which can be found in preliminary section of .

B. Notation

We represent the set of all real numbers as R and the positive real sets as R+ = {x ∈R | x ≥0} and

R+

∗= {x ∈R | x > 0}. We represent the superior limit as lim. We use the asymptotic Landau notations O and o, which denotes the loose and strict asymptotic upper bounds , defined for t0 ∈[0, ∞) respectively for the



.

A. Formulation

The Whiplash Inertial Gradient descent design was inspired by a physical understanding of the dynamical system, which involves control using its momentum as developed by Su et al. , where they model the Nesterov scheme as an ODE. Further generalizations as developed by Attouch et al. , using a Hessian-driven approach and Wibisono et al. for the formulation of a variational approach using time-scaling lead to the

Simplified Inertial Gradient Dynamical System:

¨X + γ(t) ˙X + ∇f(X) = 0.

(10)

In , closed-loop control is considered using multiple scenarios with a damping constant of the form γ = r | ˙x|p−2, where p and r are positive constants (control parameters) and ˙x is the velocity. However, the simulation results we obtained for this algorithm were unsatisfactory for minimizing non-convex functions. We

Made Two Particular Observations:

1) The damping function did not adequately stabilize the system over long intervals for various values of p and r. This inspired us to use the control parameter r as t (time) and p = 4. 2) The lack of stability of the system over large intervals of time led us to look at the system as a linear time-variant system and to perform a corresponding pole placement. This required adding a marginal value to the damping to ensure a lower bound on the damping at t = 0, such that the damping term never disappears, because that leads to lack of attenuation as the system approaches the minima.

(11)

where the Hessian ∇2f(X) is of the objective function at the minima X = X∗, we thus look at the eigenvalues for the linear time-variant system matrix corresponding to (11) to understand its convergence rate motivated by

5

Figure 1. Whiplash control system block diagram. the approach in . For this purpose, we define a new system with state y for the underlying linearised state

Space System ˙X = A X, Which Is Given As:

y = x e−ηt, η > 0 .

Which In Matrix Form Can Be Written As:

˙y = (A −ηI) y.

(14)

The minimum real part of the eigenvalues of the system (14) can be written as:

(15)

which indicates an exponential convergence rate of at least η. Finally, we redefine the damping γ = K + t∥˙x∥2. We choose the term K = 1 for the damping coefficient. Note that the choice of K = 1 is because using K > 1 leads to unwanted damping in implementation. Our motivation for the choice of K = 1 was inspired by the Heavy ball dynamical system, as in at t = 0, the system essentially behaves as a Heavy Ball system. As we know from , for values K < 1, the convergence rate is slower because of the unwanted oscillations due to an unstable pole at t = 0. Hence, the value of K acts as a marginal value for the safe placement of the pole.

Thus, we arrive at our hybrid gradient descent optimization method, which we shall refer to as the whiplash

Inertial Gradient Optimization Method:

¨X + (1 + t || ˙X||2 ) ˙X + ∇f(X) = 0.

(16)

A block diagram for this system is shown in Figure: 1. The damping of the system for convex costs is as shown in figure: 2, with respect to time2.

B. Discretisation & Physical Model

The discretisation used is the semi-implicit or symplectic Euler method . Using a discrete-time step s and sampling period t ≈k√s, we obtain a two-state recursive estimate of the acceleration and velocity as shown 2The unique graph of the damping led to the nomenclature of the system as “Whiplash”.

6

Figure 2. Damping of the dynamics with respect to time for convex costs. Figure 3. Description of the whiplash gradient descent method. below as the equivalent of the Hamiltonian flow for the state-space, given as:

,

1 + t || ˙X||2 ≈1 + k√s||vk||2.

(17)

Now, we modify (16) to add a fixed mass to the system, which has been considered unit magnitude up until this point. The choice of mass that we shall make is m =

1

√s. The idea of introducing this mass in inertial gradient flow methods while discretizing them has been inspired by selective mass scaling in finite element methods , where the iterative process can be scaled by choosing an effective mass. The rationale is that since the discrete-time method depends heavily on the step size, it will take much longer to converge for smaller step sizes. Hence, to counter this effect, we introduce a fixed mass, which scales the dynamics depending on the step size. Upon making these substitutions and modifications to (16), as a model of the second order damped oscillator, with no external forces or perturbation, and a potential function g(x), mass m > 0 and damping

7

Figure 4. Physical model of the whiplash gradient descent optimization method.

+ (1 + K√S||Vk||2) Vk

√s + ∇f(xk) = 0.

Vk+1 = (1 −√S −Ks Vt

k · vk)vk −s∇f(xk) .

(20)

Now, we consider the symplectic approximation for the Lyapunov stable system such that ∥˙x(t)∥→0 as t →∞. This implies that ∥vk∥→0 as k →∞. Therefore, we introduce zk = xk −xk−1 = √svk−1. For asymptotic analyses, there is no difference between the sequences zk and vk asymptotically as

K→∞∥Zk+1 −Vk∥= Lim

k→∞|√s −1|∥vk∥= 0.

(21)

We may consider this as two transforms. First as a scaling of the system, followed by a backward recursion:

√S

(x(k√s) −x((k −1)√s)).

(22)

This trick simplifies our system’s updates while keeping intact the geometry of the dynamical system and does not change the global nature of the system’s convergence. This particular design choice for the algorithm simplifies the computation and makes discrete-time analyses of convergence considerably easier. We finally

(23)

where condition (2) holds. The whiplash method generates the momentum of the cost function to scale its next move in the discrete iteration. Figure: 3 provides a representation of the algorithm of (23). We can model the whiplash gradient descent as a physical system, consisting of mass m =

√S, Where S > 0 (Is The Step-Size Of

the algorithm), in a fluid of damping constant c = 1 as shown in Figure: 4. We can model the oracle as a spring of varying restoring force −∇f(x) and the non-linear damping as an adaptive damper, connected by rigid inextensible links.

8

Figure 5. A study of performance of the whiplash gradient descent for increasing condition numbers: κ = 1 (top left), κ = 10 (top right), κ = 100 (bottom left), κ = 1000 (bottom right).

C. Naive & Momentum-Based Stopping Algorithms

This discrete-time scheme (23) can be translated to the following algorithm (1) using a step-size s and n iterations, with initial starting point x0 and final point xn. Unlike classical gradient descent algorithms, this algorithm does not use any hyper-parameters. Instead, it uses a simple two-step assignment to update the discrete-time damping in every iteration. The zeroth step of the iteration x1 is a gradient descent step which assigns the initial momentum for the first iteration. A modified version of algorithm (1) is constructed

Return Xk;

in algorithm (2) on the basis of the momentum criterion. We introduce a small stopping value ϵ > 0, which allows for early termination of the algorithm, significantly reducing computation for convex functions. Note that in this pseudo-code, we have x as the initial vector, t as the output vector and y as an intermediate variable.

We discuss the motivation in Remark: 2. However, in the absence of strictly convex criterion, the algorithm (2), would not terminate and instead go on to an infinite loop. Therefore, upon encountering saddle points, as

9

Algorithm 2: Whiplash algorithm with Momentum-based stopping criterion

Result: T

Initialise : t = x −s∇f(x), k = 1, z = t −x, p = zTz

Return T;

explained in Remark: 1, we need to use additional stopping criterion, which are based on heuristic evaluations of the class of functions under study. We discuss such a novel algorithm using the Whiplash scheme in §3-E.

D. Numerical Results

1) As explained previously, for the Rosenbrock function, for the stiffness of the system, we use a step-size of no more than 10−5. This is because the algorithm is unable to learn the gradient of the cost function and picks up momentum without correcting the damping. For a sufficiently small step-size, the whiplash gradient descent algorithm successfully found the minima of Rosenbrock’s function for all initial conditions.

We have shown a few examples in Figure 6. This indicates that Rosenbrock’s function optimization has been achieved over the given time interval. Figure 7 shows the nature of the trajectory, as it approaches the minima of the Rosenbrock function.

2) We analyse the performance of our algorithm for convex cost functions. The standard method of determining the algorithm’s effectiveness is analysing its performance for various geometries. Note that, for unconstrained minimisation, this is a benchmark test because it allows us to analyse the tractability of the algorithm over a wide range of geometries. We perform a few experiments to test the algorithmic performance, as shown

In Figure 5 Using The Function F(X, Y) = 1

2(x2 + κy2) for the starting point (1, −1), where the condition number κ is varied. 3) In , we considered the utility of non-zero starting velocities for non-convex functions. We observed that, for non-convex or ill-conditioned systems, the initial velocity direction often dictates the nature of convergence. For the convex case, we observe that the direction of the starting velocity is immaterial to the nature of convergence, as shown in Figure: 8. As shown in Figure: 9, for small starting velocities, i.e.

|v| < 0.1, the nature of the trajectory is independent of the direction of the starting velocity. 4) We made a few observations for the numerical experimentation of the naive Whiplash algorithm around Saddle points. We observed that as long as the starting point is not at the saddle point itself, it is able to escape the saddle point. It is observed for the function J = 1

2(X2 −Y2), Which Has A Saddle Point At (0, 0)

we observed that if the algorithm is started sufficiently far from the saddle point, it does find the saddle point but escapes it. The numerical results for the saddle point experiment has been shown in figure: 10. Remark 1. The disadvantage of our naive algorithm is for functions with saddle points, it is unable to terminate because the approach being fundamentally black box prevents it from storing global information which means it may oscillate around a similar neighbourhood as it has no memory of the neighbourhoods visited in the past nor can it restart automatically from a different neighborhood. To counter this issue, we introduce a restarting scheme which force the algorithms out of neighbourhoods of the saddle points, as shown in algorithm (3), introduced in the next section. The algorithm has been verified for the cost function J. We find not finite minima

10

Figure 6. Trajectories for the Rosenbrock function optimization are dependent on initial condition: Note the blue circle denotes the starting point and the red star denotes the ending point. From upper left corner the initial conditions are (0,0), upper right(12,3), lower left (-3,7) and lower right (-7,17).

Figure 7. Zoomed Trajectory Plot with starting point (2,2). in r = 20 restarts, which numerically confirms that our algorithm is successful in deterministically escaping the saddle point.

E. Whiplash Exploration Algorithm

We introduce a final algorithm (3) which terminates automatically depending on heuristic parameters. Note that we cannot guarantee finding global minimas for non-convex functions in finite-time. Hence, inspired by Global Optimization methods , we introduce an auto restart variable r which uses the maximal radius explored by the algorithm to find another initial point. After r restarts, upon N maximum iterations on every restart batch,

11

Figure 8. Study of performance of the whiplash method under various starting velocities. Figure 9. Trajectories for small starting velocities. the algorithm auto-terminates. This algorithm specialises at exploring the function locally and deterministically.

Hence, we have named this as Whiplash exploration algorithm. The functional setting for the cost function is locally convex globally non-convex function with finite number of saddle points and local minimas represented by the finite set X, with one global minima x∗∈X, which maps as Rn 7→R, such that f ∗= minx∗∈X f. The

Strategy We Follow Is As Follows:

1) We choose the the initial point xi, step-size s > 0, the maximum number of permitted iterations in a batch N, the number of restarts r ≥0, the exploration parameter λ > 1 and the stopping criterion ϵ ≥0. 2) Initialise the oracle as a data line for the algorithm which allows it to sequence the gradient values in a black-box format. We also use the function output as a zero-order oracle.

3) Initialise counter variables as zero, while retaining the other initialisation and the initial direction vector

U = [1 . . . N Times . . . 1]T = It

n . 4) Initialise momentum using the gradient descent for the initial step as in the naive algorithm.

12

Figure 10. Numerically escaping the saddle point for the function J = 1 2(x2 −y2) given the starting point (-0.01,-0.01). 5) Initialise the reference radius Rr = ∥t−xi∥which allows the algorithm to decide whether it has started at a stationary point. Note that we are performing a trade-off. Essentially we are trading off faster convergence for exploration. The initial radius of exploration is the reference radius.

6) If the algorithm has not restarted, we enter the iteration loop for N as k updates and performs the naive whiplash algorithm scheme. If k > N, then the algorithm restarts. 7) The exploration radius Rk is updated if it is higher than the reference radius (in the first iteration) or since the last iteration. This allows for finding the maximum radius in the batch.

8) As the algorithm iterates, if it finds a local optima, it moves towards the minima, accurate to an error magnitude of ϵ. In case the momentum does not converge, in the presence of a saddle point or ill-conditioned plains, we iterate the algorithm up to a tolerating limit N, after which we restart the algorithm from a different initial point.

9) In case the momentum has converged, if the algorithm has searched sufficiently, i.e. R > λRr, the algorithm breaks out of the loop and finishes to return the value of the point, otherwise it restarts, as the batch must have been started near a saddle point. The choice of exploration parameter, which is the scaling magnitude λ, is determined heuristically. In the exceptional case where the algorithm restarts multiple times near local minimas, the lowest value f(y), where y ∈A is the output. To perform this we save the value in an array

A.

10) To restart in the next batch if the minima is not found within the search radius, we employ the following

∥∇F(T)∥,

whereby we can generate a new search space at every batch using an input unit vector u, which can be assigned arbitrarily. Essentially, we want to prevent the search in the same Rn space covered in the first batch and hence, we restart algorithm at double the maximum explored radius R of the initial batch. This process is visualized in figure:11.

11) The value of u can be changed at every iteration, however, in our implementation, it is updated

D

.

13

Figure 11. Evolution of the maximum radius and the restart of the Whiplash exploring algorithm with respect to the gradient descent direction. 12) Finally, as a terminating criterion, if the algorithm has explored heuristically for the minima and has either found the minima or has exhausted restarts it makes a decision on the output. If the restarts have been exhausted the algorithm auto-terminates. If the position vector t = ∞while searching for a minima, the algorithm restarts, thus speeding up the search process. In implementation we make sure that the value is not NaN. Hence, only if the momentum sequence has converged and the algorithm has explored sufficiently far enough, determined by the choice λ, the algorithm produces a viable output.

Note that in our implementation, we make the following set of choices: s = 10−4, λ = 2, r = 20, N = 100000 and ϵ = 10−6. We implement this algorithm for the class f = 1

2 (X2 + Κy2), For Various Κ > 0. Note That Our

algorithm does not adapt input heuristics. Stochastic approaches for designing the heuristic can be used in future work . For example the direction vector u could be a random multivariate Gaussian vector, normalised to unit magnitude. Other computational approaches like parallel-processing algorithms could be used to further speed-up the search process by exploiting local memory (cache) options within the system.

It is important to address the fact that in case the algorithm runs out of restarts and fails to find the global minima, it produces the minimal vector of a discovered stationary point. This limitation, which might produce sub-optimal results, is heuristic-driven. Our algorithm is strictly limited to gradient information in its run-time and, therefore, cannot adapt to the geometry of the function itself nor can it verify whether the minima found is global.

Finally, it is important to address the fact that there is a probability that every restart might end up spending iterations in neighbourhood of points it has already explored. To prevent this one could always update the input

∇F(T)

∥∇f(t)∥. However, numerically we have not found any significant difference in results. It is useful to thus consider heuristics using priori learning or systematic knowledge of the local geometries.

A. Symplectic Asymptotic Convergence

We consider the following lemmas—1, 2 and 3, which bridge from the continuous-time analysis of convergence to the discrete-time analysis using the symplectic discretisation property of asymptotic behavioural invariance. We analyse the Whiplash inertial gradient dynamical system which originates using an inverted approach of Wibisono et al.’s and Su et al.’s approach towards integrating discrete dynamical systems. The step-size s is considered to be sufficiently small in our analysis. Instead of using conventional methods of proving sequence based convergence estimates, using the asymptotic stability of the system itself, we essentially exploit the idea “rate-preserving” symplectic discretisation which allows us to use the similar arguments of convergence analysis

14

Algorithm 3: Whiplash exploring algorithm (with Momentum-based stopping criterion and Heuristic

Go To Restart;

fail: Output and Exit Program : No minima found in finite time for the given heuristics.

15

Figure 12. Symplectic Asymptotic Convergence analysis methodology in the discrete domain. Our methodology for proving convergence exploiting Lyapunov stability theorem and symplectic discretisation instead of finding estimate sequences or other discrete methods is summarised in figure: 12. Thus, we elucidate a non-classical methodology of proving convergence using an indirect approach, named as symplectic asymptotic convergence method.

Lemma 1. The Whiplash inertial gradient dynamical system (16) is globally asymptotically stable.

(24)

we can guarantee global asymptotic stability if there exists a functional, V (x), such that:

V (0) = 0

˙V (x) < 0 ∀x̸ = 0 .

(25)

We consider the La-Salle principle of invariance and suppose there exists a continuously differentiable, positive definite, radially unbounded function V (z) : Rn →R such that ∀z ∈Rn:

∂V

∂x (z −xe) f(z) ≤W(z) ≤0 .

(26)

Then, xe is a Lyapunov stable equilibrium point, and the solution always exists globally. “Moreover, x(t) converges to the largest invariant set M contained in E = {z ∈Rn : W(z) = 0}. When W(z) = 0 only for z = xe then E = {xe}. Since M ⊂E, therefore, x(t) →xe which implies asymptotic stability. Even when E̸ = {xe}, we often have the condition M = {xe} from which we can conclude asymptotic stability” . This result is used in our analysis for the general inertial gradient dynamical system by defining a candidate Lyapunov function W(t) for all damping functions γ such that:

(27)

where f(x∗) denotes the minima of the cost function. Upon replacing the time derivative in the equation (27)

˙W(T) = ⟨˙X, ¨X⟩+ ⟨∇(F), ˙X⟩

= −γ|| ˙X||2 ≤0 ∀γ ≥0 .

16

This relation shows that the time derivative of our Lyapunov candidate is negative and semi-definite. This condition shall suffice to show using La-Salle’s principle of invariance that the set of accumulation points of any trajectory is contained in I, where c is the union of complete trajectories contained entirely in the set {x : ˙W(x) = 0} . Thus by Lyapunov’s Second theorem, we have the functional W is positive definite; i.e.

“I contains no trajectory of the system except the trivial trajectory x(t) ≡0 and as W is radially unbounded; i.e. W(x) →∞as ||x|| →∞”, we conclude that the origin is globally asymptotically stable . Since from (16), has γ = (1 + t∥˙x∥2) > 0, hence, it suffices the condition to be globally asymptotically stable as required.

Lemma 2. For the whiplash gradient descent method, the sequence ∥xk −x∗∥converges as k →∞for a convex cost function. Proof. The system is globally asymptotically stable for the whiplash gradient descent, as shown in Lemma 1. We know that for the symplectic “rate preserving” Euler scheme , the asymptotic nature of the inertial gradient system remains intact within the sampled time-domain T > 0; i.e.

√S

∥xk −x(k√s)∥= 0.

(29)

This means that as ∥x(t) −x∗∥is asymptotically convergent, ∥x(k√s) −x∗∥is asymptotically convergent, as k →∞. Then it follows that, for a step-size 0 < s ≤1, the following must hold

Lim

k→∞xk = x∗.

(30)

Thus, the sequence ∥xk −x∗∥must be convergent, as required. Lemma 3. The momentum sequence ∥zk∥of the whiplash gradient descent method is bounded and convergent. Proof. In lemma 1, using LaSalle’s invariance principle, we proved that the system (16) is globally asymptotically stable. This implies that there exists no trajectory within the set I, which is unbounded, and hence, it follows that ∥x(t)∥< ∞which also implies from lemma 2 that the sequence ∥xk −x∗∥is bounded for every k > 0. It implies thus that ∥zk∥= ∥xk −xk−1∥is bounded for every k > 0. From lemma 1, we also know that

Lim

t→∞∥˙x(t)∥= 0.

(31)

Applying the symplectic discretisation of ˙x(t) = xk+1−xk

(32)

as required. Lemma 4. The inner product sequence: ⟨xk −x∗, zk⟩converges as k →∞. Proof. Let the sequence xk −x∗= pk. Then, using Cauchy-Schwarz inequality for finite dimensional vector

2

= ∥pk∥∥zk∥. Now applying the limits using the Cauchy-Schwarz inequality, we have

(33)

as required.

Related Journal Articles & DOI Links

Selected peer-reviewed publications relevant to 12 Lead ECG Acquisition. Click the DOI to access the full paper (may require institutional access).

Why Choose Us?

Bangalore guidance for robotics, Spectre and autonomous systems projects.