My question relates to an alternative optimality criterion for an SVM dual solution derived in Bottou, Lin (2006) in pages 8 and 9.
Let:
- $\alpha^* = (\alpha_1^*,\dots,\alpha_n^*)$ be a dual solution to the SVM. Recall that any solution $\alpha^*$ must satisfy: $\forall i \in \{1,...,n\}, 0 \leq \alpha_i^* \leq C$;
- $g_i^*$ the derivative of the dual objective function $\mathcal{D}$ with respect to $\alpha_i^*$;
- $B_i$ equal to $C \times 1_{\{y_i=1\}}$ and $A_i$ equal to $-C \times 1_{\{y_i=-1\}}$ such that $\forall i \in \{1,...,n\},\; y_i\alpha_i \in [A_i,B_i]$ $-$ i.e. $[A_i,B_i]$ might be equal to $[0,C]$ or $[-C,0]$;
- $I_{up} = \{i:y_i\alpha_i < B_i\}$ $-$ i.e. $\alpha_i < C$ or $\alpha_i < 0$;
- $I_{down} = \{j:y_j\alpha_j > A_j\}$ $-$ i.e. $\alpha_j > 0$ or $\alpha_j > -C$.
Then Bottou and Lin's necessary and sufficient optimality criterion $-$ let call it $\mathcal{O}_{SVM}(\alpha^*)$ $-$ is:
$$ \exists \: \rho \in \mathbb{R} : \max_{i \, \in \, I_{up}} y_ig_i^* \leq \rho \leq \min_{j \, \in \, I_{down}} y_jg_j^* $$
I understand how $\alpha^*$ being a solution implies $\mathcal{O}_{SVM}(\alpha^*)$ $-$ it is shown in the paper $-$ however I am not sure how $\mathcal{O}_{SVM}(\alpha^*)$ implies $\alpha^*$ is a solution.
Does anybody know a reference where the reciprocal is proved? If not, could someone shed more light on this? As noted, details can be found in the above link in pages 8 and 9; the criterion corresponds to equation $(1.11)$.
[Addendum - edited]
My issue relates primarily to $\varepsilon$ $-$ see paper: the inequality $\mathcal{D}(\alpha^{\varepsilon}) \leq \mathcal{D}(\alpha^*)$ should hold for all $\alpha^{\varepsilon}$ for $\alpha^*$ to be an optimum, however $\varepsilon$ should be sufficiently small for $\alpha^{\varepsilon}$ to satisfy its constraints, hence the inequality does not hold for all $\alpha^{\varepsilon}$, does it? Except if we are implicitly restricting ourselves to the feasible region by considering only the following set of epsilons: $S_{\varepsilon} = \{\varepsilon:\forall i \in \{1,\dots,n\}, \alpha^{\varepsilon} = (\alpha_1^{\varepsilon},\dots,\alpha_n^{\varepsilon}), 0\leq\alpha_i^{\varepsilon}\leq C\}$ ?