# How to solve this convex optimization problem with inequalities constraint?

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?

• 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. – Batman Dec 24 '15 at 13:47
• In general, a book (like Boyd/Vandenberghe or Hastie/Friedman/Tibshirani) is better than a video. It might take a little longer, of course. – Hans Engler Dec 24 '15 at 14:16