0
$\begingroup$

I am trying to understand how to solve the SVM optimization problem.

It is usally written : $$\text{Minimize} $$ $$\|\textbf{w}\|$$ $$\text{Subject to}$$ $$y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \geq 1$$ $$\text{(for any i=1,…,n)}$$ (Wikipedia)

To simplify the problem we can minimize the square of the norm instead of the norm.

If we have two points $x_1 = (1,2)$ and $x_2 = (4,6)$ for which $y_1=1$ and $y_2=-1$

Our problem is now:

$$\text{Minimize} $$ $$\|\textbf{w}\|^2$$ $$\text{Subject to}$$ $$y_1(\mathbf{w}\cdot\mathbf{x_1} - b) \geq 1$$ $$y_2(\mathbf{w}\cdot\mathbf{x_2} - b) \geq 1$$

Given vector $\textbf{w}(a, 1)$ the square of its norm is: $$\|\textbf{w}\|^2= (\sqrt{a^2+1^2})^2$$

We now replace each vectors by its values and the problem is:

$$\text{Minimize} $$ $$ a^2+1$$ $$\text{Subject to}$$ $$ a+2- b \geq 1$$ $$ -4a - 6 + b \geq 1$$

How can I solve such a problem? I know that we can use the Lagrange Multipliers as shown in this video when the constraints are equality constraints but I didn't find a simple explanation to handle inequality constraints like this.

Most description of the SVM transform the primal problem into a dual problem before resolving it but I would like to solve it without doing this. Is it possible ?

Is there a way to solve it geometrically too?

$\endgroup$
2
  • $\begingroup$ The KKT (Karush–Kuhn–Tucker) conditions are how you handle convex problems with inequality constraints. See Boyd and Vandenberghe's Convex Optimization (Section 5.5.3) for details. Also note that when you allow for classes to overlap for an SVM, you have to be careful in how you define the margin since the "natural" way is non-convex (see Elements of statistical learning by Hastie, Friedman and Tibshirani, Sec. 12.2 for more details). The geometric solution where the classes are separate is just maximizing the margin. When the classes overlap, I don't think theres a nice pure geometric answer. $\endgroup$
    – Batman
    Dec 24, 2015 at 13:47
  • $\begingroup$ In general, a book (like Boyd/Vandenberghe or Hastie/Friedman/Tibshirani) is better than a video. It might take a little longer, of course. $\endgroup$
    – Hans Engler
    Dec 24, 2015 at 14:16

1 Answer 1

Reset to default
0
$\begingroup$

For inequality constraints, you need to modify the Lagrangian in such a way that it now includes the inequality constraints in addition to any equality constraints. This modification is done by the use of slack variables. Detailed explanation with an example is shared in this video inequality constrained optimization. The slack variable basically converts an inequality constraint into an equality constraint, the problem is then solved as done for an equality constrained problem by the use of Lagrange multipliers. If the slack variable equals 0 then it implies that the inequality constraint is in fact to be satisfied as an equality constraint to solve the given problem.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .