Newton-like dynamics associated to nonconvex optimization problems

DOI10.1007/978-3-030-11370-4_6MaRDI QIDQ2319938zbMATH OpenOpenAlexFDO

Authors Radu I. Boţ, Ernö Robert Csetnek

Publication date 21 August 2019

Full work available at URL https://arxiv.org/abs/1703.01339

zbMATH Keywords

dynamical systemsKurdyka-Łojasiewicz propertylimiting subdifferentialLyapunov analysisNewton-like methodsnonsmooth optimization

Mathematics Subject Classification ID

Ordinary differential inclusions (34A60) Monotone operators and generalizations (47H05) Iterative procedures involving nonlinear operators (47J25) Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)

Abstract: We consider the dynamical system �egin{equation*}left{ �egin{array}{ll} v(t)inpartialphi(x(t))\ lambdadot x(t) + dot v(t) + v(t) + abla psi(x(t))=0, end{array} ight.end{equation*} where $phi:R^{n}oRcup+infty$ is a proper, convex and lower semicontinuous function, $psi:R^{n}oR$ is a (possibly nonconvex) smooth function and $lambda>0$ is a parameter which controls the velocity. We show that the set of limit points of the trajectory $x$ is contained in the set of critical points of the objective function $phi+psi$, which is here seen as the set of the zeros of its limiting subdifferential. If the objective function satisfies the Kurdyka-L{}ojasiewicz property, then we can prove convergence of the whole trajectory $x$ to a critical point. Furthermore, convergence rates for the orbits are obtained in terms of the L{}ojasiewicz exponent of the objective function, provided the latter satisfies the L{}ojasiewicz property.

Review text

The paper studies differential inclusions of the form \[ \begin{aligned} &v(t)\in \partial \varphi (x(t)),\\ &\lambda x'(t)+v'(t)+v(t)+\nabla \psi (x(t))=0,\\ &x(0)=x_0,\quad v(0)=v_0\in \partial \varphi (x_0), \end{aligned} \] where \(\varphi :{\mathbb{R}}^n\to {\mathbb{R}}^n\cup \{\infty \}\) is a proper convex lower semicontinuous function, \(\psi :{\mathbb{R}}^n\to \mathbb{R}\) is a function with Lipschitz continuous gradient, \(\lambda >0\) and \(x_0,y_0\in {\mathbb{R}}^n\). By assuming a certain Kurdyka-Lojasiewicz property it is proved the convergence of the solution \(x\) to a critical point of \(\varphi +\psi \). Several estimates for the convergence rates of the orbits are also provided. For the entire collection see [Zbl 1417.49001].

Recommendations

• Approaching nonsmooth nonconvex optimization problems through first order dynamical systems with hidden acceleration and Hessian driven damping terms
• Convergence of a Class of Nonmonotone Descent Methods for Kurdyka–Łojasiewicz Optimization Problems
• Approaching nonsmooth nonconvex minimization through second-order proximal-gradient dynamical systems
• A second-order dynamical approach with variable damping to nonconvex smooth minimization
• A forward-backward dynamical approach to the minimization of the sum of a nonsmooth convex with a smooth nonconvex function

Cited in

(10)

• Levenberg-Marquardt dynamics associated to variational inequalities
• Approaching nonsmooth nonconvex minimization through second-order proximal-gradient dynamical systems
• Convergence rates for the heavy-ball continuous dynamics for non-convex optimization, under Polyak-Łojasiewicz condition
• Convergence rates for an inertial algorithm of gradient type associated to a smooth non-convex minimization
• On the dynamics of a differential inclusion built upon a nonconvex constrained minimization problem
• A forward-backward dynamical approach to the minimization of the sum of a nonsmooth convex with a smooth nonconvex function
• A second-order dynamical approach with variable damping to nonconvex smooth minimization
• Accelerated differential inclusion for convex optimization
• Finite-time nonconvex optimization using time-varying dynamical systems
• Continuous dynamics related to monotone inclusions and non-smooth optimization problems

This page was built for publication: Newton-like dynamics associated to nonconvex optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2319938)