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

0-1半定规划：建模、理论基础、解析和应用

• 批准号: 0915240
• 负责人: Jiming Peng
• 金额: $ 22.5万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-07-01 至 2013-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0915240&HistoricalAwards=false
• 关键词: Semidefinite; Programming; Modeling; Theoretical; Foundation

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.

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。0 -1半定规划（0-1 SDP）是一种新的优化模型，涵盖了几类具有挑战性的非线性整数规划问题。0-1 SDP经常出现在学习、通信和设施定位等各个领域的大量应用中。然而，尽管其广泛的应用范围和计算的挑战，它构成的，鲜为人知的是关于新的优化模型，除了一些结果分散在文献中。在这个项目中，PI和他的研究小组将研究0-1 SDP模型的理论基础，包括识别模型的多项式可解情况，并从优化的角度探索其理论局限性，开发这类新问题的解决技术，例如有效的精确算法和可扩展的近似算法，可以处理大规模问题，该项目的主要目标是研究一种新的优化模型，可以应用于广泛的领域，如学习和工程设计，并开发可靠的和可扩展的解决工具，这样一个模型。 创造性的建模技术对于捕获许多应用程序中的问题语义至关重要。例如，在多智能体学习中，每个智能体可能对同一问题有不同的目标和解决方案。如何综合各代理商的意见和解决方案，对该问题有更全面的认识，达到更好的解决目标，是非常重要的。该项目中新的优化模型为多智能体学习提供了一种强有力的方法。可靠的、可扩展的计算方法是从大量噪声数据中学习的必要条件。