I think that so far I understand the crucial concepts of Support Vector Machines: That we represent our data as points in some n-dimensional space, and in the binary case try to separate them by an optimal maximal margin hyperplane (optimality defined with regards of the bias-variance trade-off, see hard or soft margin SVMs). What I do not know yet is how exactly this hyperplane is found - so what is the algorithm? Given we have two datasets, does an algorithm randomly tries out one plane after the other to determine which plane is the optimal one? What does it mean, that for the calculation of the hyperplane only the support vectors are considered?
Does an algorithm randomly tries out one plane after the other to determine which plane is the optimal one?
No, that would be terribly inefficient. These days (kernel) SVM's are trained using sequential minimal optimization, which is essentially a customized form of quadratic programming.
Quadratic programming is an instance of the general class of convex optimization. One of the biggest advantages of the fact that training an SVM is a convex problem is the fact it has a global optimum that can efficiently be found, in stark contrast to the training problems associated to neural networks.
What does it mean, that for the calculation of the hyperplane only the support vectors are considered?
Via the (generalized) representer theorem, we know that the separating hyperplane is a linear combination of support vectors. Hence, we only need to consider solutions of that form.