Source author record

Juan Peypouquet

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.OC

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

preprint2016arXiv

From error bounds to the complexity of first-order descent methods for convex functions

This paper shows that error bounds can be used as effective tools for deriving complexity results for first-order descent methods in convex minimization. In a first stage, this objective led us to revisit the interplay between error bounds and the Kurdyka-Łojasiewicz (KL) inequality. One can show the equivalence between the two concepts for convex functions having a moderately flat profile near the set of minimizers (as those of functions with Hölderian growth). A counterexample shows that the equivalence is no longer true for extremely flat functions. This fact reveals the relevance of an approach based on KL inequality. In a second stage, we show how KL inequalities can in turn be employed to compute new complexity bounds for a wealth of descent methods for convex problems. Our approach is completely original and makes use of a one-dimensional worst-case proximal sequence in the spirit of the famous majorant method of Kantorovich. Our result applies to a very simple abstract scheme that covers a wide class of descent methods. As a byproduct of our study, we also provide new results for the globalization of KL inequalities in the convex framework. Our main results inaugurate a simple methodology: derive an error bound, compute the desingularizing function whenever possible, identify essential constants in the descent method and finally compute the complexity using the one-dimensional worst case proximal sequence. Our method is illustrated through projection methods for feasibility problems, and through the famous iterative shrinkage thresholding algorithm (ISTA), for which we show that the complexity bound is of the form $O(q^{k})$ where the constituents of the bound only depend on error bound constants obtained for an arbitrary least squares objective with $\ell^1$ regularization.

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.

preprint2014arXiv

Splitting forward-backward penalty scheme for constrained variational problems

We study a forward backward splitting algorithm that solves the variational inequality \begin{equation*} A x +\nabla Φ(x)+ N_C (x) \ni 0 \end{equation*} where $H$ is a real Hilbert space, $A: H\rightrightarrows H$ is a maximal monotone operator, $Φ: H\to\mathbb{R}$ is a smooth convex function, and $N_C$ is the outward normal cone to a closed convex set $C\subset H$ . The constraint set $C$ is represented as the intersection of the sets of minima of two convex penalization function $Ψ_1:H\to\mathbb{R}$ and $Ψ_2: H\to\mathbb{R}\cup \{+\infty\}$ . The function $Ψ_1$ is smooth, the function $Ψ_2$ is proper and lower semicontinuous. Given a sequence $(β_n)$ of penalization parameters which tends to infinity, and a sequence of positive time steps $(λ_n)$ , the algorithm $\left\{\begin{array}{rcl} x_1 & \in & H,\\ x_{n+1} & = & (I+λ_n A+λ_nβ_n\partialΨ_2)^{-1}(x_n-λ_n\nablaΦ(x_n)-λ_nβ_n\nablaΨ_1(x_n)),\ n\geq 1. \end{array}\right.$ performs forward steps on the smooth parts and backward steps on the other parts. Under suitable assumptions, we obtain weak ergodic convergence of the sequence $(x_n)$ to a solution of the variational inequality. Convergence is strong when either $A$ is strongly monotone or $Φ$ is strongly convex. We also obtain weak convergence of the whole sequence $(x_n)$ when $A$ is the subdifferential of a proper lower-semicontinuous convex function. This provides a unified setting for several classical and more recent results, in the line of historical research on continuous and discrete gradient-like systems.

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.