1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Are you familiar with Slater's condition and its variants? I think these notes will help. $\endgroup$ – cardinal Apr 27 '11 at 11:36
  • $\begingroup$ Thank you, @cardinal, it seems to answer the question. $\endgroup$ – Leo Apr 27 '11 at 15:56
  • $\begingroup$ @cardinal The link is broken. $\endgroup$ – littleO Jul 9 '17 at 11:09

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.