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

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

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.