1
$\begingroup$

I have a question about the derivation of the SVM algorithm (for example, page 3 here ). The question is about the math, so that's why I'm asking this here.

Suppose I have the following optimization problem:

$$min_{w, \xi} \frac{1}{2} ||w||^2 +C \sum_i\xi_i,\\ s.t. \ y_i w x_i \geq 1 - \xi_i, \ i = 1, ... m, \\ \xi_i \geq 0 $$

In order to solve the problem, we use the Lagrangian:

$$ L(w, \xi, \alpha, \beta) = \frac{1}{2} ||w||^2 +C \sum_i\xi_i + \sum_i \alpha_i(1-\xi_i - y_i w x_i ) + \sum_i \beta_i (-\xi_i)$$

My question is: in this algorithm, the parameter $C$ is assumed to be non-negative. Why isn't this added to the constraints of the Lagrangian?

Thanks.

$\endgroup$
  • 2
    $\begingroup$ Because $C$ is a parameter, not part of the domain over which you are minimizing. $\endgroup$ – Derek Elkins Feb 9 '16 at 14:38
  • $\begingroup$ Oh, right, thanks... but then, suppose I was deriving a similar algorithm (adding a few constraints), and one of the derivatives of the Lagrangian came up with C being equal to a negative number. Does that mean that I have a mistake? Or should I simply ignore it? Thanks @DerekElkins $\endgroup$ – Cheshie Feb 9 '16 at 14:44
  • 2
    $\begingroup$ If you simply add further constraints to this optimization problem and it requires $C$ to be negative, then you've made an unsatisfiable problem. Instead of the parameter $C$ you could instantiate it to 2. If you require 2 to be -4, you're not going to have a solution. $\endgroup$ – Derek Elkins Feb 9 '16 at 14:51
  • $\begingroup$ OK, thanks so much... $\endgroup$ – Cheshie Feb 9 '16 at 15: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.