Constrained versus unconstrained formulation of SVM optimisation

Question

Let us take two formulations of the $\ell_{2}$ SVM optimization problem, one constrained:

$\min_{\alpha,b} ||w||_2^2 + C \sum_{i=1}^n {\xi_{i}^2}$

s.t $ y_i(w^T x_i +b) \geq 1 - \xi_i$
and $\xi_i \geq 0 \forall i$

and one unconstrained:

$\min_{\alpha,b} ||w||_2^2 + C \sum_{i=1}^n \max(0,1 - y_i (w^T x_i + b))^2$

What is the difference between those two formulations of the optimization problem? Is one better than the other?

Hope I didn't make any mistake in the equations. Thanks.

Update : I took the unconstrained formulation from Olivier Chapelle's work. It seems that people use the unconstrained optimization problem when they want to work on the primal and the other way around when they want to work on the dual, I was wondering why?

Answer 1

It seems to me that at the solution of the first problem, the inequality constraint becomes an equality, i.e. $1 - \xi_i = y_i(w^Tx_i + b)$, because we are minimising the $\xi_i$s and the smallest value that satisfies the constraint occurs at equality. So as $\xi_i \geq 0$, $\xi_i = max(0, 1 - y_i(w^Tx_i+b))$, which substituting gives something rather similar to your second formulation.

Having checked the paper by Chapelle, it looks like the second formulation is missing a "1 -" in the second half of the max operation (see definition of L(.,.) following equation 2.8). In that case both formulations are identical, they are both equivalent representations of the primal optimisation problem (the dual formulation is in terms of the Lagrange multipliers $\alpha_i$). The advantages and disadvantages are therefore purely computational.

Answer 2

Please see the first page of https://davidrosenberg.github.io/mlcourse/Notes/svm-lecture-prep.pdf for a more formal answer. aka, the 2 problems are "equivalent" in the sense that the minimizer and the minimum of the first problem is the minimizer of the second, and vice versa.

Replacing $g(x)$ in the doc with $1-y_i(w^T x_i +b) $ will answer your question.

To prove it in both directions:

The second problem in the doc -> the first problem in the doc

Suppose we have $(x^\star, \xi^\star)$ as the minimizer of the second problem in the doc. Then $\xi^\star=g(x^\star)$ (because otherwise the objective function can get a smaller value by setting $\xi$ smaller). Due to being a minimizer, we have "$\forall x, \forall \xi, f(x)+\xi \ge f(x^\star)+g(x^\star)$". By setting $\xi=g(x)$ as a special case, we have "$\forall x, f(x)+g(x) \ge f(x^\star)+g(x^\star)$", which shows it's also the minimum of the first problem. QED.

The first problem -> the second problem

Suppose we have $x^\star$ as the minimizer of the first problem in the doc.

Therefore $x^\star$ minimizes "$f(x)+\xi, s.t. \xi=g(x)$".

Therefore $x^\star$ minimizes "$f(x)+\xi, s.t. \xi \ge g(x)$" (because when this problem attains minimum, $\xi$ must be equal to $g(x)$; which means it degrades to the above problem). This problem is exactly the second problem in the doc. QED.