Project Summary

0-1 SDP is a novel optimization model introduced in recent years. It targets at minimizing an objective function where the involved matrix argument has to be a projection matrix. The model can be viewed as a natural extension of the classical integer programming to the setting of conic constraints. Many challenging mixed integer nonlinear optimization problems from various disciplines such as data mining, communication and chemical processing can be embedded into this new model, which can be further relaxed to polynomially solvable conic optimization problems. In this project, we try to identify classes of 0-1 SDPs that can be solved in polynomial time, develop efficient approximation algorithms to 0-1 SDPs and use the theoretical analysis to guide the model and feature selection process.

Sample Publications and Reference

[1] J. Peng and Y. Wei, Approximating K-means-type clustering via semidefinite programming. SIAM J. Optimization. 18 (2007), no. 1, 186–205.
[2] V. Singh, L. Mukherjee, J. Peng and J. Xu. Ensemble Clustering using Semidefinite Programming with applications. Machine Learning , Vol 79 (1-2), 177-200, 2010.
[3] H.R. Chen and J. Peng, 0-1 Semidefinite Programming for Graph-Cut Clustering: Modelling and Approximation. Invited paper for CRM Proceedings& Lecture Notes of the American Mathematical Society, 2008.
[4] M. Heath, P. Jiang, J. Peng and R. Yang. Finding the densest k-subgraph via 1-mean clustering and low-dimension approximation.

Participants:

PrincipaI Investigator: Jiming Peng.

PhD student:               R. Yang.

Sponsor:                     NSF, 2009–2013.