Algorithms for structured nonconvex optimization: theory and practice

by Hieu Thao Nguyen
Doctoral thesis
Date of Examination:2017-10-17
Date of issue:2018-07-24
Advisor:Prof. Dr. Russell Luke
Referee:Prof. Dr. Thorsten Hohage
Referee:Prof. Dr. Anita Schöbel
Referee:Prof. Dr. Anja Sturm
Referee:Prof. Dr. Ralf Meyer
Referee:Prof. Dr. Alexander Kruger
Persistent Address: http://dx.doi.org/10.53846/goediss-6943

 

 

Files in this item

Name:Thesis_Hieu_Thao_Nguyen_electronic_2.pdf
Size:1.09Mb
Format:PDF

The following license files are associated with this item:

Abstract

English

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
 
Statistik