Closing the Duality Gap: Decomposition of High-Dimensional Nonconvex Optimization

缩小对偶差距：高维非凸优化的分解

• 批准号: 1619818
• 负责人: Mengdi Wang
• 金额: $ 20万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1619818&HistoricalAwards=false
• 关键词: Closing; Duality; Gap; Decomposition; Dimensional

In the modern computerized age, nonconvex optimization remains a critical computational challenge. Nonconvexity of an optimization problem implies a combinatorial structure, which often makes the computation problem fundamentally hard. Efficient computation tools with global approximation guarantees are in high demand. The principal investigator will study a class of nonconvex optimization problems that naturally arise from distributed intelligence systems, sparse estimation and data analysis. The proposed research will contribute new computation tools for data analytics, statistic and machine learning, distributed and parallel computing, and multi-agent intelligence systems. The project will also develop two new courses for both undergraduate and graduate students at Princeton and also will involve undergraduate students in the research project via the Princeton undergraduate summer research program.This research project aims to tackle an important class of nonconvex problems utilizing their geometric structure via a systematic dualization approach. The result is expected to advance the non-convex optimization theory as well as to provide algorithmic solutions to a large variety of distributed systems. Specifically, the principal investigator plans to study the non-convex duality for a class of non-convex optimization problems that admit a near-separable structure, with extensions to minimax problems and variational inequalities, and to develop computation tools that produce approximate global optimal solutions with complexity guarantees. In addition to the fundamental aspects, the principal investigator aims to investigate practical algorithms tailored to specific problems in high-dimensional structural estimation, sparse learning, and distributed optimization. The theoretical results and new methodology are expected to advance the theory of non-convex optimization as well as to provide algorithmic solutions to a variety of computational challenges.

在现代计算机化时代，非凸优化仍然是一个关键的计算挑战。优化问题的非凸性意味着组合结构，这通常使计算问题从根本上变得困难。具有全局近似保证的高效计算工具的需求量很大。首席研究员将研究一类由分布式智能系统、稀疏估计和数据分析自然产生的非凸优化问题。 拟议的研究将为数据分析、统计和机器学习、分布式和并行计算以及多智能体智能系统提供新的计算工具。该项目还将为普林斯顿大学的本科生和研究生开发两门新课程，并将通过普林斯顿大学本科生暑期研究计划让本科生参与该研究项目。该研究项目旨在利用其几何结构解决一类重要的非凸问题通过系统的二元化方法。该结果预计将推进非凸优化理论，并为各种分布式系统提供算法解决方案。具体来说，首席研究员计划研究一类承认近可分离结构的非凸优化问题的非凸对偶性，并扩展到极小极大问题和变分不等式，并开发产生近似全局最优解的计算工具具有复杂性保证。除了基本方面之外，主要研究者还致力于研究针对高维结构估计、稀疏学习和分布式优化中的特定问题量身定制的实用算法。理论结果和新方法有望推进非凸优化理论，并为各种计算挑战提供算法解决方案。