Struggling to understand threshold(b) update step in SMO 
Currently reading Platt's paper, Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines , I got stuck in section 2.3 Computing the Threshold:

SVM notation

objective function:
\begin{array}{1}
 \max _{\alpha }\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}y_{j}K_{ij}\alpha _{i}\alpha _{j}\\
 0\leqslant \alpha_i \leqslant C : Lagrange multipliers\\
\sum_{i=1}^Nyi\alpha_i=0\\
\end{array}
KKT condition:
\begin{array}{l}
\quad {a_i} = 0 \quad \Leftrightarrow \quad {y_i}u_i \ge 1\\
0 < {a_i} < C \quad \Leftrightarrow \quad {y_i}u_i = 1\\
\quad {a_i} = C \quad \Leftrightarrow \quad {y_i}u_i \le 1
\end{array}
$b$: threshold in SVM model $w^Tx-b$
$u_i=\sum_{j=1}^Ny_j\alpha_jK_{ij}-b$: predict value using SVM
$E_i=u_i-y_i$: difference between target and prediction
$K_{ij}=K(x_i, x_j)=K(x_j,x_i)$: the kernel matrix

Brief description about SMO

According to Platt, SMO optimize two Lagrange multipliers one time, for example:
$y_1\alpha_1+y_2\alpha_2=-\sum_{i=3}^Ny_i\alpha_i=Const$

...
Update $\alpha_i$ 
...
The question


*

*if $\alpha_i$ is not at bound, threshold $b$ can be computed by forcing the output to be $y_i$: 
$b_i=E_i+y_i(\alpha^{new}_1-\alpha_1)K_{11}+y_2(\alpha_2^{new,clipped}-\alpha_2)K_{12}+b^{old}$   (eq.1) 

*if both $\alpha_1$ and $\alpha_2$ are at bound, then using eq.1 computing $b_1$ and $b_2$, all thresholds between $b_1$ and $b_2$ are consistent with KKT conditions.

I understand case 1 since $0<\alpha_i<C$,we get $y_iu_i=1$, prediction error must be 0, but I failed to understand case 2... 
 A: I don't think the answer is obvious.  Without figuring out their notation and possibly getting my pencil out, I can't get you all the way to an answer. But I think the following will get you pretty close:
In general in SVMs, if you can find at least one $\alpha_i$ "not at bound", then you can find $b$ in a straightforward way (which amounts to your Eqn 1 in this context).  Otherwise, according to the paper "A Note On Support Vector Machine Degeneracy" by Rifkin et al., the problem is degenerate, which means it has a solution for which $w=0$. Moreover, according to their Lemma 6, the solution has $b=1$ if there are more training examples in the positive class, $b=-1$ if there are more training examples in the negative class, and $b \in [-1,1]$ if there are equally many examples in each class. 
This must reduce to their claim in Eqn 2 for their special case.
A: I figured it out finally:

when both $\alpha_1$ and $\alpha_2$ are at bound, then using eq.1 computing $b_1$ and $b_2$, all thresholds between $b_1$ and $b_2$ are consistent with KKT conditions.

let $b^{new}=tb_1+(1-t)b_2,0\leqslant t\leqslant1$, i.e.,$b^{new}$ is between $b_1$and $b_2$, we have:
$$
\begin{split}
b^{new}&=tb_1+(1-t)b_2\\
&=t(E_1+y_1(\alpha_1^{new}-\alpha_1)K_{11}+y_2(\alpha_2^{new}-\alpha_2)K_{12}+b)+(1-t)(E_2+y_2(\alpha_2^{new}-\alpha_2)K_{22}+y_1(\alpha_1^{new}-\alpha_1)K_{12}+b)\\
\end{split}
$$
since both $\alpha_1$ and $\alpha_2$ are at bound, $\alpha_2$ probably have been clipped(see figure in the question), so we introduce $0\leqslant \lambda\leqslant1$ to update $\alpha_2$:
$$
\alpha_2^{new}=\alpha_2+\lambda\frac{y_2(E_1-E_2)}{\eta}\quad(see \ eq.16\ in\ SMO\ paper )
$$

$$\begin{split}
E_1^{new}&=E_1+y_2(\alpha_2^{new}-\alpha_2)K_{12}+(\alpha_1^{new}-\alpha_1)y_1K_{11}-\Delta b\\
E_2^{new}&=E_2+y_2(\alpha_2^{new}-\alpha_2)K_{22}+(\alpha_1^{new}-\alpha_1)y_1K_{12}-\Delta b\\
\Delta b&=b^{new}-b\\
&=E_2+y_1(\alpha_1^{new}-\alpha_1)K_{12}+y_2(\alpha_2^{new}-\alpha_2)K_{22}+t[E_1-E_2+y_1(\alpha_1^{new}-\alpha_1)(K_{11}-K_{12})+y_2(\alpha_2^{new}-\alpha_2)(K_{12}-K_{22})]\\
\end{split}$$
substitute $\Delta b$ into $E_1^{new}$ and $E_2^{new}$, we have:
$$\begin{split}
E_1^{new}&=(1-t)(1-\lambda)(E_1-E_2)\\
E_2^{new}&=-t(1-\lambda)(E_1-E_2)\\
\end{split}
$$

take $\alpha_1=\alpha_2=C$ for example:
$$\begin{split}
\alpha_2^{new}-\alpha_2&=\lambda\frac{y_2(E_1-E_2)}{\eta} \geqslant 0\\
&\Leftrightarrow y_2(E_1-E_2) \geqslant 0\\
&\Leftrightarrow -t(1-\lambda)y_2(E_1-E_2)\leqslant 0\\
&i.e., y_2E_2^{new}\leqslant 0
\end{split}$$
for $\alpha_1$:
$$\begin{split}
\alpha_1^{new}-\alpha_1&=s(\alpha_2-\alpha_2^{new})\geqslant 0\\
&\Leftrightarrow-s\lambda\frac{y_2(E_1-E_2)}{\eta}\geqslant 0\\
&\Leftrightarrow-\lambda\frac{y_1(E_1-E_2)}{\eta}\geqslant 0\\
&\Leftrightarrow y_1(E_1-E_2)\leqslant 0\\
&\Leftrightarrow (1-t)(1-\lambda)y_1(E_1-E_2)\leqslant 0\\
&i.e., y_1E_1^{new}\leqslant 0
\end{split}$$
KKT condition holds!
