Collaborative Research: AF: Medium: Fundamental Challenges in Optimization

University Of Washington, Seattle WA

Investigators

Abstract

Efficient Optimization is the bedrock of modern computation. Progress over the last century has led to powerful techniques to solve problems from myriad applications. The complexity of basic questions such as solving linear systems, linear programs and integer programs is at the core of the theory of algorithms. The goal of this project is to advance the field by addressing challenging problems on the frontier of efficient optimization. New algorithms for the problems considered would be of direct interest to many disciplines in science and engineering. The project includes a research workshop targeted at junior researchers, as well as a video tutorial course by the team of investigators on contemporary techniques in optimization. Research findings from the project are being incorporated into courses on “Continuous Algorithms”, “Spectral Algorithms” and “Integer and Linear Programming”. Course content and software resulting from the project is being made publicly available. The focus problems of this project range from continuous to discrete: (1) sparse general Linear Systems, (2) sparse Linear Programs and p-norm minimization, (3) using Semi-definite Programs for efficient low-rank approximation to combinatorial optimization problems, (4) advancing the continuous approach to discrete optimization and (5) resolving the complexity of integer programming. Recent progress on discrete optimization has relied heavily on inspiration and analysis from continuous methods, while the solution of continuous optimization problems often uses graph theory. It is anticipated that new techniques bridging this spectrum, and of broad, general applicability, will be developed. The connections to operations research, numerical analysis, stochastic processes (including various types of diffusion), homotopy methods, graph theory, geometric properties of convexity and the theory of lattices are being enhanced. 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.