iPiano: Inertial Proximal Algorithm for Nonconvex Optimization
Peter Ochs (ochscs.uni-freiburg.de)
Abstract: In this paper we study an algorithm for solving a minimization problem composed of a differentiable (possibly nonconvex) and a convex (possibly nondifferentiable) function. The algorithm iPiano combines forward-backward splitting with an inertial force. It can be seen as a nonsmooth split version of the Heavy-ball method from Polyak. A rigorous analysis of the algorithm for the proposed class of problems yields global convergence of the function values and the arguments. This makes the algorithm robust for usage on nonconvex problems. The convergence result is obtained based on the Kurdyka-Lojasiewicz inequality. This is a very weak restriction, which was used to prove convergence for several other gradient methods. First, an abstract convergence theorem for a generic algorithm is proved, and, then iPiano is shown to satisfy the requirements of this theorem. Furthermore, a convergence rate is established for the general problem class. We demonstrate iPiano on computer vision problems: image denoising with learned priors and diffusion based image compression.
Keywords: nonconvex optimization, Heavy-ball method, inertial forward-backward splitting, Kurdyka-Lojasiewicz inequality, proof of convergence
Category 1: Nonlinear Optimization
Citation: SIAM Journal on Imaging Sciences, 7(2):1388–1419, 2014.
Entry Submitted: 06/28/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|