2
$\begingroup$

The linear L2 SVM can be intuitively understood as

\begin{equation} \text{minimize } f(\boldsymbol{w}) = \frac{1}{2} \Vert\boldsymbol{w}\Vert^2_2 + C \sum_{i=1}^m \xi_i^2 \tag{1} \end{equation} where $\xi_i = \text{max}(0, 1 - y_i\boldsymbol{w}^T\boldsymbol{x}_i)$.

However, in papers, I often find it presented instead as (1) s.t. $\xi_i \geq 1 - y_i\boldsymbol{w}^T\boldsymbol{x}_i$.

What are the mathematical conditions that allow the equality constraint $\xi_i = \text{max}(0, 1 - y_i\boldsymbol{w}^T\boldsymbol{x}_i)$ to be recast as the inequality constraint $\xi_i \geq 1 - y_i\boldsymbol{w}^T\boldsymbol{x}_i$?

$\endgroup$
1
$\begingroup$

The two problems are equivalent.

[To be clear, the optimization problem with the inequality constraint is an optimization with respect to $w$ as well as $\xi_1, \ldots, \xi_m$.]

Consider the version with the inequality constraint. Suppose $w$ is fixed, and we want to find the best $\xi_i$; this is simply minimizing $\xi_i^2$ under the constraint $\xi_i \ge 1 - y_i w^\top x_i$. Do you see that the best $\xi_i$ is $\xi_i = \max(0, 1- y_i w^\top x_i)$?

$\endgroup$
  • 1
    $\begingroup$ Thanks. As a follow-up, is this simply a nice trick? Or are there general rules when an equality constraint can be written equivalently as an inequality? $\endgroup$ – Tim Mak May 14 '18 at 6:05
  • $\begingroup$ @TimMak I don't think anything special is going on here beyond the fact that the solution of optimizing $\xi_i$ with the inequality constraint is precisely the equality constraint. $\endgroup$ – angryavian May 14 '18 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.