In Convex optimization, We are given a convex function f$($x$)$ with convex constraints h$\_$i$($x$)$ and g$\_$j$($x$).$ Normally in convex functions we saw that in order to find the minimum value we need to take derivative wrt the variables and set it to $0.$ have constraints we simply do that. min f$($x$)$ s$.$t: h$\_$i$($x$)=0$ ; i$=1,...,$ p g$\_$j$($x$)<=0$ ; j$=1,...,$ m So in order to solve for you need to follow the following steps: $-$ Step $1$: apply Lagrangian function as primal objective function $+$ dual multipliers $*$ its primal constraints:

$[$ L$($x$,\backslash$beta $,\backslash$alpha $)=$f$($X$)+\_$i$^$p$\backslash$alpha $\_$i h$\_$i$($x$)+\_$j$^$m$\backslash$beta $\_$j g$\_$j$($x$)$; s$.$t : $\backslash$alpha $\_$i in ; $\backslash$beta $\_$j$>=0]$

Important note: if for all values of i and j h$\_$i$($x$)=0$ and g$\_$j$($x$)<=0$ then by maximizing the L$($x$,\backslash$beta $,\backslash$alpha $)$ we are minimizing the f$($x$)$ In the case of SVM the variables are L$($w$,$ b$,\backslash$alpha $)-$ Step $2$: Solve for the variables using MLE. In class we mentioned to avoid the dimensional problem we will solve for w$,$ b first. after solving and finding the optimal values as:

w$^*=\_$i$=1^$N$\backslash$alpha $\_$i y$\_$i x$\_$i

and solving for b we found that $\_$i$=1^$n$\backslash$alpha $\_$i y$\_$i$=0($this is a finding that means is a dual constraint$)-$ Step $3$: Replace the derived variables into the original Lagrangian function

L$(\backslash$alpha $,$ w$^*,$ b$^*)=-1/2\_$i$\_$j y$\_$i y$\_$j$($x$\_$i$^$T x$\_$j$)\backslash$alpha $\_$i$\backslash$alpha $\_$j$+\_$i$\backslash$alpha $\_$i

We call this dual function. $-$ Step $4$: Write your dual function and its associated constraints:

$[$ max $\_\backslash$alpha $-1/2\_$i$\_$j y$\_$i y$\_$j$($x$\_$i$^$T x$\_$j$)\backslash$alpha $\_$i$\backslash$alpha $\_$j$+\_$i$\backslash$alpha $\_$i; s$.$t: $\_$i$=1^$n$\backslash$alpha $\_$i y$\_$i$=0\_$i$=1,...,$ N; $\backslash$alpha $\_$i$>=0\_$i$=1,...,$ N $]$

$-$ Step $5$: Solve for the dual variables $\backslash$alpha $\_$i using some methods like SMO. $-$ Step $6$: Check for KKT conditions specially complementary slackness: Complementary slackness $=$ Dual variables $*$ Primal constraints $=0$ depending on how many dual variables you have you will get multiple condition: for example if you have only $\backslash$alpha $\_$i then: In case of above example : $\backslash$alpha $\_$i$(1-$y$\_$i$($w$^$T x$\_$i$+$b$))=0$ So now you want to verify that for each constraints this equation always holds: A$.$ Case that $\backslash$alpha $\_$i$>0$ then it means y$\_$i$($w$^$T x$\_$i$+$b$)=1$ which means the points are on the margin B$.$ Case that $1-$y$\_$i$($w$^$T x$\_$i$+$b$)>0$ then it means that $\backslash$alpha $\_$i$=0$ which means y$\_$i$($w$^$T x$\_$i$+$b$)>1($points after the marg For your homework you need to write the above steps for Soft margin SVM$.$