<p>The <a href="http://en.wikipedia.org/wiki/Support_vector_machine#Transductive_support_vector_machines" rel="nofollow">Transductive Support Vector Machine training problem</a> is a non-convex mixed integer programming problem:</p>

<blockquote>
  <p><strong>Transductive Support Vector Machine training problem.</strong>
  $$
\begin{align}
\mathop{\text{minimize}}_{\xi,\theta,b,u} \;&amp;\|\theta\|^2 + C \sum_{i=1}^{m+k} \xi_i \\[1ex]
\text{subject to:}\;
&amp;y^{(i)}(\theta^T x^{(i)}-b) \geqslant 1-\xi_i, \quad\text{for } \; i=1, \ldots, m\\
&amp;u_i\;\;(\theta^T x^{(i)}-b) \geqslant 1-\xi_i, \quad\text{for }\; i=m, \ldots, m+k\\
&amp;u_i \in \{-1, 1\}\\
&amp;\xi_i \geqslant 0
\end{align}
$$
  where $C &gt; 0$, and:</p>
  
  <ul>
  <li>$x^{(1)},\dots,x^{(m+k)} \in \mathbb{R}^n$ are data points;</li>
  <li>$y^{(1)},\dots,y^{(m)} \in \{-1, 1\}$ are labels provided for $1 \leqslant i \leqslant m$ <br>(the vectors $x^{(i)}$ are missing labels for $i &gt; m$). </li>
  </ul>
</blockquote>

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

<p><strong>Questions.</strong></p>

<ul>
<li><p>Is it really NP-hard?</p></li>
<li><p>Is it APX-complete?</p></li>
</ul>

CC BY-SA 3.0
2014-03-02T10:16:33.703Z
The $NP$-hardness result is folklore since this non convex problem can encode integer linear programming which is $NP$-complete.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-03-03T16:17:19.930Z
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
<cc.complexity-theory><reference-request><machine-learning><svm>
Complexity of the Transductive SVM training problem
Antonio Valerio Miceli-Barone
# Complexity of the Transductive SVM training problem

(Asked by: username_0 on 2014-02-21)

The [Transductive Support Vector Machine training problem](http://en.wikipedia.org/wiki/Support_vector_machine#Transductive_support_vector_machines) 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?

**Tags:** cc.complexity-theory, reference-request, machine-learning, svm

> **Comments:**
> **username_1**: The $NP$-hardness result is folklore since this non convex problem can encode integer linear programming which is $NP$-complete.  
> **username_0**: 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?  

---

## 0 answers

