Collaborative Research: Second-Order Variational Analysis in Structured Optimization and Algorithms with Applications

Oakland University, Rochester MI

Investigators

Abstract

This project focuses on developing advanced tools of mathematical analysis to investigate modern structured optimization problems and building efficient algorithms to solve them. These problems arise in different areas of science and engineering, including massive data analysis, machine learning, signal processing, medical image reconstruction, statistics, traffic and logistical networks, and operations research. Most of them share the irregular phenomenon of nonsmoothness or nonconvexity that challenges computation. Despite several practically successful algorithms recently proposed to solve such problems, the underlying fundamental theory is not quite understood and explored. Only analyzing the complexity and the deep mathematics behind these problems and algorithms provides practitioners across related, vital science and engineering areas new tools to comprehend their core features, be able to design more efficient algorithms, and attack more challenging problems arising from practice. The investigators develop such tools via a novel approach from a relatively young subfield of applied mathematics, variational analysis, which is naturally compatible with these nonsmooth and complex structures. Several topics from this project are integrated with teaching topic courses and training of students. This project is devoted to developing the theory of second-order variational analysis (SOVA) and using it to study the stability, sensitivity, and computational complexity of algorithms for solving structured optimization problems. The first part of this project serves as the theoretical foundation; it concerns the theory of SOVA with connections to stability and sensitivity analysis. More specifically, the investigators intend to study: (i) tilt stability and full stability for general optimization problems with connections to Robinson's strong regularity and Kojima's strong stability for conic programming via SOVA; (ii) metric (sub)regularity of the subdifferential and Kurdyka-Lojasiewicz property on nonsmooth (possibly nonconvex) functions via SOVA; and (iii) stability for parametric variational systems including Nash equilibrium systems and variational inequalities via SOVA. The second part of this project consists of designing and analyzing proximal algorithms for solving convex and nonconvex structured problems. Immediate applications include Lasso, group Lasso, elastic net, basic pursuit, sparsity, low-rank problems, and completion matrix problems that originate from compressed sensing, image reconstruction, machine learning, and data science. Stability theory developed in the first part plays a significant role here, especially in the complexity analysis of these algorithms. It explains why the development of many recent proximal algorithms is strongly influenced by the hidden power of SOVA. The specific objectives of this part are: (i) to accelerate the forward-backward splitting method and analyze the phenomenon of linear convergence encountered frequently in numerical experiments; and (ii) to design efficient methods of Douglas-Rachford splitting type for solving nonconvex optimization and feasibility problems. Other important applications include inverse problems corrupted by Poisson noise and total variation denoising models, both of which are well recognized in imaging science and statistical learning. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.