Duality for Support Vector Machines

SVM classifier for two linearly separable classes is based on the following convex optimization problem: \begin{equation*} \frac{1}{2}\sum_{k=1}^{n}w_k^2 \rightarrow \min \end{equation*} \begin{equation*} \sum_{k=1}^{n}w_k x_{ik} + b \geq 1,\; \forall x_i \in C_1 \end{equation*} \begin{equation*} \sum_{k=1}^{n}w_k x_{ik} + b \leq -1,\; \forall x_i \in C_2 \end{equation*} where $x_1, x_2, ... , x_l$ are training vectors from $R^n$. For this problem, there is a well known dual problem which is solved to get the optimal $w, b$.

However, my question is about applicability of the strong duality theorem to this problem. The strong duality theorem for a convex optimization problem with objective function $f(w, b)$ and constraints given by inequalities $g_i(w, b) \leq 0, i = 1, ..., p$, states that if $w, b$ is a solution of such problem and a regular point of the constraints, and $\mu_1^* \geq 0, \mu_2^* \geq 0, ..., \mu_p^* \geq 0$ are the corresponding Lagrange multipliers, then the dual problem has solution at $\mu_1^*, \mu_2^* , ..., \mu_p^*$.

Assume $(w, b)$ is the optimal solution of the primary SVM problem stated above. One needs to check whether it is a regular point of the constraints, i.e., whether $\nabla g_i(w, b)$ are linearly independent for all $i$ such that $g_i(w, b) = 0$, i.e., for all $i$ such that $x_i$ are vectors closest to the separating hyperplane (support vectors). The gradient of the constraint $g_i(w, b)$ is $-(x_{i1}, x_{i2}, ..., x_{in}, 1)$ if $x_i \in C_1$, and $(x_{i1}, x_{i2}, ..., x_{in}, 1)$ if $x_i \in C_2$. Generally speaking, there is no guarantee that these vectors will be linearly independent. Thus, there is no guarantee that $(w, b)$ will be a regular point of the constraints listed in the primary problem. So how one can use the strong duality theorem here?

-

migrated from stats.stackexchange.comApr 27 '11 at 11:04

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

Are you familiar with Slater's condition and its variants? I think these notes will help. – cardinal Apr 27 '11 at 11:36
Thank you, @cardinal, it seems to answer the question. – Leo Apr 27 '11 at 15:56