Collaborative Research: AF: Medium: Fundamental Challenges in Optimization

高效优化是现代计算的基石。上个世纪的进步带来了强大的技术来解决无数应用中的问题。求解线性系统、线性规划和整数规划等基本问题的复杂性是算法理论的核心。该项目的目标是通过解决高效优化前沿的挑战性问题来推进该领域。所考虑的问题的新算法将直接引起科学和工程许多学科的兴趣。该项目包括一个针对初级研究人员的研究讲习班，以及一个由调查小组就当代优化技术进行的视频指导课程。该项目的研究成果被纳入“连续算法”、“谱算法”和“整数与线性规划”课程。该项目产生的课程内容和软件正在向公众开放。本项目的重点问题范围从连续到离散：(1)稀疏一般线性系统；(2)稀疏线性规划和p范数最小化；(3)使用半确定规划对组合优化问题进行有效的低秩逼近；(4)推进离散优化的连续方法；(5)解决整数规划的复杂性。离散优化的最新进展很大程度上依赖于连续方法的启发和分析，而连续优化问题的解决通常使用图论。预计将开发出跨越这一范围并具有广泛和普遍适用性的新技术。与运筹学、数值分析、随机过程（包括各种类型的扩散）、同伦方法、图论、凸性的几何性质和格理论的联系正在加强。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.