Soft-margin SVM duality and KKT conditions

Let $(w_{\ast },b_{\ast },{\xi }_{\ast })$ be any primal minimizer, which exists by [F1], and let $M=\mathrm{span}\{\varphi (x_i):1\le i\le n\}$. Project $w_{\ast }$ onto $M$ using [F2]; its residual is orthogonal to every $\varphi (x_i)$, so the projection preserves all margins and slacks. If the residual were nonzero, [F3] would give a strictly smaller squared norm and hence a strictly smaller objective, contradicting minimality because the regularization coefficient is $1\mathrm{/}2>0$. Thus every primal minimizer has $w_{\ast }\in M$.

Identify $M$ with a Euclidean space using an orthonormal basis. In the finite-dimensional variable space $M\times \mathbb{R}\times {\mathbb{R}}^n$, the objective is a proper continuous convex function and the $2n$ inequality constraints are continuous affine functions with the sign convention [F7]. No inequality is removed by the domain-preserving convention in [F5]: all functions have full domain, and sending the corresponding ${\xi }_i\to -\mathrm{\infty }$ makes either constraint function positive. There are no primal equality rows, so the full-row-rank condition in [F5] holds vacuously.

The point $w=0$, $b=0$, ${\xi }_i=2$ has strict slack in every constraint: $1-{\xi }_i-y_i(⟨w,\varphi (x_i)⟩+b)=-1<0$ and $-{\xi }_i=-2<0$. The objective and all constraint domains are the whole finite-dimensional variable space, so this point lies in their relative interiors. Together with the finite attained primal value from [F1], this verifies every hypothesis of [F6].

Write the margin constraints as $g_i^{(m)}:=1-{\xi }_i-y_i(⟨w,\varphi (x_i)⟩+b)\le 0$ and the nonnegative-slack constraints as $g_i^{(s)}:=-{\xi }_i\le 0$. Give them multipliers ${\alpha }_i\ge 0$ and ${\mu }_i\ge 0$, respectively. The Lagrangian is $L=\frac{1}{2}\mathrm{\parallel }w{\mathrm{\parallel }}^2+C{\sum }_i{\xi }_i+{\sum }_i{\alpha }_i{g}_i^{(m)}+{\sum }_i{\mu }_i{g}_i^{(s)}$.

Put $v:={\sum }_i{\alpha }_i{y}_i\varphi (x_i)$. The terms of $L$ depending on $w$ are $\frac{1}{2}\mathrm{\parallel }w{\mathrm{\parallel }}^2-⟨w,v⟩=\frac{1}{2}\mathrm{\parallel }w-v{\mathrm{\parallel }}^2-\frac{1}{2}\mathrm{\parallel }v{\mathrm{\parallel }}^2$, so their infimum is $-\frac{1}{2}\mathrm{\parallel }v{\mathrm{\parallel }}^2$. The infimum over the unrestricted bias $b$ is finite exactly when ${\sum }_i{\alpha }_i{y}_i=0$, and the infimum over each unrestricted ${\xi }_i$ is finite exactly when $C-{\alpha }_i-{\mu }_i=0$. Thus the dual-feasible conditions are ${\sum }_i{\alpha }_i{y}_i=0$ and $0\le {\alpha }_i\le C$.

Apply [F6] using the verified hypotheses in [step 3.1]. It gives an attained dual optimum $(\alpha ,\mu )$ with the same value as the primal optimum and complementarity for both families $g_i^{(m)}$ and $g_i^{(s)}$. At any fixed primal minimizer, these equal values and complementarity make $L$ attain its unconstrained infimum; its derivatives in $w$, $b$, and each ${\xi }_i$ therefore vanish.

For any finite list $u_1,\dots ,u_m\in X$ and $c_1,\dots ,c_m\in \mathbb{R}$, symmetry and bilinearity of the real inner product give ${\sum }_{r,s}{c}_r{c}_{s}k(u_r,u_s)=⟨{\sum }_r{c}_r\varphi (u_r),{\sum }_s{c}_s\varphi (u_s)⟩=\mathrm{\parallel }{\sum }_r{c}_r\varphi (u_r){\mathrm{\parallel }}^2\ge 0$. Thus the feature-induced kernel $k$ is real positive semidefinite, so its sample Gram matrix satisfies the hypothesis of [F4]. Since $k(x_i,x_j)=⟨\varphi (x_i),\varphi (x_j)⟩$, $\mathrm{\parallel }v{\mathrm{\parallel }}^2={\sum }_{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_{j}k(x_i,x_j)$. By [F4], the matrix $(y_i{y}_{j}k(x_i,x_j){)}_{i,j}$ is the Gram matrix of $y_i{z}_i$, so its quadratic form is nonnegative. Hence the displayed dual objective is concave. Its equality row has coefficient vector $y\mathrm{\ne }0$, because $n\ge 1$ and each $y_i\in \{-1,+1\}$, so that row is independent.

Differentiating the Lagrangian of [step 3.2] gives $w={\sum }_i{\alpha }_i{y}_i\varphi (x_i)$, ${\sum }_i{\alpha }_i{y}_i=0$, and $C-{\alpha }_i-{\mu }_i=0$. The last equation and ${\mu }_i\ge 0$ give ${\alpha }_i\le C$; together with ${\alpha }_i\ge 0$ these are the dual box constraints. The complementarity equations supplied by [F6] are ${\alpha }_i{g}_i^{(m)}=0$ and ${\mu }_i{g}_i^{(s)}=0$, which are exactly the two equations in the Statement.

The finite-dimensional primal has differentiable convex objective and affine convex constraints on the open convex variable space identified in [step 2.1]. Thus [F8] certifies that any feasible tuple satisfying the stationarity and complementarity equations is a global primal minimizer. If $0<{\alpha }_i<C$, then ${\mu }_i=C-{\alpha }_i>0$, so ${\mu }_i{\xi }_i=0$ forces ${\xi }_i=0$; then ${\alpha }_i{g}_i^{(m)}=0$ forces the signed margin to equal $1$. Finally, for any input $x$, stationarity gives the score $s(x)={\sum }_i{\alpha }_i{y}_{i}k(x_i,x)+b$.