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 model that covers several classes of challenging nonlinear integer programming problems. 0-1 SDPs arise frequently from numerous applications in various domains such as learning, communications and facility location. However, in spite of its broad range of applications and the computational challenge it poses, little is known with respect to the new optimization model except few results scattered in the literature. In this project, the PI and his research group will study the theoretical foundations of the 0-1 SDP model including identifying polynomially solvable cases of the model and exploring its theoretical limitations from an optimization perspective, develop resolution techniques for this new class of problems such as effective exact algorithms and scalable approximation algorithms that can deal with large size problems, and apply the new modeling and resolution techniques to problems from various disciplines.
The primary goal of the project is to study a new optimization model that can be applied to a broad range of domains such as learning and engineering design, and to develop reliable and scalable resolution tools for such a model. Creative modeling techniques are crucial for capturing the problem semantics in many applications. For example, in multi-agent learning, every agent might have a different objective and solution to the same problem. It is important to integrate various opinions and solutions from the agents to have a more comprehensive understanding and achieve a global objective. The new optimization model in this project provides a powerful approach for multi-agent learning. Reliable and scalable computational methods are essential for learning from massive and noisy data set.
