# Odd Behavior in Cutoff of Soft Margin SVM

In soft margin svm, we solve the following quadratic programming problem. $$\text{maximize}\ \sum_{i=1}^N \alpha_i-\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jX_i^tX_j,\\ \text{subject to}\ \sum_{i=1}^N \alpha_i Y_i=0,\\ 0\le \alpha_i\le C, 1\le i\le N.$$ $X_i$ is a vector predictor and $Y_i$ is a binary 1, -1 response. You can use the quadprog library in R to solve this. Once you have the solution, each predictor $X_i$ is projected on the real line by, $$\sum_{j=1}^N \alpha_jY_j X_i^tX_j.$$ You want to find a suitable cutoff $b$, to assign a label, $$\text{sign}\left[\sum_{j=1}^N \alpha_jY_j X_i^tX_j+b\right].$$ Using this, we can assign a label to new predictor $\tilde{X}$ by, $$\text{sign}\left[\sum_{j=1}^N \alpha_jY_j \tilde{X}^tX_j+b\right].$$ You can obtain the cutoff by the fact that for $i$ such that $0\le\alpha_i\le C$, we have the equality, $$Y_i\left(\sum_{j=1}^N \alpha_jY_j X_i^tX_j+b\right)=1.$$

But the iact value of solve.QP of quadprog returns that for all $i$, at least one of the inequalities $0\le \alpha_i$ and $\alpha_i\le C$ is an equality. This means there are no support vectors, which can't be. When I take a look at the $\alpha$'s, at least three of them is considerably far from 0 and C. But I get one cutoff value from two of these $\alpha$'s and another different cutoff value by using another $\alpha$. Even though they should be returning the same value. Help on why such odd things are happening would be much appreciated. The projection seems to be correct. And if the projections are correct, obtaining the cutoff is just one line from there.

Above is the simulated data. Below is the projection and the cutoffs.

The code that produced this is below.

library(quadprog)
set.seed(051517)

X=matrix(rnorm(200),100,2)
plot(X[,1],X[,2],pch='+')
vrbinom=Vectorize(rbinom)
Y=vrbinom(n=1,size=1,prob=exp(4*rowSums(X))/(exp(4*rowSums(X))+1))
Y=2*Y-1
Xp=X[Y==1,]
Xm=X[Y==-1,]
plot(Xp[,1],Xp[,2],pch='+',xlim=range(X[,1])+c(-0.1,0.1),
ylim=range(X[,2])+c(-0.1,0.1))
points(Xm[,1],Xm[,2],pch='-')
epsilon=1e-6
M=(X%*%t(X))
MAT=(Y%o%Y)*(X%*%t(X))+epsilon*diag(100)

lambda=100
A=rbind(Y,diag(100))
A=rbind(A,-diag(100))
A=t(A)
b=rep(0,101)
b=c(b,rep(-lambda,100))
sc=norm(2*MAT,"2")
sol=solve.QP(Dmat=2*MAT/sc,dvec=rep(1,100)/sc,Amat=A,bvec=b,meq=1)