# Complexity of the Transductive SVM training problem

The Transductive Support Vector Machine training problem is a non-convex mixed integer programming problem:

Transductive Support Vector Machine training problem. \begin{align} \mathop{\text{minimize}}_{\xi,\theta,b,u} \;&\|\theta\|^2 + C \sum_{i=1}^{m+k} \xi_i \\[1ex] \text{subject to:}\; &y^{(i)}(\theta^T x^{(i)}-b) \geqslant 1-\xi_i, \quad\text{for } \; i=1, \ldots, m\\ &u_i\;\;(\theta^T x^{(i)}-b) \geqslant 1-\xi_i, \quad\text{for }\; i=m, \ldots, m+k\\ &u_i \in \{-1, 1\}\\ &\xi_i \geqslant 0 \end{align} where $C > 0$, and:

• $x^{(1)},\dots,x^{(m+k)} \in \mathbb{R}^n$ are data points;
• $y^{(1)},\dots,y^{(m)} \in \{-1, 1\}$ are labels provided for $1 \leqslant i \leqslant m$
(the vectors $x^{(i)}$ are missing labels for $i > m$).

If I recall correctly, it can be proved that this problem is NP-hard, but I can't find a reference to that claim.

Questions.

• Is it really NP-hard?

• Is it APX-complete?

• The $NP$-hardness result is folklore since this non convex problem can encode integer linear programming which is $NP$-complete. – Mohammad Al-Turkistany Mar 2 '14 at 10:16
• Although I find this intuitively plausible, it's not obvious to me how to encode an arbitrary integer linear programming problem into a transductive SVM training problem. May you please explain how it's done? – Antonio Valerio Miceli-Barone Mar 3 '14 at 16:17