An inertial forward–backward algorithm for the minimization of the sum of two nonconvex functions

详细信息    查看全文

• 作者：Radu Ioan Boţ ; Ernö Robert Csetnek…
• 关键词：Nonsmooth optimization ; Limiting subdifferential ; Kurdyka ; Łojasiewicz inequality ; Bregman distance ; Inertial proximal algorithm
• 刊名：EURO Journal on Computational Optimization
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：4
• 期：1
• 页码：3-25
• 全文大小：1,701 KB
• 参考文献：Alvarez F (2000) On the minimizing property of a second order dissipative system in Hilbert spaces. SIAM J Control Optim 38(4):1102–1119CrossRef
  Alvarez F (2004) Weak convergence of a relaxed and inertial hybrid projection-proximal point algorithm for maximal monotone operators in Hilbert space. SIAM J Optim 14(3):773–782CrossRef
  Alvarez F, Attouch H (2001) An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping. Set Valued Anal 9:3–11CrossRef
  Attouch H, Bolte J (2009) On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math Program 116(1–2):5–16 Series BCrossRef
  Attouch H, Bolte J, Redont P, Soubeyran A (2010) Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality. Math Operat Res 35(2):438–457CrossRef
  Attouch H, Bolte J, Svaiter BF (2013) Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math Program Ser A 137(1–2):91–129CrossRef
  Attouch H, Peypouquet J, Redont P (2014) A dynamical approach to an inertial forward-backward algorithm for convex minimization. SIAM J Optim 24(1):232–256CrossRef
  Bauschke HH, Combettes PL (2011) Convex analysis and monotone operator theory in hilbert spaces, CMS books in mathematics. Springer, New YorkCrossRef
  Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J Imag Sci 2(1):183–202CrossRef
  Bertsekas DP (1999) Nonlinear programming, 2nd edn. Athena Scientific, Cambridge
  Bolte J, Daniilidis A, Lewis A (2006) The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J Optim 17(4):1205–1223CrossRef
  Bolte J, Daniilidis A, Lewis A, Shiota M (2007) Clarke subgradients of stratifiable functions. SIAM J Optim 18(2):556–572CrossRef
  Bolte J, Daniilidis A, Ley O, Mazet L (2010) Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity. Trans Am Math Soc 362(6):3319–3363CrossRef
  Bolte J, Sabach S, Teboulle M (2014) Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math Program Ser A 146(1–2):459–494CrossRef
  Boţ RI, Csetnek ER (2015) An inertial forward-backward-forward primal-dual splitting algorithm for solving monotone inclusion problems. Numer Algorithms. doi:10.​1007/​s11075-015-0007-5
  Boţ RI, Csetnek ER (2015) An inertial alternating direction method of multipliers. Minimax Theory Appl, 1(1). arXiv:​1404.​4582
  Boţ RI, Csetnek ER (2015) A hybrid proximal-extragradient algorithm with inertial effects. Numer Funct Anal Optim. 36(8):951–963CrossRef
  Boţ RI, Csetnek ER (2015) An inertial Tseng’s type proximal algorithm for nonsmooth and nonconvex optimization problems. J Optim Theory Appl. doi:10.​1007/​s10957-015-0730-z
  Boţ RI, Csetnek ER, Hendrich C (2015) Inertial Douglas-Rachford splitting for monotone inclusion problems. Appl Math Comput 256:472–487CrossRef
  Cabot A, Frankel P (2011) Asymptotics for some proximal-like method involving inertia and memory aspects. Set Valued Var Anal 19:59–74CrossRef
  Chan RH, Yang J, MA S (2014) Inertial primal-dual algorithms for structured convex optimization. arXiv:​1409.​2992v1
  Chen C, Yang J, Ma S (2014) A general inertial proximal point method for mixed variational inequality problem. arXiv:​1407.​8238v2
  Chouzenoux E, Pesquet J-C, Repetti A (2014) Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function. J Optim Theory Appl 162(1):107–132CrossRef
  Combettes PL (2004) Solving monotone inclusions via compositions of nonexpansive averaged operators. Optimization 53(5–6):475–504CrossRef
  Frankel P, Garrigos G, Peypouquet J (2015) Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates. J Optim Theory Appl 165(3):874–900CrossRef
  Hesse R, Luke DR, Sabach S, Tam MK (2014) Proximal heterogeneous block input-output method and application to blind ptychographic diffraction imaging. arXiv:​1408.​1887v1
  Kurdyka K (1998) On gradients of functions definable in o-minimal structures. Annales de l’institut Fourier (Grenoble) 48(3):769–783CrossRef
  Łojasiewicz S (1963) Une propriété topologique des sous-ensembles analytiques réels. Les Équations aux Dérivées Partielles, Éditions du Centre National de la Recherche Scientifique Paris, pp 87–89
  Maingé P-E (2008) Convergence theorems for inertial KM-type algorithms. J Comput Appl Math 219:223–236CrossRef
  Maingé P-E, Moudafi A (2008) Convergence of new inertial proximal methods for dc programming. SIAM J Optim 19(1):397–413CrossRef
  Mordukhovich B (2006) Variational analysis and generalized differentiation, I: basic theory, II: applications. Springer, Berlin
  Moudafi A, Oliny M (2003) Convergence of a splitting inertial proximal method for monotone operators. J Comput Appl Math 155:447–454CrossRef
  Nesterov Y (2004) Introductory lectures on convex optimization: a basic course. Kluwer Academic Publishers, DordrechtCrossRef
  Ochs P, Chen Y, Brox T, Pock T (2014) iPiano: inertial proximal algorithm for non-convex optimization. SIAM J Imag Sci 7(2):1388–1419CrossRef
  Pesquet J-C, Pustelnik N (2012) A parallel inertial proximal optimization method. Pac J Optim 8(2):273–306
  Rockafellar RT, Wets RJ-B (1998) Variational analysis, fundamental principles of mathematical sciences 317. Springer, Berlin
  
• 作者单位：Radu Ioan Boţ (1)
  Ernö Robert Csetnek (1)
  Szilárd Csaba László (2)
  
  1. Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz 1, 1090, Vienna, Austria
  2. Department of Mathematics, Technical University of Cluj-Napoca, 400027, Cluj-Napoca, Romania
  
• 刊物主题：Operations Research/Decision Theory; Production/Logistics/Supply Chain; Operations Research, Management Science; Optimization;
• 出版者：Springer Berlin Heidelberg
• ISSN：2192-4414

文摘

We propose a forward–backward proximal-type algorithm with inertial/memory effects for minimizing the sum of a nonsmooth function with a smooth one in the nonconvex setting. Every sequence of iterates generated by the algorithm converges to a critical point of the objective function provided an appropriate regularization of the objective satisfies the Kurdyka-Łojasiewicz inequality, which is for instance fulfilled for semi-algebraic functions. We illustrate the theoretical results by considering two numerical experiments: the first one concerns the ability of recovering the local optimal solutions of nonconvex optimization problems, while the second one refers to the restoration of a noisy blurred image.