BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Hedy Attouch

Hedy Attouch appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCmath.DS

Catalog footprint

What is connected

13works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2022arXiv

Accelerated gradient methods combining Tikhonov regularization with geometric damping driven by the Hessian

In a Hilbert setting, for convex differentiable optimization, we consider accelerated gradient dynamics combining Tikhonov regularization with Hessian-driven damping. The Tikhonov regularization parameter is assumed to tend to zero as time tends to infinity, which preserves equilibria. The presence of the Tikhonov regularization term induces a strong convexity property which vanishes asymptotically. To take advantage of the exponential convergence rates attached to the heavy ball method in the strongly convex case, we consider the inertial dynamic where the viscous damping coefficient is taken proportional to the square root of the Tikhonov regularization parameter, and therefore also converges towards zero. Moreover, the dynamic involves a geometric damping which is driven by the Hessian of the function to be minimized, which induces a significant attenuation of the oscillations. Under an appropriate tuning of the parameters, based on Lyapunov's analysis, we show that the trajectories have at the same time several remarkable properties: they provide fast convergence of values, fast convergence of gradients towards zero, and strong convergence to the minimum norm minimizer. This study extends a previous paper by the authors where similar issues were examined but without the presence of Hessian driven damping.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the effect of perturbations in first-order optimization methods with inertia and Hessian driven damping

Second-order continuous-time dissipative dynamical systems with viscous and Hessian driven damping have inspired effective first-order algorithms for solving convex optimization problems. While preserving the fast convergence properties of the Nesterov-type acceleration, the Hessian driven damping makes it possible to significantly attenuate the oscillations. To study the stability of these algorithms with respect to perturbations, we analyze the behaviour of the corresponding continuous systems when the gradient computation is subject to exogenous additive errors. We provide a quantitative analysis of the asymptotic behaviour of two types of systems, those with implicit and explicit Hessian driven damping. We consider convex, strongly convex, and non-smooth objective functions defined on a real Hilbert space and show that, depending on the formulation, different integrability conditions on the perturbations are sufficient to maintain the convergence rates of the systems. We highlight the differences between the implicit and explicit Hessian damping, and in particular point out that the assumptions on the objective and perturbations needed in the implicit case are more stringent than in the explicit case.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Fast optimization via inertial dynamics with closed-loop damping

In a Hilbert space $H$, in order to develop fast optimization methods, we analyze the asymptotic behavior, as time $t$ tends to infinity, of inertial continuous dynamics where the damping acts as a closed-loop control. The function $f: H \to R$ to be minimized (not necessarily convex) enters the dynamic through it gradient, which is assumed to be Lipschitz continuous on the bounded subsets of $H$. This gives autonomous dynamical systems with nonlinear damping and nonlinear driving force. We first consider the case where the damping term $\partial ϕ(\dot{x}(t))$ acts as a closed-loop control of the velocity. The damping potential $ϕ: H \to [0,+\infty)$ is a convex continuous function which achieves its minimum at the origin. We show the existence and uniqueness of a global solution to the associated Cauchy problem. Then, we analyze the asymptotic convergence properties of the generated trajectories generated. We use techniques from optimization, control theory, and PDE's: Lyapunov analysis based on the decreasing property of an energy-like function, quasi-gradient and Kurdyka-Lojasiewicz theory, monotone operator theory for wave-like equations. Convergence rates are obtained based on the geometric properties of the data $f$ and $ϕ$. When $f$ is strongly convex, we give general conditions which provide exponential convergence rates. Then, we extend the results to the case where an additional Hessian-driven damping enters the dynamic, which reduces the oscillations. Finally, we consider an inertial system involving jointly the velocity $\dot{x}(t)$ and the gradient $\nabla f(x(t))$. In addition to its original results, this work surveys the numerous works devoted in recent years to the interaction between continuous damped inertial dynamics and numerical algorithms for optimization, with the emphasis on autonomous systems, closed-loop adaptive procedures, and convergence rates.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fast convex optimization via a third-order in time evolution equation: TOGES-V an improved version of TOGES

