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.