Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings

作     者：Luke, D. Russell Thao, Nguyen H. Tama, Matthew K. 

作者机构：Univ Gottingen Inst Numer & Angew Math D-37083 Gottingen Germany Delft Univ Technol Delft Ctr Syst & Control NL-2628 CD Delft Netherlands 

出 版 物：《MATHEMATICS OF OPERATIONS RESEARCH》 (运筹学数学)

年 卷 期：2018年第43卷第4期

页      面：1143-1176页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：German-Israeli Foundation [G-1253-304.6] Deutsche Forschungsgemeinschaft Collaborative Research Center SFB755 Deutsche Forschungsgemeinschaft Research Training Alexander von Humboldt Foundation 

主　　题：analysis of algorithms feasibility fixed points Kurdyka-Lojasiewicz inequality linear convergence metric regularity nonconvex nonsmooth proximal algorithms subtransversality transversality 

摘      要：We develop a framework for quantitative convergence analysis of Picard iterations of expansive set-valued fixed point mappings. There are two key components of the analysis. The first is a natural generalization of single-valued averaged mappings to expansive set-valued mappings that characterizes a type of strong calmness of the fixed point mapping. The second component to this analysis is an extension of the well-established notion of metric subregularity-or inverse calmness-of the mapping at fixed points. Convergence of expansive fixed point iterations is proved using these two properties, and quantitative estimates are a natural by-product of the framework. To demonstrate the application of the theory, we prove, for the first time, a number of results showing local linear convergence of nonconvex cyclic projections for inconsistent (and consistent) feasibility problems, local linear convergence of the forward-backward algorithm for structured optimization without convexity, strong or otherwise, and local linear convergence of the Douglas-Rachford algorithm for structured nonconvex minimization. This theory includes earlier approaches for known results, convex and nonconvex, as special cases.