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.


  • Is it really NP-hard?

  • Is it APX-complete?

  • 1
    $\begingroup$ The $NP$-hardness result is folklore since this non convex problem can encode integer linear programming which is $NP$-complete. $\endgroup$ – Mohammad Al-Turkistany Mar 2 '14 at 10:16
  • $\begingroup$ 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? $\endgroup$ – Antonio Valerio Miceli-Barone Mar 3 '14 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.