Q$1(60$ pts$)$: In class, we saw that if our data is not linearly separable, then we need to

modify our support vector machine algorithm by introducing an error margin that must be

minimized. Specifically, the formulation we have looked at is known as the l$\_(1)$ norm soft

margin SVM$.$

In this problem we will consider an alternative method, known as the l$\_(2)$ norm soft margin

SVM$.$ This new algorithm is given by the following optimization problem $($notice that the

slack penalties are now squared$)$:

min$\_($w$,$b$,\backslash$xi $),(1)/(2)||$w$||^(2)+($C$)/(2)\backslash$sum$\_($i$=1)^$m $\backslash$xi $\_($i$)^(2)$

subject to

y$^(($i$))($w$^($T$)$x$^(($i$))+$b$)>=1-\backslash$xi $\_($i$),$i$=1,$dots,m$.$

Questions:

$($a$)$ Notice that we have dropped the $\backslash$xi $\_($i$)>=0$ constraint in the l$\_(2)$ problem. Show that these

non$-$negativity constraints can be removed. That is$,$ show that the optimal value of

the objective will be the same whether or not these constraints are present. $[10$ points$]$

$($b$)$ What is the Lagrangian of the l$\_(2)$ soft margin SVM optimization problem? $[10$ points$]$

$($c$)$ Minimize the Lagrangian with respect to w$,$b$,$ and $\backslash$xi by taking the following gradients:

grad$\_($w$)$L$,($delL$)/($delb$),$ and grad$\_(\backslash$xi $)$L$,$ and then setting them equal to $0.$ Here, $\backslash$xi $=[\backslash$xi $\_(1),\backslash$xi $\_(2),$dots,$\backslash$xi $\_($m$)]^($T$).$

pointsl$\_(2)$ soft margin SVM optimization problem? $[25$ points$]$