An Efficient Approach to Solve the Large-Scale Semidefinite Programming ProblemsReportar como inadecuado

An Efficient Approach to Solve the Large-Scale Semidefinite Programming Problems - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Mathematical Problems in EngineeringVolume 2012 2012, Article ID 764760, 12 pages

Research Article

College of Mechatronics and Automation, National University of Defense Technology, Changsha 410073, China

College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China

Received 21 March 2011; Accepted 17 April 2011

Academic Editor: Shengyong Chen

Copyright © 2012 Yongbin Zheng et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Solving the large-scale problems with semidefinite programming SDP constraints is of great importance in modeling and model reduction of complex system, dynamical system, optimal control, computer vision, and machine learning. However, existing SDP solvers are of large complexities and thus unavailable to deal with large-scale problems. In this paper, we solve SDP using matrix generation, which is an extension of the classical column generation. The exponentiated gradient algorithm is also usedto solve the special structure subproblem of matrix generation. The numerical experiments show that our approach is efficient and scales very well with the problem dimension. Furthermore, the proposed algorithm is applied for a clustering problem. The experimental results on real datasets imply that the proposed approach outperforms the traditional interior-point SDP solvers in terms of efficiency and scalability.

Autor: Yongbin Zheng, Yuzhuang Yan, Sheng Liu, Xinsheng Huang, and Wanying Xu



Documentos relacionados