linear programming · simplex method · L1-violation classifier

Binary Classifier via the Simplex Method, in 2D

17 points are drawn from two overlapping clouds: label +1 tends toward the upper left and label −1 toward the lower right. The clouds need not be linearly separable. The program minimizes the L₁ norm of the nonnegative violation vector η: minimize Σηᵢ, subject to bᵢ(w₀ + wₓxᵢ + wᵧyᵢ) ≥ 1 − ηᵢ and ηᵢ ≥ 0. The coefficients w₀,wₓ,wᵧ are unrestricted. The displayed boundary follows the basic feasible solution through the primal-simplex pivots.