Algorithms for structured nonconvex optimization: theory and practice
von Hieu Thao Nguyen
Datum der mündl. Prüfung:2017-10-17
Erschienen:2018-07-24
Betreuer:Prof. Dr. Russell Luke
Gutachter:Prof. Dr. Thorsten Hohage
Gutachter:Prof. Dr. Anita Schöbel
Gutachter:Prof. Dr. Anja Sturm
Gutachter:Prof. Dr. Ralf Meyer
Gutachter:Prof. Dr. Alexander Kruger
Dateien
Name:Thesis_Hieu_Thao_Nguyen_electronic_2.pdf
Size:1.09Mb
Format:PDF
Zusammenfassung
Englisch
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 convergence theory are illustrated and simulated for the source location and phase retrieval problems.
Keywords: numerical analysis; regularity property; nonconvex optimization method; transversality; subtransversality; metric regularity; necessary condition for convergence; phase retrieval; source location problem