Support Vector Machines with soft margin: solving the dual form

Question

I am currently struggling with finding an analytical solution for the $\alpha_k$. I have derived the following constrained optimization problem:

$$ L = \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i \alpha_j y_i y_j (\textbf{x}_j^T \textbf{x}) $$ $$ s.t. \quad 0 \leq \alpha_i \leq C \quad \forall i, \quad \sum_{i=1}^{N} \alpha_i y_i = 0 $$

I had, at first, not taken the constraints into account which, after taking the derivative w.r.t. $\alpha_k$, gave me: $$ y_k \sum_{i=1}^{N} \alpha_i y_i (\textbf{x}_j^T \textbf{x}) = 1 $$ This system of linear equations I could easily solve in Python using numpy. But as the alpha values were way too high (as could have been expected), I went back and found that I had forgotten about the constraints.

Now, I don't know how to find an analytical solution to that. I have tried writing down the problem using Lagrange Multipliers but that doesn't seem to get me anywhere. I have also looked around the Internet a lot and couldn't find a single lecture/slides/etc. that actually went on from that point.

Now is my question, is there a way to find an analytical solution to that constrained optimization problem or do I have to just put all of that into a solver? And if there is a solution, I would appreciate some hints on how to get there.

Thank you for your Time!

Answer 1

if you want to find an analytical solution for the problem I think that it doesn't exist.

At this point you should apply decomposition (don't try to work on all your variables, but iteratively considers only a subset of them called working set), if (and only if) you use a working set W, |W|=2, then your subproblem has an analytical solution.

Due to the large number of alpha variables, decomposition is the basis of svm implementations, in particular the svm light algorithm uses a working set W of cardinality 2.