A Newton-Like Dynamical System for Nonsmooth and Nonconvex Optimization
Juan Guillermo Garrido, Pedro Pérez-Aros, Emilio Vilches · 2024
Read A Newton-Like Dynamical System for Nonsmooth and Nonconvex Optimization by Juan Guillermo Garrido, Pedro Pérez-Aros, Emilio Vilches (2024) 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-2412-05952.txt.
Introduction
Juan Guillermo Garrido, Pedro Pérez-Aros, and Emilio Vilches present a 2024 mathematics paper on a Newton-like flow for optimization problems with kinks. Many real objectives are nonsmooth or nonconvex, so the classic Newton method stalls. The authors build a moving system whose paths slide downhill on such terrain, borrowing second-order news from a graphical derivative.
They prove the system's paths exist, are unique, and settle down in the long run. Two sets of conditions give convergence with explicit speed estimates. One rests on a regularity property of the problem's solution map. The other uses a classic inequality that controls how flat the valley can be. The theory extends a trusted method into territory where gradients break.
Catalog record
| CREATOR | Juan Guillermo Garrido, Pedro Pérez-Aros, Emilio Vilches |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-05952
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Newton-Like Dynamical System for Nonsmooth and Nonconvex Optimization Thanks: Submitted to the editors DATE. Juan Guillermo Garrido, Pedro Pérez-Aros, Emilio Vilches Abstract This work investigates a dynamical system functioning as a nonsmooth adaptation of the continuous Newton method, aimed at minimizing the sum of a primal lower-regular and a locally Lipschitz function, both potentially nonsmooth. The classical Newton method’s second-order information is extended by incorporating the graphical derivative of a locally Lipschitz mapping. Specifically, we analyze the existence and uniqueness of solutions, along with the asymptotic behavior of the system’s trajectories. Conditions for convergence and respective convergence rates are established under two distinct scenarios: strong metric subregularity and satisfaction of the Kurdyka-Łojasiewicz inequality. keywords Nonsmooth programming, nonsmooth Newton method, asymptotic analysis, global convergence, convergence rates, dynamical systems, variational analysis Funding. Research of the first author was partially supported by ANID BECAS/DOCTORADO NACIONAL 21230802. Research of the second and third author was partially supported by Centro de Modelamiento Matemático (CMM), ACE210010 and FB210005, BASAL funds for center of excellence and ANID-Chile grant: MATH-AMSUD 23-MATH-09 and MATH-AMSUD 23-MATH-17, ECOS-ANID ECOS320027, Fondecyt Regular 1220886, Fondecyt Regular 1240335, Fondecyt Regular 1240120 and Exploración 13220097. † † runningheads: A Newton-Like Dynamical System for Nonsmooth Optimization / J.G. Garrido, P. Pérez-Aros, and E. Vilches AMS 34G25, 34G20, 34A60, 49J53 1 Introduction Newton’s method is one of the most prominent algorithms for solving unconstrained optimization problems. By utilizing first- and second-order information, it achieves quadratic convergence rates, provided that the initial condition is sufficiently close to a critical point. The principles behind this algorithm have served as the foundation for the development of numerous efficient algorithms for both linear and nonlinear optimization. However, the requirements for the applicability of this algorithm can be quite restrictive in modern optimization problems, where the lack of smoothness or convexity of the objective function occurs frequently. From a more classical perspective, to address this difficulty, algorithms have been developed where, at each iteration, the objective function is replaced by a local approximation with the desired properties of differentiability or convexity. Notable examples of this paradigm include trust-region algorithms and difference-of-convex methods (see, e.g., [ 19 ] ). A different paradigm involves directly addressing the non-differentiability or non-convexity of the objective function without relying on surrogates, using tools from generalized differentiation and variational analysis. In this direction, we highlight the development of non-smooth Newton methods, which, instead of requiring the continuous second-order differentiability of the function, only impose that the objective function belongs to the class \mathcal{C}^{1,+} (see, e.g., [ 23 , 16 , 17 , 18 ] and the references therein). Furthermore, in [ 4 ] , the authors introduce a novel approach for objective functions that can be decomposed as the difference between a \mathcal{C}^{1,+} function and a prox-regular function. These algorithms, inspired by the classical Newton’s method, leverage second-order information about the objective function using a class of generalized Hessians. Advanced techniques in variational analysis enable satisfactory convergence results for the proposed algorithms, along with faster convergence rates in certain cases compared to methods that rely solely on first-order information. In this paper, we follow this second approach and we study the convergence of a Newton-like dynamical system associated with the optimization problem for objective functions that are not necessarily convex or differentiable. The study of continuous versions of optimization algorithms is a classical topic in this field. It is widely recognized that continuous versions of discrete algorithms offer several advantages, both from a theoretical and practical perspective (see, e.g., [ 29 ] ). On the one hand, they enable convergence analysis through the stability theory of dynamical systems, and on the other hand, they facilitate the understanding of essential aspects of the algorithms, such as their derivation, and parameter tuning, stability improvements, among others. In particular, different approaches to discretizing a continuous dynamical system lead to iterative algorithms, whose convergence analysis often parallels that of the continuous case. In the continuous setting, the Newton method has been an interesting topic of study. Its global convergence was studied in [ 28 ] , and in [ 3 ] , the authors addressed the convergence rates in the convex and smooth setting. Subsequently, several works have explored inertial dynamics associated with the continuous Newton method (see, e.g., [ 8 , 1 , 2 , 5 , 11 ] ). Following the continuous setting, we propose a dynamical system associated with a nonsmooth Newton method for the minimization of nonsmooth and nonconvex functions. Formally, we consider the structured nonsmooth mathematical program \min\varphi(x),\text{ with }\varphi:=\varphi_{1}+\varphi_{2}, (1) where \varphi_{1}\colon\mathbb{R}^{d}\to\mathbb{R}\cup\{\infty\} is a primal lower regular (plr) function, and \varphi_{2}\colon\mathbb{R}^{d}\to\mathbb{R} is locally Lipschitz function. It is important to highlight that the aforementioned optimization problem is quite general. On the one hand, working with extended-valued functions enables dealing with constrained optimization. On the other hand, plr functions cover a wide class of functions with an underlying nonsmooth structure. Among these functions, we can find all lower semicontinuous (lsc) proper convex functions, lower- C^{2} functions, and qualified convexly composite functions (see, e.g., [ 30 ] ). With the problem ( 1 ) in mind, we propose the following dynamical system to model a fully nonsmooth continuous dynamical Newton-like method. We aim to find an absolutely continuous function x\colon\mathbb{R}_{+}\to\mathbb{R}^{d} that satisfies the following conditions: There are measurable functions v_{1},v_{2}\colon\mathbb{R}_{+}\to\mathbb{R}^{d} such that v_{1}(t)\in\partial\varphi_{1}(x(t)) and v_{2}(t)\in\partial\varphi_{2}(x(t)) for a.e. t\in\mathbb{R}_{+} and \displaystyle v_{1}(t)+v_{2}(t) \displaystyle\in-DF(x(t))(\dot{x}(t))\text{ a.e. on }\mathbb{R}_{+} \displaystyle x(0) \displaystyle=x_{0}. where x_{0}\in\mathbb{R}^{d} is given, and F\colon\mathbb{R}^{d}\to\mathbb{R}^{d} is a locally Lipschitz function. Here, \partial f denotes the Clarke subdifferential of a function f , and DF represents the graphical derivative of the mapping F (see definitions below). The dynamical system ( 2 ) is referred to as Newton-like because if F is the gradient of a function, the system becomes the Newton method. Moreover, considering a general operator F allows for the treatment of more general cases in the spirit of quasi-Newton method or Levenberg-Marquardt algorithm (see, e.g., [ 15 ] and the references therein). The aim of this paper is to investigate the well-posedness and the asymptotic convergence of the solutions to the dynamical system ( 2 ). The paper is organized as follows: Section 2 introduces the mathematical background required for the subsequent analysis. Section 3 presents the main result concerning the existence and uniqueness of solutions for the system ( 2 ). In Section 4, we study the asymptotic behavior of the solutions to the system ( 2 ). In particular, we describe the limit set of the trajectories of ( 2 ) and demonstrate their convergence under the strong metric subregularity and the Kurdyka-Łojasiewicz inequality. Rates of convergence are established in both cases. To keep it simple, all proofs and technical aspects of the paper are provided in the appendix. 2 Notation and preliminary results In what follows, we consider the standard concepts and definitions used in nonsmooth and variational analysis. For more details, we refer to the classical monographs [ 27 , 22 , 30 ] . Throughout the paper, \mathbb{R}^{d} denotes the d -dimensional Euclidean space with the norm \|\cdot\| and the corresponding inner product \langle\cdot,\cdot\rangle . For r>0 and x\in\mathbb{R}^{d} , we denote by \mathbb{B}_{r}(x) and \mathbb{B}_{r}[x] the open and closed balls centered at