AF: Small: Collaborative Research: Distributed Quasi-Newton Methods for Nonsmooth Optimization

New York University, New York NY

Investigators

Abstract

Optimization, which finds the inputs to a mathematical function that produce the minimum output, is a workhorse algorithm behind many of the advances in smart devices or applications in the cloud. As data gets larger and more distributed, new ideas are needed to maintain the speed and accuracy of optimization. Operator splitting, which expresses the function to minimize as the sum of two convex functions, one of which is smooth and the other non-differentiable, is an idea that has produced to new first-order optimization methods. This project explores operator splitting with second-order optimization methods, which have faster convergence to the minimum. The focus is on large, distributed, and streaming data sets, so that the resulting general-purpose numerical solvers and embedded systems implementations can support optimization in cyberphysical systems and the Internet-of-Things. The project has as priority the active engagement and training of students and researchers, with specific emphasis on the inclusion of women and under-represented minority groups. This project not only involves collaboration across three top-tier American universities, but also with European research institute, KU Leuven. In specific, this research project seeks to interpret existing methods for structured convex optimization (such as the celebrated ADMM algorithm) as gradient methods applied to specific functions arising from the original problem formulation, and interpret of operator-splitting techniques as fixed point iterations for appropriately selected operators. A key theoretical foundation is the introduction of new envelope functions (smooth upper approximations possessing the same sets of solutions) that can be used as merit functions for variable-metric backtracking line-search. To conclude, a principal focus of the project is to design distributed asynchronous methods applicable to large-scale multi-agent cyberphysical systems that involve big data and impose stringent real-time constraints for decision-making. In this purview, the goal is to deliver methods that will outperform current state-of-the-art in terms of (a) speed of computations, (b) scalability with big data sizes, (c) robustness to various types of uncertainty, and, most topically, (d) distributed asynchronous implementation over networks in real-time. The merits will be illustrated in the context of applications in signal processing, control, machine learning and robotics. 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.