Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

migrated from stats.stackexchange.com Apr 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.

1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.