Optimization serves a wide variety of vital scientific and engineering applications, from machine learning and the statistics of big data, to robust control systems. Contemporary practice of computational optimization is, however, too often divorced from its classical mathematical roots. The scholarship and fast computational technology that has matured from decades of research on smooth optimization has had huge applied scientific impact. It is well known that behind any superlinear acceleration always lurk Newtonian ideas. By contrast, while an elegant and powerful theory of nonsmooth optimization has also matured, nonsmooth computational practice appears far more challenging. Without explicit algebraic structure, practitioners resort to black-box algorithms, convenient but slow. Despite much research, effective Newtonian ideas have remained conspicuously absent. The PI bridges this disciplinary chasm, bringing to bear expertise in the requisite mathematics of "nonsmooth" phenomena beyond the reach of traditional calculus, while developing algorithms with dramatic potential impact. Cornell doctoral students engage widely in the project, on foundations and computing, publishing and presenting at conferences, and collaborating with the PI through seminars and teaching. Cornell's Operations Research program trains doctoral students (typically one third of whom are women) for both academia and industry, striving to support underrepresented minorities. The PI will disseminate this research through graduate texts, broad-audience surveys, diverse collaboration, and international lectures for audiences across science and engineering.
This structure dilemma in nonsmooth optimization is, however, a false dichotomy, and one that Newtonian ideas can transform. The PI pursues a semi-structured middle ground, fertile for fast algorithms. Even without explicit presentations, concrete objectives typically boast a rich inherent variational-analytic structure, well approximated by computationally-amenable nonsmooth models. The project's attack is two-pronged: "partly smooth" structure drives a Newtonian alternating-projection-inspired method for variational inequalities, while the availability of approximating models drives an innovative "bundle Newton" algorithm that shows early computational promise. Fundamental to this project is the development of such methods into robust practical algorithms with sound theoretical foundations. Immediate target applications include moderately-sized models, from robust control, for example. However, such second-order ideas could also accelerate larger-scale first-order methods for signal processing, machine learning, and high-dimensional statistics. The PI leverages the exciting interplay between variational analysis and more classical mathematical domains: semi-algebraic geometry, in particular, serves as an illuminating arena for "concrete" objectives, and matrix spectral analysis offers a rich computational testbed for nonsmooth ideas.
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.
