Operator Splitting Methods: Certificates and Second-Order Acceleration

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

This research project is centered on development of improved numerical algorithms for application to large-scale systems that include, for example, signal/image/video reconstruction and processing, bioinformatics, and automated learning or mining of information from very large data sets. Operator splitting is a class of methods that decomposes a difficult problem into simple sub-problems. Within the past decade, operator splitting methods gained popularity due to the growing demand to handle ever-larger models. For example, signal processing and machine learning applications often have multiple parts that are easy to handle separately but are very challenging when combined. Ideas from operator splitting have led to efficient algorithms for broad classes of objective functions that are used to define the underlying systems. There is still, however, much to be done to handle complex situations. Through further development of operator splitting techniques, this research has the potential to provide efficient and stable approaches to solve a yet wider class of challenging problems. The project also includes educational impact through the development of courses, presentation of seminars, and graduate student training opportunities. The principal investigator intends to design and implement algorithms that improve the speed and stability of operator splitting methods. This project aims to extend the principle of operator splitting in two ways. First, operator splitting algorithms will be introduced that recognize infeasible and feasible-but-unbounded optimization problems, as well as those that have finite optimal values but unattainable solutions. Such pathological problems are not rare and cripple existing techniques. The new algorithms will address these pathologies and make future solvers more robust. Second, by incorporating second-order information in a novel fashion, the project will address two significant drawbacks of operator splitting algorithms. These are the slow tail convergence, and the sensitivity to severe problem conditions. Techniques to ensure global convergence will be developed. Because operator splitting is a high-level abstraction, the results of the project will apply to a broad range of numerical methods that arise in science and engineering.