1
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.