In a Hilbert space setting H, for convex optimization, we analyze the fast convergence properties as t tends to infinity of the trajectories generated by a third-order in time evolution system. The function f to minimize is supposed to be convex, continuously differentiable, with a nonempty set of minimizers. It enters into the dynamic through its gradient. Based on this new dynamical system, we improve the results obtained by [Attouch, Chbani, Riahi: Fast convex optimization via a third-order in time evolution equation, Optimization 2020]. As a main result, when the damping parameter $α$ satisfies $α> 3$, we show that the convergence of the values at the order 1/t3 as t goes to infinity, as well as the convergence of the trajectories. We complement these results by introducing into the dynamic an Hessian driven damping term, which reduces the oscillations. In the case of a strongly convex function f, we show an autonomous evolution system of the third order in time with an exponential rate of convergence. All these results have natural extensions to the case of a convex lower semicontinuous function with extended real values. Just replace f with its Moreau envelope.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling

In a Hilbert setting, we develop fast methods for convex unconstrained optimization. We rely on the asymptotic behavior of an inertial system combining geometric damping with temporal scaling. The convex function to minimize enters the dynamic via its gradient. The dynamic includes three coefficients varying with time, one is a viscous damping coefficient, the second is attached to the Hessian-driven damping, the third is a time scaling coefficient. We study the convergence rate of the values under general conditions involving the damping and the time scale coefficients. The obtained results are based on a new Lyapunov analysis and they encompass known results on the subject. We pay particular attention to the case of an asymptotically vanishing viscous damping, which is directly related to the accelerated gradient method of Nesterov. The Hessian-driven damping significantly reduces the oscillatory aspects. As a main result, we obtain an exponential rate of convergence of values without assuming the strong convexity of the objective function. The temporal discretization of these dynamics opens the gate to a large class of inertial optimization algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Asymptotic behavior of gradient-like dynamical systems involving inertia and multiscale aspects

In a Hilbert space $\mathcal H$, we study the asymptotic behaviour, as time variable $t$ goes to $+\infty$, of nonautonomous gradient-like dynamical systems involving inertia and multiscale features. Given $\mathcal H$ a general Hilbert space, $Φ: \mathcal H \rightarrow \mathbb R$ and $Ψ: \mathcal H \rightarrow \mathbb R$ two convex differentiable functions, $γ$ a positive damping parameter, and $ε(t)$ a function of $t$ which tends to zero as $t$ goes to $+\infty$, we consider the second-order differential equation $$\ddot{x}(t) + γ\dot{x}(t) + \nabla Φ(x(t)) + ε(t) \nabla Ψ(x(t)) = 0. $$ This system models the emergence of various collective behaviors in game theory, as well as the asymptotic control of coupled nonlinear oscillators. Assuming that $ε(t)$ tends to zero moderately slowly as $t$ goes to infinity, we show that the trajectories converge weakly in $\mathcal H$. The limiting equilibria are solutions of the hierarchical minimization problem which consists in minimizing $Ψ$ over the set $C$ of minimizers of $Φ$. As key assumptions, we suppose that $ \int_{0}^{+\infty}ε(t) dt = + \infty $ and that, for every $p$ belonging to a convex cone $\mathcal C$ depending on the data $Φ$ and $Ψ$ $$ \int_{0}^{+\infty} \left[Φ^* \left(ε(t)p\right) -σ_C \left(ε(t)p\right)\right]dt < + \infty $$ where $Φ^*$ is the Fenchel conjugate of $Φ$, and $σ_C $ is the support function of $C$. An application is given to coupled oscillators.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Asymptotic behavior of nonautonomous monotone and subgradient evolution equations

In a Hilbert setting $H$, we study the asymptotic behavior of the trajectories of nonautonomous evolution equations $\dot x(t)+A_t(x(t))\ni 0$, where for each $t\geq 0$, $A_t:H\tto H$ denotes a maximal monotone operator. We provide general conditions guaranteeing the weak ergodic convergence of each trajectory $x(\cdot)$ to a zero of a limit maximal monotone operator $ A_\infty$, as the time variable $t$ tends to $+\infty$. The crucial point is to use the Brézis-Haraux function, or equivalently the Fitzpatrick function, to express at which rate the excess of $\gph A_\infty$ over $\gph A_t$ tends to zero. This approach gives a sharp and unifying view on this subject. In the case of operators $A_t= \partial ϕ_t$ which are subdifferentials of closed convex functions $ϕ_t$, we show convergence results for the trajectories. Then, we specialize our results to multiscale evolution equations, and obtain asymptotic properties of hierarchical minimization, and selection of viscosity solutions. Illustrations are given in the field of coupled systems, and partial differential equations.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Combining fast inertial dynamics for convex optimization with Tikhonov regularization

