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.

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