SVC: why is at least one sample always exactly lying on the support vectors? I don't really understand, why at least one sample is always exactly lying on the support vector(s). When assuming, that the dataset is exactly linearly seprable and considering the cost function of the SVC
$$ c = ||{\boldsymbol{w}}||^2 + C\sum_{i=1}^N \max (0, 1-y_i(x^Tw+b)) $$
I'd also get $c=0$ if the support vectors are translated further into the margin area (see picture). Is this behaviour simply due to the $||{\boldsymbol{w}}||^2$ therm in the cost function?


The SVM aims to construct a maximum margin classifier.  Essentially this means a decision boundary that is as far as possible from the nearest data point on either side.  This is equivalent to finding the discriminant function with the lowest slope for which the values of the discriminant are some arbitrary value (say +1 and -1) for the closes points on either side, i.e.
Minimise $\|\vec{w}\|^2$
subject to $y_i(\vec{w}\cdot\vec{x}_i + b) >= 1$ for all i
Now if the $y_i(\vec{w}\cdot\vec{x}_i + b)$ are greater than 1 for all i, then we can always make the weight vector lie in the same direction but with a smaller magnitude, so it will be possible to minimise the objective a bit more without violating the constraints.  The reason we end up with at least one point on each side that lies exactly on the margin is that this is the first point where the contraints would be violated if we reduced the objective any further.
I don't think this is going to be true for the soft-margin SVM.  If you consider a linearly separable problem, and start with the hard margin solution (which is a soft-margin with infinite slack penalties), and decrease the slack penalty, then you will immediately be able to reduce the objective function (if only very slightly) by introducing some small amount of slack in the constraints.  This would mean the margins no longer lie over the data points that the used to, but will be infinitessimably beyond them.
