Support Vector Machines with soft margin: solving the dual form 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!
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.