In soft-margin SVM, is it guaranteed that some points will lie on the margin?

Question

In soft-margin SVM, once we solve the dual-form optimization problem (using quadratic programming, which is guaranteed to converge on a global optimum because the problem is convex), we get a vector $\alpha$ of coefficients that we can use to recover the hyperplane parameters $\beta$ and $\beta_0$. The additional constraint in soft-margin (compared to hard-margin) is $0 \leq \alpha_i \leq C$ for some positive constant $C$. We say that:

1. If $\alpha_i = 0$, then the corresponding $x_i$ is outside the margin
2. If $\alpha_i = C$, then the corresponding $x_i$ is on the wrong side of the margin
3. If $0 \lt \alpha_i \lt C$, then the corresponding $x_i$ is on the margin

We recover $\beta$ through the KKT condition $\beta = \sum_{i}{\alpha_i y_i x_i}$, but we recover $\beta_0$ by selecting any $x_i$ whose corresponding $\alpha_i$ satisfies the third condition above and solving $y_i(\beta^T x_i + \beta_0)=1$ (we should get the same value for $\beta_0$ using any such point satisfying the third condition above).

Here's my question: given an optimal $\alpha$, is it possible for the third condition to not be satisfied for any $\alpha_i$? For example, I actually have a dataset that's linearly separable for which I'm trying to train a soft-margin SVM with $C=0.5$, but I'm finding that every value in $\alpha$ is either $0$ or $0.5$ and that there are no values in between, hence I cannot recover $\beta_0$. Am I doing something wrong if my $\alpha$ doesn't satisfy the third condition above for any $i$? My intuition tells me that there should always be at least two points on the margin because the primal optimization problem maximizes the size of the margin; but the $\alpha$ for my dataset is contradicting my intuition.

---

If it helps, I'm doing this in MATLAB with the following (pseudo)code:

X = 2 by n matrix of linearly separable data points
y = n by 1 matrix of class labels (-1 or +1)
X_hat = X with each column signed to its label
H = X_hat' * X_hat;
f = -1 * ones(n, 1);
Aeq = y';
beq = 0;
lb = zeros(n, 1);
ub = 0.5 * ones(n, 1);
alpha = quadprog(H, f, [], [], Aeq, beq, lb, ub); % alpha is always 0 or 0.5

Answer 1

No, it's not guaranteed, but if the solution has no alpha in that open interval, then we have a "degenerate" SVM training problem, for which the optimal w=0, and we always predict the majority class. This is shown in Rifkin et al.’s “A Note on Support Vector Machine Degeneracy”, an MIT AI Lab Technical Report. Does your problem have these characteristics? It seems unlikely this would happen with naturally occurring data.

Answer 2

In extremely rare case when there is no free support vectors, b would be a range of values constrained by the related KKT conditions. You can calculate that range and then pick any b in that range.

But I suggest you change the value of $C$ first and see if there is still no free SV.

Answer 3

If we have a case where the solution is non-unique, then it is in fact guaranteed that there is some solution with no support vectors on the margin!

See the corollary of Theorem 2 on page 4 in this paper: https://pdfs.semanticscholar.org/c8b8/16b48dcd4ea5b37c6bb9a238b44622eeacce.pdf