A new branch-and-bound approach to semi-supervised support vector machine

This paper develops a branch-and-bound algorithm to solve the 2-norm soft margin semi-supervised support vector machine. First, the original problem is reformulated as a non-convex quadratically constrained quadratic programming problem with a simple structure. Then, we propose a new lower bound estimator which is conceptually simple and easy to be implemented in the branch-and-bound scheme. Since this estimator preserves both a high efficiency and a relatively good quality in the convex relaxation, it leads to a high total efficiency in the whole computational process. The numerical tests on both artificial and real-world data sets demonstrate the better effectiveness and efficiency of this proposed approach, which is compared to other well-known methods on different semi-supervised support vector machine models.