Nonconvex Quadratic Composite Minimization: Theory and Algorithms

• Applicant: Professor Dr. David Russell Luke
• Subject Area: Mathematics
• Term: from 2019 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 434554779

The goal of the proposed research is to develop a complete analysis of the behaviour - from local to global - of first-order algorithms for nonconvex and nonsmooth optimization with quadratic composite structure. The greater dividend of the research is a synthesis of two strains of analysis that have been at the root of the most significant advances in the analysis of algorithms for nonconvex and nonsmooth optimization problems in the last decade. The first is the use of the so-called Kurdyka-Loyasiewicz (KL) inequality, which is central to showing global convergence results with complexity estimates based on function values. The second is based on a generalization of prox-regularity (super-regularity), together with regularity of constraints at the solution set (transversality) to show local linear convergence of algorithm iterates. The first strategy, which is global and can be applied to any optimization problem with semi-algebraic structure, starts with the target optimization problem and proceeds to algorithms as discretizations of dynamical systems whose steady states are the solution to the optimization problem. The second strategy, which is local, starts with a proposed algorithm for solving an optimization problem and applies fixed-point theoretic tools to characterize the behavior of the corresponding Picard iterations. The two kinds of regularity - semi-algebraicity on one hand and super-regularity on the other - lead to different categorizations of nonconvexity that are not always compatible. This results in a gap in the analysis of algorithms, namely the transition from global behavior to local behavior and characterization of limiting behavior of algorithms in the context of the desired optimization problem. Our focus on problems with quadratic composite format allows us to merge the two strains of analysis at a common point of intersection. Capitalizing on these two main strains of analysis and our recent achievements in these areas, several challenging questions revolving around the design of algorithms and their convergence/complexity analysis will be addressed, in particular regarding the mechanism behind quantifiable convergence of new methods for problems lacking standard smoothness, and scalabilty. Our theoretical findings will be translated into implementation of new, practical and efficient algorithms for solving high-impact applied problems.

• DFG Programme: Research Grants
• International Connection: Israel
• International Co-Applicants: Professor Shoham Sabach, Ph.D.; Professor Dr. Marc Teboulle