SDP RELAXATION FOR SEMI-SUPERVISED SUPPORT VECTOR MACHINE

Semi-Supervised Support Vector Machine ((SVM)-V-3) is based on applying the margin maximization principle to both labeled and unlabeled sets. The formulation of (SVM)-V-3 leads to a mixed integer nonlinear optimization problem. In this paper we first consider a semidefinite programming (SDP) relaxation to the mixed integer nonlinear optimization problem associated with (SVM)-V-3. To reduce the size of the SDP relaxation formulation, we further modify the SDP problem by decomposing the semidefinite positive matrix into a sequence of small-size matrices. Finally, we apply the modified SDP relaxation to two artificial and five real-world classification problems under a common experimental setting. The numerical examples show that the modified SDP relaxation is effective. In particular, the relative error of the modified SDP relaxation is within 3% for protein classification test problems.