In a Hilbert space setting $\mathcal H$, we study the convergence properties as $t \to + \infty$ of the trajectories of the second-order differential equation \begin{equation*} \mbox{(AVD)}_{α, ε} \quad \quad \ddot{x}(t) + \fracα{t} \dot{x}(t) + \nabla Φ(x(t)) + ε(t) x(t) =0, \end{equation*} where $\nablaΦ$ is the gradient of a convex continuously differentiable function $Φ: \mathcal H \to \mathbb R$, $α$ is a positive parameter, and $ε(t) x(t)$ is a Tikhonov regularization term, with $\lim_{t \to \infty}ε(t) =0$. In this damped inertial system, the damping coefficient $\fracα{t}$ vanishes asymptotically, but not too quickly, a key property to obtain rapid convergence of the values. In the case $ε(\cdot) \equiv 0$, this dynamic has been highlighted recently by Su, Boyd, and Candès as a continuous version of the Nesterov accelerated method. Depending on the speed of convergence of $ε(t)$ to zero, we analyze the convergence properties of the trajectories of $\mbox{(AVD)}_{α, ε}$. We obtain results ranging from the rapid convergence of $Φ(x(t))$ to $\min Φ$ when $ε(t)$ decreases rapidly to zero, up to the strong ergodic convergence of the trajectories to the element of minimal norm of the set of minimizers of $Φ$, when $ε(t)$ tends slowly to zero.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Fast convex optimization via inertial dynamics with Hessian driven damping

We first study the fast minimization properties of the trajectories of the second-order evolution equation $$\ddot{x}(t) + \fracα{t} \dot{x}(t) + β\nabla^2 Φ(x(t))\dot{x} (t) + \nabla Φ(x(t)) = 0,$$ where $Φ:\mathcal H\to\mathbb R$ is a smooth convex function acting on a real Hilbert space $\mathcal H$, and $α$, $β$ are positive parameters. This inertial system combines an isotropic viscous damping which vanishes asymptotically, and a geometrical Hessian driven damping, which makes it naturally related to Newton's and Levenberg-Marquardt methods. For $α\geq 3$, $β>0$, along any trajectory, fast convergence of the values $$Φ(x(t))- \min_{\mathcal H}Φ=\mathcal O\left(t^{-2}\right)$$ is obtained, together with rapid convergence of the gradients $\nablaΦ(x(t))$ to zero. For $α>3$, just assuming that $Φ$ has minimizers, we show that any trajectory converges weakly to a minimizer of $Φ$, and $ Φ(x(t))-\min_{\mathcal H}Φ= o(t^{-2})$. Strong convergence is established in various practical situations. For the strongly convex case, convergence can be arbitrarily fast depending on the choice of $α$. More precisely, we have $Φ(x(t))- \min_{\mathcal H}Φ= \mathcal O(t^{-\frac{2}{3}α})$. We extend the results to the case of a general proper lower-semicontinuous convex function $Φ: \mathcal H \rightarrow \mathbb R \cup \{+\infty \}$. This is based on the fact that the inertial dynamic with Hessian driven damping can be written as a first-order system in time and space. By explicit-implicit time discretization, this opens a gate to new $-$ possibly more rapid $-$ inertial algorithms, expanding the field of FISTA methods for convex structured optimization problems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity O(1/n^2)

In a Hilbert setting, we introduce a new dynamical system and associated algorithms for solving monotone inclusions by rapid methods. Given a maximal monotone operator $A$, the evolution is governed by the time dependent operator $I -(I + λ(t) {A})^{-1}$, where the positive control parameter $λ(t)$ tends to infinity as $t \to + \infty$. The tuning of $ λ(\cdot) $ is done in a closed-loop way, by resolution of the algebraic equation $λ\norm{(I + λ{A})^{-1}x -x}=θ$, where $θ$ is a positive given constant. The existence and uniqueness of a strong global solution for the Cauchy problem follows from Cauchy-Lipschitz theorem. We prove the weak convergence of the trajectories to equilibria, and superlinear convergence under an error bound condition. When $A =\partial f$ is the subdifferential of a closed convex function $f$, we show a $\bigo(1/t^2)$ convergence property of $f(x(t))$ to the infimal value of the problem. Then, we introduce proximal-like algorithms which can be obtained by time discretization of the continuous dynamic, and which share the same fast convergence properties. As distinctive features, we allow a relative error tolerance for the solution of the proximal subproblem similar to the ones proposed in ~\cite{So-Sv1, So-Sv2}, and a large step condition, as proposed in~\cite{MS1,MS2}. For general convex minimization problems, the complexity is $\bigo(1/n^2)$. In the regular case, we show the global quadratic convergence of an associated proximal-Newton method.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Fast Convergence of an Inertial Gradient-like System with Vanishing Viscosity

