0-1 Semidefinite Programming: Modeling, Theoretical Foundation, Resolution and Applications

该奖项是根据2009年美国复苏和再投资法案(公共法律111-5)资助的。0-1半定规划(0-1 SDP)是一种新的优化模型，涵盖了几类具有挑战性的非线性整数规划问题。在学习、通信和设施选址等领域的大量应用中，经常会出现0-1个SDP。然而，尽管新的优化模型有着广泛的应用范围和计算上的挑战，但人们对它知之甚少，除了文献中零散的几个结果。在这个项目中，Pi和他的研究小组将研究0-1 SDP模型的理论基础，包括从优化的角度识别该模型的多项式可解情况并探索其理论局限性，为这类新问题开发解决技术，如有效的精确算法和能够处理大规模问题的可伸缩逼近算法，并将新的建模和解决技术应用于不同学科的问题。该项目的主要目标是研究一种可应用于学习和工程设计等广泛领域的新的优化模型，并为该模型开发可靠且可扩展的求解工具。创造性的建模技术对于捕捉许多应用程序中的问题语义至关重要。例如，在多智能体学习中，每个智能体对同一问题可能有不同的目标和解决方案。重要的是要整合代理人的各种意见和解决方案，以便更全面地了解和实现一个全球目标。该优化模型为多智能体的学习提供了一种强有力的方法。可靠和可扩展的计算方法对于从海量和噪声数据集中进行学习是必不可少的。

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).0-1 Semidefinite Programming (0-1 SDP) is a new optimization modelthat covers several classes of challenging nonlinear integerprogramming problems. 0-1 SDPs arise frequently from numerousapplications in various domains such as learning, communications andfacility location. However, in spite of its broad range ofapplications and the computational challenge it poses, little isknown with respect to the new optimization model except few resultsscattered in the literature. In this project, the PI and hisresearch group will study the theoretical foundations of the 0-1 SDPmodel including identifying polynomially solvable cases of the modeland exploring its theoretical limitations from an optimizationperspective, develop resolution techniques for this new class ofproblems such as effective exact algorithms and scalableapproximation algorithms that can deal with large size problems, andapply the new modeling and resolution techniques to problems fromvarious disciplines.The primary goal of the project is to study a new optimizationmodel that can be applied to a broad range of domains such aslearning and engineering design, and to develop reliable and scalableresolution tools for such a model. Creative modeling techniques arecrucial for capturing the problem semantics in many applications. Forexample, in multi-agent learning, every agent might have adifferent objective and solution to the same problem. It isimportant to integrate various opinions and solutions from theagents to have a more comprehensive understanding and achieve aglobal objective. The new optimization model in this projectprovides a powerful approach for multi-agent learning. Reliableand scalable computational methods are essential for learning frommassive and noisy data set.