CAREER: The Interplay between Combinatorial Optimization and Algorithmic Convex Geometry

职业：组合优化和算法凸几何之间的相互作用

• 批准号: 1749609
• 负责人: Yin Tat Lee
• 金额: $ 50万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-03-15 至 2023-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1749609&HistoricalAwards=false
• 关键词: CAREER; Interplay; between; Combinatorial; Optimization

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.

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

项目成果

A Faster Interior Point Method for Semidefinite Programming

• DOI: 10.1109/focs46700.2020.00089
• 发表时间: 2020-09
• 期刊: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Haotian Jiang;Tarun Kathuria;Y. Lee;Swati Padmanabhan;Zhao Song

A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path

• DOI: 10.1145/3406325.3451056
• 发表时间: 2020-11
• 期刊: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Sally Dong;Y. Lee;Guanghao Ye

Private Convex Optimization in General Norms

• DOI: 10.48550/arxiv.2207.08347
• 发表时间: 2022-07
• 作者: Sivakanth Gopi;Y. Lee;Daogao Liu;Ruoqi Shen;Kevin Tian

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

中等密集图上近线性时间的二分匹配

• DOI: 10.1109/focs46700.2020.00090
• 发表时间: 2020
• 作者: van den Brand, Jan;Lee, Yin-Tat;Nanongkai, Danupon;Peng, Richard;Saranurak, Thatchaphol;Sidford, Aaron;Song, Zhao;Wang, Di
• 通讯作者: Wang, Di

A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions

• 发表时间: 2021-12
• 作者: Damek Davis;D. Drusvyatskiy;Y. Lee;Swati Padmanabhan;Guanghao Ye