In a real Hilbert space $\mathcal H$, we study the fast convergence properties as $t \to + \infty$ of the trajectories of the second-order evolution equation $$ \ddot{x}(t) + \fracα{t} \dot{x}(t) + \nabla Φ(x(t)) = 0, $$ where $\nabla Φ$ is the gradient of a convex continuously differentiable function $Φ: \mathcal H \rightarrow \mathbb R$, and $α$ is a positive parameter. In this inertial system, the viscous damping coefficient $\fracα{t}$ vanishes asymptotically in a moderate way. For $α> 3$, we show that any trajectory converges weakly to a minimizer of $Φ$, just assuming that the set of minimizers is nonempty. The strong convergence is established in various practical situations. These results complement the $\mathcal O(t^{-2})$ rate of convergence for the values obtained by Su, Boyd and Candès. Time discretization of this system, and some of its variants, provides new fast converging algorithms, expanding the field of rapid methods for structured convex minimization introduced by Nesterov, and further developed by Beck and Teboulle. This study also complements recent advances due to Chambolle and Dossal.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Dynamical systems and forward-backward algorithms associated with the sum of a convex subdifferential and a monotone cocoercive operator

In a Hilbert framework, we introduce continuous and discrete dynamical systems which aim at solving inclusions governed by structured monotone operators $A=\partialΦ+B$, where $\partialΦ$ is the subdifferential of a convex lower semicontinuous function $Φ$, and $B$ is a monotone cocoercive operator. We first consider the extension to this setting of the regularized Newton dynamic with two potentials. Then, we revisit some related dynamical systems, namely the semigroup of contractions generated by $A$, and the continuous gradient projection dynamic. By a Lyapunov analysis, we show the convergence properties of the orbits of these systems. The time discretization of these dynamics gives various forward-backward splitting methods (some new) for solving structured monotone inclusions involving non-potential terms. The convergence of these algorithms is obtained under classical step size limitation. Perspectives are given in the field of numerical splitting methods for optimization, and multi-criteria decision processes.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality

We study the convergence properties of an alternating proximal minimization algorithm for nonconvex structured functions of the type: $L(x,y)=f(x)+Q(x,y)+g(y)$, where $f:\R^n\rightarrow\R\cup{+\infty}$ and $g:\R^m\rightarrow\R\cup{+\infty}$ are proper lower semicontinuous functions, and $Q:\R^n\times\R^m\rightarrow \R$ is a smooth $C^1$ function which couples the variables $x$ and $y$. The algorithm can be viewed as a proximal regularization of the usual Gauss-Seidel method to minimize $L$. We work in a nonconvex setting, just assuming that the function $L$ satisfies the Kurdyka-Łojasiewicz inequality. An entire section illustrates the relevancy of such an assumption by giving examples ranging from semialgebraic geometry to "metrically regular" problems. Our main result can be stated as follows: If L has the Kurdyka-Łojasiewicz property, then each bounded sequence generated by the algorithm converges to a critical point of $L$. This result is completed by the study of the convergence rate of the algorithm, which depends on the geometrical properties of the function $L$ around its critical points. When specialized to $Q(x,y)=|x-y|^2$ and to $f$, $g$ indicator functions, the algorithm is an alternating projection mehod (a variant of Von Neumann's) that converges for a wide class of sets including semialgebraic and tame sets, transverse smooth manifolds or sets with "regular" intersection. In order to illustrate our results with concrete problems, we provide a convergent proximal reweighted $\ell^1$ algorithm for compressive sensing and an application to rank reduction problems.

0 citations0 reviewsNo code linkedOpen access