CAREER: The Interplay between Combinatorial Optimization and Algorithmic Convex Geometry

寻找满足给定约束条件的最佳解决方案的优化问题可能出现在离散设置中，其中存在一组不同可能性的选择，如图中的节点，或连续设置，其中选择是可以通过微调调整的数字。凸优化问题是一类特殊的问题，其中的约束足够简单，连续问题获得几何和/或离散结构。在过去一个世纪里，人们对这些结构进行了广泛的研究。其中一些技术，如线性规划，已经成为所有科学领域的基本工具。最近，有一些有趣的案例，其中连续方法在离散优化方面取得了进展。在这个项目中，PI寻求开发更有效的算法来解决凸问题，特别是来自图和组合问题的问题。开发用于连续和离散问题的近线性时间算法的主要障碍是缺乏对凸几何及其与算法的联系的理解。本项目重点关注三个关键主题和相关目标：1)算法凸几何：了解凸集如何很好地由椭球体近似（KLS猜想），探索将显式给定多面体变形为黎曼流形的方法，并使用变形来开发更快的多面体采样算法；2)组合优化：通过理解凸几何与内点法之间的关系，打破求解线性规划的平方根迭代障碍，发展内点法的细粒度复杂度；3)凸优化：通过定位集几何研究切割平面方法，通过算法凸几何开发高效切割平面方法，通过采样算法探索非凸优化。通过改进对这些主题的理解，本项目开发的优化算法可以在各个科学领域产生广泛的影响。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Optimization problems, which look for the best solution satisfying given constraints, may arise in discrete settings, where there is a choice of a distinct set of possibilities like nodes in a graph, or continuous settings, where the choices are numbers that can be tuned with fine adjustments. Convex optimization problems are a special class in which the constraints are simple enough that continuous problems gain geometric and/or discrete structures. These structures have been studied extensively over the past century. Some of these techniques like linear programming have become fundamental tools in all fields of science. More recently, there have been interesting cases in which continuous methods have yielded advances in discrete optimization. In this project, the PI seeks to develop significantly more efficient algorithms to solve convex problems, especially problems come from graph and combinatorial problems. A major obstacle to developing nearly linear-time algorithms for both continuous and discrete problems is the lack of understanding of convex geometry and its connection to algorithms. This project focuses on three key topics and related goals: 1) Algorithmic Convex Geometry: understand how well convex sets can be approximated by ellipsoids (KLS conjecture), explore ways to deform an explicit given polytope as a Riemannian manifold and use the deformations to develop faster polytope sampling algorithms; 2) Combinatorial Optimization: break the square root iterations barrier for solving linear programming by understanding the relation between convex geometry and interior point methods to develop a fine-grained complexity for interior point methods; 3) Convex Optimization: investigate cutting plane methods via the geometry of localization sets, develop efficient cutting plane methods via algorithmic convex geometry and explore non-convex optimizations via sampling algorithms. Improved algorithms for optimization developed via this project through an improved understanding of these topics can have a broad impact across various sciences.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.