Optimization Online


iPiano: Inertial Proximal Algorithm for Nonconvex Optimization

Peter Ochs (ochs***at***cs.uni-freiburg.de)
Yunjin Chen (cheny***at***icg.tugraz.at)
Thomas Brox (brox***at***cs.uni-freiburg.de)
Thomas Pock (pock***at***icg.tugraz.at)

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.

Download: [PDF]

Entry Submitted: 06/28/2014
Entry Accepted: 06/28/2014
Entry Last Modified: 01/10/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society