Algorithms for structured nonconvex optimization: theory and practice

We first synthesize and unify notions of regularity, both of individual functions/sets and of families of functions/sets, as they appear in the convergence theory of fixed point iterations. Several new primal and dual characterizations of regularity notions are presented with the focus on convergence analysis of numerical methods. A theory of almost averaged mappings is developed with a specialization to the projectors and reflectors associated with elemental regular sets. Based on the knowledge of regularity notions, we develop a framework for quantitative convergence analysis of Picard iterations of expansive set-valued fixed point mappings. As application of the theory, we provide a number of results showing local convergence of nonconvex cyclic projections for both inconsistent and consistent feasibility problems, local convergence of the forward–backward algorithm for structured optimization without convexity, and local convergence of the Douglas–Rachford algorithm for structured nonconvex minimization. In particular, we establish a unified and weakest criterion for linear convergence of consistent alternating projections. As preparation for subsequent applications, we also discuss convergence of several relaxed versions of Douglas–Rachford algorithm and the alternating direction method of multipliers (ADMM). Our development of regularity theory also sheds light on the relations between seemingly different ideas and point to possible necessary conditions for local linear convergence of fixed point iterations. We show that metric subregularity is necessary for linear monotonicity of fixed point iterations. This is specialized to an intensive discussion on subtransversality and alternating projections. In particular, we show that subtransversality is not only sufficient but also necessary for linear convergence of convex consistent alternating projections. More general results on gauge metric subregularity as necessary conditions for convergence are also discussed. The algorithms together with their ...