Conic Relaxations for Semi-supervised Support Vector Machines

详细信息    查看全文

• 作者：Yanqin Bai ; Xin Yan
• 刊名：Journal of Optimization Theory and Applications
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：169
• 期：1
• 页码：299-313
• 全文大小：599 KB
• 刊物主题：Calculus of Variations and Optimal Control; Optimization; Optimization; Theory of Computation; Applications of Mathematics; Engineering, general; Operations Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2878
• 卷排序：169

文摘

Semi-supervised support vector machines arise in machine learning as a model of mixed integer programming problem for classification. In this paper, we propose two convex conic relaxations for the original mixed integer programming problem. The first one is a new semi-definite relaxation, and its possibly maximal ratio of the optimal value is estimated approximately. The second one is a doubly nonnegative relaxation, which is relaxed from a well-known conic programming problem called completely positive programming problem that is equivalent to the original problem. Furthermore, we prove that the doubly nonnegative relaxation is tighter than the semi-definite relaxation. Finally, the numerical results show that two proposed relaxations not only generate proper classifiers but also outperform some existing methods in classification accuracy.KeywordsSemi-supervised support vector machinesConvex conic relaxationSemi-definite relaxationCompletely positive programmingDoubly nonnegative relaxation