Solving nonconvex optimization problems via a second order dynamical system with unbounded damping

Szilárd Csaba László 1,∗ · 2025

Read Solving nonconvex optimization problems via a second order dynamical system with unbounded damping by Szilárd Csaba László 1,∗ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16864.txt.

Introduction

Szilárd Csaba László studies a moving-system method for hard minimization in a 2025 paper. The goal is minimizing a smooth function that is nonconvex. Nonconvex means the landscape has many valleys, not just one. His system follows a path shaped by changing friction-like terms.

László proves the path settles at a critical point of the function. That holds when a smoothed version of the function meets a known shape condition. He also derives how fast the path closes in. The speed depends on a single exponent describing the function's shape. Letting the damping grow without bound improves earlier known rates. Instead of steady linear progress, the method gains superlinear speed near the end.

Catalog record

CREATORSzilárd Csaba László 1,∗
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-16864

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Solving nonconvex optimization problems via a second order dynamical system with unbounded damping Szilárd Csaba László 1,∗ Abstract 1 Department of Mathematics, Technical University of Cluj-Napoca, Memorandumului 28, Cluj-Napoca, Romania This paper is dedicated to the memory of Professor Hedy Attouch Abstract. In this paper we study a second order dynamical system with variable coefficients in connection to the minimization problem of a smooth nonconvex function. The convergence of the trajectories generated by the dynamical system to a critical point of the objective function is assured, provided a regularization of the objective function satisfies the Kurdyka-Łojasiewicz property. We also provide convergence rates for the trajectories generated by the dynamical system, formulated in terms of the Łojasiewicz exponent, and we show that the unbounded damping considered in our dynamical system significantly improves the convergence rates known so far in the literature, that is, instead of linear rates we obtain superlinear rates. Keywords. second order dynamical system; unbounded damping; nonconvex optimization; Kurdyka-Łojasiewicz inequality; convergence rate; superlinear rate. 2020 Mathematics Subject Classification. 90C26, 90C30, 65K10. † † footnotetext: ∗ Corresponding author. E-mail address: [email protected]. Received xx, x, xxxx; Accepted xx, x, xxxx. ©2022 Communications in Optimization Theory 1. Introduction Consider the second order dynamical system \left\{\begin{array}[]{lll}\displaystyle\frac{\lambda}{t^{2}}\ddot{x}(t)+\frac{\gamma}{t}\dot{x}(t)+\nabla g(x(t))=0\\ \\ \displaystyle x(t_{0})=u_{0},\,\dot{x}(t_{0})=v_{0},\end{array}\right. (DS) in connection to the optimization problem \ \inf_{x\in\mathbb{R}^{n}}g(x), (P) where t_{0}>0, g:\mathbb{R}^{n}\longrightarrow\mathbb{R} is a possibly nonconvex Fréchet differentiable function with L_{g} -Lipschitz continuous gradient, u_{0},v_{0}\in\mathbb{R}^{n} and \gamma,\lambda\in(0,+\infty). Note that the governing differential equation of ( DS ) can be written as \ddot{x}(t)+\frac{\gamma}{\lambda}t\dot{x}(t)+\frac{t^{2}}{\lambda}\nabla g(x(t))=0 where the damping \frac{\gamma}{\lambda}t is indeed unbounded. Of course, instead of ( DS ) one can consider the dynamical system \lambda(t)\ddot{x}(t)+\gamma(t)\dot{x}(t)+\nabla g(x(t))=0,\,\displaystyle x(t_{0})=u_{0},\,\dot{x}(t_{0})=v_{0} provided \lambda(t)=\mathcal{O}\left(\frac{1}{t^{2}}\right) and \gamma(t)=\mathcal{O}\left(\frac{1}{t}\right) as t\to+\infty and the analysis presented in the paper remains valid. We emphasize that a particular instance of the latter system can be obtained from the dynamical system studied in [ 9 ] , that is, \ddot{y}(s)+\gamma\dot{y}(s)+{\nabla}g(y(s))=0,\,y(s_{0})=u_{0},\,\dot{y}(s_{0})=v_{0},\,b>0, (BBJ) by using the time rescaling s=t^{2},\,x(t)=y(s). Indeed, after some easy computations we obtain \frac{1}{4t^{2}}\ddot{x}(t)+\left(\frac{\gamma}{2t}-\frac{1}{4t^{3}}\right)\dot{x}(t)+{\nabla}g(x(t))=0, therefore in some sense ( DS ) and ( BBJ ) seem to be equivalent. However, according to [ 9 ] , (see also [ 14 ] ), the trajectories generated by ( BBJ ) converge to a critical point of g , provided g is of class C^{2} and satisfies the Kurdyka-Łojasiewicz property, further the desingularizing function \varphi satisfies \varphi(s)\geq c\sqrt{s},\,s\in(0,\eta), where c,\eta>0 . In contrast, in this paper we obtain the convergence of a trajectory generated by ( DS ) to a critical point of g , provided the regularization of g , H:\mathbb{R}^{n}\times\mathbb{R}^{n}\longrightarrow\mathbb{R},\,H(u,v)=g(u)+\frac{1}{2}\|u-v\|^{2} satisfies the Kurdyka-Łojasiewicz inequality. Moreover, we will obtain some convergence rates that are better than those obtained in [ 9 ] or [ 14 ] . In particular, in case of strongly convex objective functions, we will obtain superlinear rates instead of linear rates. Another motivation for the study of the dynamical system ( DS ) arises in the following setting. Consider the perturbed dynamical system studied in [ 15 ] , that is, \ddot{x}(t)+\left(\frac{\alpha}{t}+\gamma\right)\dot{x}(t)+\nabla g(x(t))=0,\,x(t_{0})=u_{0},\,\dot{x}(t_{0})=v_{0}, (BCL) where u_{0},v_{0}\in\mathbb{R}^{n} and \alpha,\gamma\in(0,+\infty). Indeed, ( BCL ) is a perturbed version of the dynamical system considered by Su, Boyd and Candès in [ 25 ] , the latter one can be obtained by taking \gamma=0 in ( BCL ). However the objective function in [ 25 ] is assumed to be convex, and in this context the dynamical system studied in [ 25 ] can be seen as the continuous counterpart of the celebrated Nesterov accelerated convex gradient method [ 22 ] . By using the time rescaling t=s^{2} and by denoting y(s)=x\left(s^{2}\right), the system ( BCL ) can be rewritten as \frac{1}{4s^{2}}\ddot{y}(s)+\left(\frac{\gamma}{2s}-\frac{2\alpha-1}{4s^{3}}\right)\dot{y}(s)+\nabla g(y(s))=0,\,y(s_{0})=u_{0},\,\dot{y}(s_{0})=2s_{0}v_{0}, where s_{0}=\sqrt{t_{0}}. Consequently the dynamical system ( DS ) is also similar to the dynamical system ( BCL ). According to [ 15 ] , the trajectories generated by ( BCL ) converge to a critical point of g , provided the function g(u)+\frac{1}{2}\|u-v\|^{2},\,u,v\in\mathbb{R}^{n} satisfies the Kurdyka-Łojasiewicz inequality. Note that in case g is a strongly convex function then according to [ 9 ] and [ 15 ] one has lim_{t\to+\infty}x(t)=\overline{x} where \overline{x} is a critical point of g. Further, it holds the linear rate \|x(t)-\overline{x}\|=\mathcal{O}(e^{-At}) as t\to+\infty, where A>0. In contrast, for strongly convex objective functions, in this paper we will obtain the superlinear rate \|x(t)-\overline{x}\|=\mathcal{O}(e^{-At^{2}})\mbox{ as }t\to+\infty. The paper is organized as follows. After presenting some preliminary notion and results that we need in order to carry out our analysis, in section 3 we show the existence and uniqueness of the trajectories of the dynamical system ( DS ). We also show that the third order derivative exists almost everywhere. In section 4 we show the convergence of the trajectories generated by the dynamical system ( DS ) to a critical point of our objective function g . We also discuss the cases when g is semialgebraic or g is strongly convex. In section 5 we obtain convergence rates in terms of the Łojasiewicz exponent of the objective function. In particular we show that for strongly convex objective functions the trajectories generated by the dynamical system ( DS ) converge in superlinear rate to a critical point of g. 2. Preliminaries The finite-dimensional spaces considered in the manuscript are endowed with the Euclidean norm topology. The Fermat rule in this setting reads as: if x\in\mathbb{R}^{n} is a local minimizer of g then 0\in\nabla g(x) . We denote by \crit(g)=\{x\in\mathbb{R}^{n}:0\in{\nabla}g(x)\} the set of critical points of g . Definition 2.1 . (see, for instance, [ 7 , 1 ] ) A function x:[0,+\infty)\rightarrow\mathbb{R}^{n} is said to be locally absolutely continuous, if is absolutely continuous on every interval [0,T],\,T>0 , that is, one of the following equivalent properties holds: (i) there exists an integrable function y:[0,T]\rightarrow\mathbb{R}^{n} such that x(t)=x(0)+\int_{0}^{t}y(s)ds\ \ \forall t\in[0,T]; (ii) x is continuous and its distributional derivative is Lebesgue integrable on [0,T] ; (iii) for every \varepsilon>0 , there exists \eta>0 such that for any finite family of intervals I_{k}=(a_{k},b_{k})\subseteq[0,T] we have the implication \left(I_{k}\cap I_{j}=\emptyset\mbox{ and }\sum_{k}|b_{k}-a_{k}|<\eta\right)\Longrightarrow\sum_{k}\|x(b_{k})-x(a_{k})\|<\varepsilon. Remark 2.2 . (a) It follows from the definition that an absolutely continuous function is differentiable almost everywhere, its derivative coincides with its distributional derivative almost everywhere and one can recover the function from its derivative \dot{x}=y by the integration formula (i). (b) If x:[0,T]\rightarrow\mathbb{R}^{n} (where T>0 ) is absolutely continuous and B:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n} is L -Lipschitz continuous (where L\geq 0 ), then the function z=B\circ x is absolutely continuous, too. This can be easily seen by using the characterization of absolute continuity in Definition 2.1 (iii). Moreover, z is almost everywhere differentiable and the inequality \|\dot{z}(\cdot)\|\leq L\|\dot{x}(\cdot)\| holds almost everywhere. We recall two technical lemmas which will play an essential role in our analysis, (see [ 1 ] Lemma 5.1 and Lemma 5.2, respectively). Lemma 2.3 . Suppose that F:[0,+\infty)\rightarrow\mathbb{R} is locally absolutely continuous and bounded below and that there exists G\in L^{1}([0,+\infty)) such that for almost every t\in[0,+\infty) \frac{d}{dt}F(t)\leq G(t). Then there exists \lim_{t\rightarrow\infty}F(t)\in\mathbb{R} . Lemma 2.4 . If 1\leq p<\infty , 1\leq r\leq\infty , F:[0,+\infty)\rightarrow[0,+\infty) is locally absolutely continuous, F\in L^{p}([0,+\infty)) , G:[0,+\infty)\rightarrow\mathbb{R} , G\in L^{r}([0,+\infty)) and for almost every t\in[0,+\infty) \frac{d}{dt}F(t)\leq G(t), then \lim_{t\rightarrow+\infty}F(t)=0 . The convergence of the trajectories generated by the dynamical system ( DS )

Read the complete text