Maximum-Margin Classification from First Principles: SVMs as Convex Optimization

Why the widest street wins: geometry, quadratic programming, support vectors, and the soft-margin trade-off — every number below is solved, not asserted.

Machine Learning
Optimization
Mathematics
Author

Ravi Kalia

Published

July 23, 2026

Maximum-Margin Classification from First Principles

A support vector machine (SVM) selects a separating hyperplane by solving a convex optimization problem that maximizes geometric margin. Soft-margin SVMs add slack penalties for non-separable data.

All numeric results below come from CVXPY solves on two synthetic 2D datasets. Assertions in the notebook block render if solver output disagrees with hand-derived values. scikit-learn cross-checks appear at the end.

Setup: imports, house palette, plotting helpers, and the toy dataset 
import numpy as np
import cvxpy as cp
import matplotlib.pyplot as plt
from matplotlib.lines import Line2D
from IPython.display import Markdown

# palette (house style)
BLUE, ORANGE, INK = "#2a78d6", "#eb6834", "#0b0b0b"
MUTED, GRID, SURFACE = "#898781", "#e1e0d9", "#fcfcfb"

plt.rcParams.update({
    "figure.facecolor": SURFACE, "axes.facecolor": SURFACE,
    "savefig.facecolor": SURFACE,
    "axes.edgecolor": MUTED, "axes.labelcolor": INK,
    "xtick.color": MUTED, "ytick.color": MUTED, "text.color": INK,
    "axes.grid": True, "grid.color": GRID, "grid.linewidth": 0.8,
    "axes.spines.top": False, "axes.spines.right": False,
    "font.size": 11, "axes.titlesize": 12,
})

RNG_SEED = 42          # fixed seed for every random draw in this post
TOL = 1e-6             # numerical tolerance used for all constraint checks


def md_table(headers, rows):
    """Render a small Markdown table without extra dependencies."""
    head = "| " + " | ".join(headers) + " |"
    sep = "|" + "|".join(["---"] * len(headers)) + "|"
    body = ["| " + " | ".join(str(c) for c in r) + " |" for r in rows]
    return Markdown("\n".join([head, sep, *body]))


def scatter_classes(ax, X, y, s=70, sv_mask=None):
    """Class -1 as blue circles, class +1 as orange squares (shape backs up color)."""
    neg, pos = y < 0, y > 0
    ax.scatter(*X[neg].T, s=s, c=BLUE, marker="o", zorder=3,
               edgecolor=SURFACE, linewidth=1.2, label="class $-1$")
    ax.scatter(*X[pos].T, s=s, c=ORANGE, marker="s", zorder=3,
               edgecolor=SURFACE, linewidth=1.2, label="class $+1$")
    if sv_mask is not None and sv_mask.any():
        ax.scatter(*X[sv_mask].T, s=s * 3.4, facecolor="none",
                   edgecolor=INK, linewidth=1.6, zorder=4,
                   label="support vector")


def draw_hyperplane(ax, w, b, level=0.0, x1lim=(-1, 6), **kw):
    """Draw the line w@x + b = level over the given x1 range."""
    w = np.asarray(w, dtype=float)
    x1 = np.array(x1lim, dtype=float)
    if abs(w[1]) > 1e-12:
        ax.plot(x1, (level - b - w[0] * x1) / w[1], **kw)
    else:  # vertical line x1 = (level - b) / w1
        ax.axvline((level - b) / w[0], **kw)


def draw_svm(ax, w, b, x1lim=(-1, 6)):
    """Decision boundary plus the two margin lines w@x + b = ±1."""
    draw_hyperplane(ax, w, b, 0.0, x1lim, color=INK, lw=2.0,
                    label=r"boundary $w^\top x + b = 0$")
    for lv in (-1.0, 1.0):
        draw_hyperplane(ax, w, b, lv, x1lim, color=MUTED, lw=1.4, ls="--",
                        label=r"margin $w^\top x + b = \pm 1$" if lv > 0 else None)


# ---- Dataset A: linearly separable, chosen for clean numbers -----------------
X_A = np.array([
    [1.0, 1.0], [0.0, 1.5], [1.5, 0.0], [0.3, 0.4], [1.2, 0.2],   # class -1
    [3.0, 3.0], [2.8, 3.4], [3.5, 4.0], [4.0, 2.5], [4.5, 3.2],   # class +1
])
y_A = np.array([-1, -1, -1, -1, -1, +1, +1, +1, +1, +1])
n_A = len(y_A)

1 Linear classifier

A linear classifier uses

\[ f(x) = w^\top x + b, \]

with decision boundary \(\{x : w^\top x + b = 0\}\). Predict class \(+1\) if \(f(x)>0\), class \(-1\) if \(f(x)<0\).

2 Separation constraints

Training data \((x_i, y_i)\) with \(y_i\in\{-1,+1\}\) is separated when

\[ y_i \left( w^\top x_i + b \right) > 0, \qquad i = 1, \ldots, n. \]

Multiplying by \(y_i\) unifies both class cases in one inequality.

3 Dataset A

3.1 Data provenance

  • Source: Synthetic; ten hand-chosen 2D points, five per class.
  • Objective: Hard-margin SVM with analytically known solution.
  • Why synthetic: Closest cross-class pair is \((1,1)\) and \((3,3)\); optimal boundary is their perpendicular bisector \(x_1+x_2=4\), enabling exact checks.

Infinitely many hyperplanes can satisfy separation on separable data. Training accuracy alone does not select among them.

Verify and plot three separating lines 
candidates = {
    "(a)  $x_1 + x_2 = 4$":            (np.array([1.0, 1.0]),  -4.0),
    "(b)  $2x_1 + x_2 = 6.5$":         (np.array([2.0, 1.0]),  -6.5),
    "(c)  $0.3x_1 + x_2 = 2.8$":       (np.array([0.3, 1.0]),  -2.8),
}
for name, (w_c, b_c) in candidates.items():
    worst = np.min(y_A * (X_A @ w_c + b_c))
    assert worst > 0, f"candidate {name} does not separate the data"

fig, ax = plt.subplots(figsize=(7.5, 5.6))
scatter_classes(ax, X_A, y_A)
for (name, (w_c, b_c)), ls in zip(candidates.items(), ["-", "--", "-."]):
    draw_hyperplane(ax, w_c, b_c, 0.0, (-1, 6), color=MUTED, lw=1.8, ls=ls,
                    label=name)
ax.set_xlim(-0.7, 5.4); ax.set_ylim(-0.7, 5.2); ax.set_aspect("equal")
ax.set_xlabel("$x_1$"); ax.set_ylabel("$x_2$")
ax.legend(frameon=False, loc="upper left", bbox_to_anchor=(1.01, 1.0),
          fontsize=9)
ax.set_title("Many hyperplanes separate the same data")
plt.tight_layout()
plt.show()
Figure 1: Three different lines, each verified to classify all ten training points correctly. Training accuracy alone cannot choose between them — line (c) skims dangerously close to the orange class, yet separates the data just as ‘perfectly’ as the others.

4 Geometric margin

Perpendicular distance from \(x_i\) to \(\{x : w^\top x + b = 0\}\):

\[ \operatorname{dist}(x_i) = \frac{\left| w^\top x_i + b \right|}{\lVert w \rVert}. \]

  • Functional margin: \(|f(x_i)|\) — scales with \((w,b)\).
  • Geometric margin: \(|f(x_i)|/\lVert w\rVert\) — scale-invariant distance.

Margin of a separating hyperplane:

\[ \gamma(w, b) = \min_i \frac{y_i \left( w^\top x_i + b \right)}{\lVert w \rVert}. \]

Geometric margin of each candidate line 
rows = []
for name, (w_c, b_c) in candidates.items():
    d = y_A * (X_A @ w_c + b_c) / np.linalg.norm(w_c)
    rows.append([name, f"{d.min():.3f}",
                 f"({X_A[d.argmin()][0]:g}, {X_A[d.argmin()][1]:g})"])
md_table(["candidate line", "geometric margin $\\gamma$ (distance)",
          "closest training point"], rows)
candidate line geometric margin \(\gamma\) (distance) closest training point
(a) \(x_1 + x_2 = 4\) 1.414 (1, 1)
(b) \(2x_1 + x_2 = 6.5\) 1.118 (3, 3)
(c) \(0.3x_1 + x_2 = 2.8\) 0.862 (4, 2.5)

Line (a) has \(\gamma\approx1.414\); line (c) has \(\gamma\approx0.86\) with closest point \((4,2.5)\).

5 Canonical scaling

\((w,b)\) and \((cw,cb)\) describe the same hyperplane for \(c>0\). Impose

\[ y_i \left( w^\top x_i + b \right) \ge 1, \qquad i = 1, \ldots, n, \]

with equality at the nearest point(s). Under this convention:

  • One-sided geometric margin: \(1/\lVert w\rVert\).
  • Full margin width (between \(w^\top x+b=\pm1\)): \(2/\lVert w\rVert\).

6 Hard-margin primal

Maximizing \(1/\lVert w\rVert\) under canonical scaling equals minimizing \(\tfrac12\lVert w\rVert^2\):

\[ \begin{aligned} \min_{w, b} \quad & \tfrac{1}{2} \lVert w \rVert^2 \\ \text{subject to} \quad & y_i \left( w^\top x_i + b \right) \ge 1, \qquad i = 1, \ldots, n. \end{aligned} \]

This is a convex quadratic program (QP): convex quadratic objective, linear constraints.

7 Analytic solution on Dataset A

Closest pair: \((1,1)\) and \((3,3)\). Perpendicular bisector: \(x_1+x_2=4\), so \(w^\star=(0.5,0.5)\), \(b^\star=-2\), full margin width \(2/\lVert w^\star\rVert=2\sqrt{2}\).

Hard-margin QP in CVXPY, with assertions against the analytic solution 
w = cp.Variable(2)
b = cp.Variable()
margin_cons = [cp.multiply(y_A, X_A @ w + b) >= 1]
hard = cp.Problem(cp.Minimize(0.5 * cp.sum_squares(w)), margin_cons)
hard.solve(solver=cp.CLARABEL)

w_hard, b_hard = w.value, b.value
alpha_hard = margin_cons[0].dual_value        # Lagrange multipliers (used later)
func_margins = y_A * (X_A @ w_hard + b_hard)
sv_mask_hard = np.isclose(func_margins, 1.0, atol=1e-4)
width_hard = 2 / np.linalg.norm(w_hard)

assert hard.status == "optimal"
assert np.allclose(w_hard, [0.5, 0.5], atol=1e-5), w_hard
assert abs(b_hard - (-2.0)) < 1e-5, b_hard
assert func_margins.min() >= 1 - TOL           # all constraints satisfied
assert sv_mask_hard.sum() == 2                 # exactly (1,1) and (3,3)

print(f"solver status   : {hard.status}")
print(f"w* = ({w_hard[0]:.6f}, {w_hard[1]:.6f}),  b* = {b_hard:.6f}")
print(f"decision boundary: {w_hard[0]:.3f}·x1 + {w_hard[1]:.3f}·x2 "
      f"+ {b_hard:.3f} = 0   (i.e. x1 + x2 = 4)")
print(f"one-sided margin : 1/||w|| = {1/np.linalg.norm(w_hard):.6f}  (= √2)")
print(f"full margin width: 2/||w|| = {width_hard:.6f}  (= 2√2)")
print(f"support vectors  : {[tuple(p) for p in X_A[sv_mask_hard]]}")
print(f"min_i y_i(w·x_i+b) = {func_margins.min():.8f}  (≥ 1 − {TOL:g} ✓)")
solver status   : optimal
w* = (0.500000, 0.500000),  b* = -2.000000
decision boundary: 0.500·x1 + 0.500·x2 + -2.000 = 0   (i.e. x1 + x2 = 4)
one-sided margin : 1/||w|| = 1.414214  (= √2)
full margin width: 2/||w|| = 2.828427  (= 2√2)
support vectors  : [(np.float64(1.0), np.float64(1.0)), (np.float64(3.0), np.float64(3.0))]
min_i y_i(w·x_i+b) = 1.00000000  (≥ 1 − 1e-06 ✓)

Points with \(y_i f(x_i)=1\) are support vectors — they define the margin. Inactive constraints have slack \(>1\).

Per-point constraint check 
rows = []
for i in range(n_A):
    rows.append([
        f"({X_A[i,0]:g}, {X_A[i,1]:g})", f"{y_A[i]:+d}",
        f"{func_margins[i]:.4f}",
        f"{func_margins[i]/np.linalg.norm(w_hard):.4f}",
        "**support vector**" if sv_mask_hard[i] else "interior",
    ])
md_table(["$x_i$", "$y_i$", "$y_i(w^\\top x_i + b)$",
          "distance to boundary", "role"], rows)
\(x_i\) \(y_i\) \(y_i(w^\top x_i + b)\) distance to boundary role
(1, 1) -1 1.0000 1.4142 support vector
(0, 1.5) -1 1.2500 1.7678 interior
(1.5, 0) -1 1.2500 1.7678 interior
(0.3, 0.4) -1 1.6500 2.3335 interior
(1.2, 0.2) -1 1.3000 1.8385 interior
(3, 3) +1 1.0000 1.4142 support vector
(2.8, 3.4) +1 1.1000 1.5556 interior
(3.5, 4) +1 1.7500 2.4749 interior
(4, 2.5) +1 1.2500 1.7678 interior
(4.5, 3.2) +1 1.8500 2.6163 interior
Plot the hard-margin solution 
fig, ax = plt.subplots(figsize=(7.5, 5.8))
scatter_classes(ax, X_A, y_A, sv_mask=sv_mask_hard)
draw_svm(ax, w_hard, b_hard)

# perpendicular distance arrows from each support vector to the boundary
u = w_hard / np.linalg.norm(w_hard)          # unit normal
for sv, sign in zip(X_A[sv_mask_hard], (-1, +1)):
    foot = sv - (w_hard @ sv + b_hard) / np.linalg.norm(w_hard) * u
    ax.annotate("", xy=foot, xytext=sv,
                arrowprops=dict(arrowstyle="<->", color=INK, lw=1.2))
ax.annotate(r"$\frac{1}{\Vert w\Vert}=\sqrt{2}$ each side",
            xy=(2.0, 2.0), xytext=(2.7, 0.6), fontsize=10,
            arrowprops=dict(arrowstyle="->", color=MUTED))
ax.set_xlim(-0.7, 5.4); ax.set_ylim(-0.7, 5.2); ax.set_aspect("equal")
ax.set_xlabel("$x_1$"); ax.set_ylabel("$x_2$")
ax.legend(frameon=False, loc="upper left", bbox_to_anchor=(1.01, 1.0),
          fontsize=9)
ax.set_title(r"Hard-margin SVM: full band width $2/\Vert w\Vert = 2\sqrt{2}$")
plt.tight_layout()
plt.show()
Figure 2: The maximum-margin solution for Dataset A: boundary \(x_1+x_2=4\) (solid), margin lines \(w^\top x + b = \pm 1\) (dashed), support vectors ringed in black. Each support vector sits exactly \(1/\lVert w\rVert = \sqrt{2}\) from the boundary; the full band is \(2\sqrt{2} \approx 2.83\) wide.

8 Convexity of the hard-margin QP

  • Objective: \(\tfrac12\lVert w\rVert^2\) is strictly convex in \(w\); \(b\) does not appear in the objective.
  • Constraints: Each \(y_i(w^\top x_i+b)\ge1\) is a linear half-space in \((w,b)\).
  • Feasible set: Intersection of half-spaces — a convex polyhedron.

Consequences:

  • Every local minimum is global.
  • Interior-point solvers (CLARABEL) return certified optima via duality.
  • No random restarts required.

Limits:

  • Feasibility: Non-separable data yields empty feasible set (Section 11).
  • Uniqueness: Convexity does not imply a unique minimizer in all variables (Section 9, Section 12).
  • Numerical tolerance: Checks use TOL = 1e-6.

Eliminating \(b\), feasible \((w_1,w_2)\) satisfy \(w^\top(x_i-x_j)\ge2\) for all cross-class pairs \((i,j)\).

Feasible region in (w1, w2) after eliminating b 
g = np.linspace(-0.15, 1.25, 500)
W1, W2 = np.meshgrid(g, g)
feasible = np.ones_like(W1, dtype=bool)
for xp in X_A[y_A > 0]:
    for xn in X_A[y_A < 0]:
        d = xp - xn
        feasible &= (W1 * d[0] + W2 * d[1]) >= 2

fig, ax = plt.subplots(figsize=(6.8, 6.2))
ax.contourf(W1, W2, feasible.astype(float), levels=[0.5, 1.5],
            colors=["#2a78d633"])
ax.contour(W1, W2, feasible.astype(float), levels=[0.5],
           colors=[BLUE], linewidths=1.4)
R = np.sqrt(W1**2 + W2**2)
cs = ax.contour(W1, W2, 0.5 * R**2, levels=[0.0625, 0.125, 0.25, 0.5, 0.9],
                colors=[MUTED], linewidths=0.9, linestyles=":")
ax.clabel(cs, fmt=lambda v: rf"$\frac{{1}}{{2}}\|w\|^2$={v:g}", fontsize=7)
ax.scatter([w_hard[0]], [w_hard[1]], s=90, c=INK, zorder=5)
ax.annotate(r"$w^\star = (0.5,\ 0.5)$", xy=w_hard, xytext=(0.60, 0.34),
            fontsize=11, arrowprops=dict(arrowstyle="->", color=INK))
ax.annotate("feasible: some $b$ satisfies\nevery margin constraint",
            xy=(0.82, 0.95), fontsize=9, color=INK, ha="center")
ax.set_xlabel("$w_1$"); ax.set_ylabel("$w_2$"); ax.set_aspect("equal")
ax.set_title("Smallest norm ball touching the feasible region")
plt.tight_layout()
plt.show()
Figure 3: The QP in parameter space with the intercept eliminated: each cross-class pair of training points imposes the half-plane \(w^\top(x_i - x_j) \ge 2\) on \((w_1, w_2)\); their intersection is the shaded feasible region. The objective’s circular level sets shrink toward the origin, and \(w^\star = (0.5, 0.5)\) is the point of the feasible region closest to the origin — its active edge is generated by the support-vector pair \((3,3)\) and \((1,1)\).

9 Uniqueness

For feasible two-class hard-margin SVMs:

  • \(w^\star\) is unique (strict convexity in \(w\)).
  • \(b^\star\) collapses to a point when both classes contribute binding constraints at optimum.
b-interval collapse + independent solvers agree 
b_lo = np.max(1 - X_A[y_A > 0] @ w_hard)      # +1 class: b ≥ 1 − w·x
b_hi = np.min(-1 - X_A[y_A < 0] @ w_hard)     # −1 class: b ≤ −1 − w·x
print(f"b interval given w*: [{b_lo:.6f}, {b_hi:.6f}]  →  width "
      f"{b_hi - b_lo:.2e} (collapses to the point b* = −2)")

hard.solve(solver=cp.OSQP)
print(f"OSQP     : w = ({w.value[0]:.6f}, {w.value[1]:.6f}), b = {b.value:.6f}")
print(f"CLARABEL : w = ({w_hard[0]:.6f}, {w_hard[1]:.6f}), b = {b_hard:.6f}")
assert np.allclose(w.value, w_hard, atol=1e-3) and abs(b.value - b_hard) < 1e-3
hard.solve(solver=cp.CLARABEL)   # restore the reference solution
b interval given w*: [-2.000000, -2.000000]  →  width 3.11e-10 (collapses to the point b* = −2)
OSQP     : w = (0.500000, 0.500000), b = -2.000000
CLARABEL : w = (0.500000, 0.500000), b = -2.000000
np.float64(0.25000000007783907)

9.1 One-class degeneracy

With only \(+1\) points, \((w,b)=(0,b)\) with \(b\ge1\) is feasible and optimal (\(\tfrac12\lVert w\rVert^2=0\)). \(w^\star=0\) is unique; \(b^\star\) is not; no hyperplane exists.

One-class degenerate solve with two solvers 
w1c, b1c = cp.Variable(2), cp.Variable()
one_class = cp.Problem(cp.Minimize(0.5 * cp.sum_squares(w1c)),
                       [X_A[y_A > 0] @ w1c + b1c >= 1])
for solver in (cp.CLARABEL, cp.SCS):
    one_class.solve(solver=solver)
    print(f"{solver:<9}: status={one_class.status},  ||w|| = "
          f"{np.linalg.norm(w1c.value):.2e},  b = {b1c.value:.4f}")
    assert np.linalg.norm(w1c.value) < 1e-3   # w* = 0 in both cases
CLARABEL : status=optimal,  ||w|| = 5.25e-10,  b = 3.0166
SCS      : status=optimal,  ||w|| = 4.87e-12,  b = 1.0000

10 Duality and support vectors

Lagrangian with multipliers \(\alpha_i\ge0\):

\[ \mathcal{L}(w, b, \alpha) = \tfrac12 \lVert w \rVert^2 - \sum_{i} \alpha_i \left[ y_i \left( w^\top x_i + b \right) - 1 \right]. \]

Stationarity:

\[ w = \sum_i \alpha_i y_i x_i, \qquad \sum_i \alpha_i y_i = 0. \]

  • Complementary slackness: \(\alpha_i[y_i f(x_i)-1]=0\) — only margin points have \(\alpha_i>0\).
  • Class balance: \(\sum_i \alpha_i y_i=0\).

Dual problem:

\[ \max_{\alpha \ge 0,\ \sum_i \alpha_i y_i = 0} \;\; \sum_i \alpha_i - \tfrac12 \sum_{i,j} \alpha_i \alpha_j y_i y_j \, x_i^\top x_j. \]

Data enter only through dot products \(x_i^\top x_j\) (kernel extension point).

Dual variables: support vectors carry all the weight 
rows = [[f"({X_A[i,0]:g}, {X_A[i,1]:g})", f"{y_A[i]:+d}",
         f"{alpha_hard[i]:.6f}",
         f"{alpha_hard[i] * (func_margins[i] - 1):.1e}"]
        for i in range(n_A)]
display(md_table(["$x_i$", "$y_i$", "$\\alpha_i$",
                  "$\\alpha_i\\,[y_i f(x_i) - 1]$ (compl. slack)"], rows))

w_from_alpha = (alpha_hard * y_A) @ X_A
dual_val = alpha_hard.sum() - 0.5 * np.linalg.norm(w_from_alpha) ** 2
print(f"stationarity  ||w* − Σαᵢyᵢxᵢ||  = "
      f"{np.linalg.norm(w_hard - w_from_alpha):.2e}")
print(f"balance        Σαᵢyᵢ           = {(alpha_hard * y_A).sum():+.2e}")
print(f"strong duality: dual objective  = {dual_val:.6f} "
      f"vs primal ½||w*||² = {0.5*np.linalg.norm(w_hard)**2:.6f}")
assert np.allclose(alpha_hard[sv_mask_hard], 0.25, atol=1e-4)
assert np.all(alpha_hard[~sv_mask_hard] < 1e-6)
\(x_i\) \(y_i\) \(\alpha_i\) \(\alpha_i\,[y_i f(x_i) - 1]\) (compl. slack)
(1, 1) -1 0.250000 4.4e-11
(0, 1.5) -1 0.000000 2.8e-11
(1.5, 0) -1 0.000000 4.4e-11
(0.3, 0.4) -1 0.000000 4.2e-11
(1.2, 0.2) -1 0.000000 4.0e-11
(3, 3) +1 0.250000 3.4e-11
(2.8, 3.4) +1 0.000000 5.7e-11
(3.5, 4) +1 0.000000 4.0e-11
(4, 2.5) +1 0.000000 3.4e-11
(4.5, 3.2) +1 0.000000 3.8e-11 
stationarity  ||w* − Σαᵢyᵢxᵢ||  = 2.33e-10
balance        Σαᵢyᵢ           = -6.50e-11
strong duality: dual objective  = 0.250000 vs primal ½||w*||² = 0.250000

Eight of ten points have \(\alpha_i=0\).

11 Soft-margin SVM

11.1 Dataset B

  • Source: Synthetic — two Gaussian clusters (\(n=20\) each, \(\sigma=0.75\), centres \((1.4,1.6)\) and \((3.3,3.1)\)) plus one planted outlier \((4.3,3.7)\) labelled \(-1\), seed RNG_SEED=42.
  • Objective: Soft-margin QP; compare behaviour across \(C\).
  • Why synthetic: Overlap and outlier are known; hard margin is provably infeasible.
Dataset B + hard margin is infeasible on it 
rng = np.random.default_rng(RNG_SEED)
X_neg = rng.normal(loc=[1.4, 1.6], scale=0.75, size=(20, 2))
X_pos = rng.normal(loc=[3.3, 3.1], scale=0.75, size=(20, 2))
outlier = np.array([[4.3, 3.7]])                       # labeled −1, sits among +1
X_B = np.vstack([X_neg, outlier, X_pos])
y_B = np.array([-1] * 21 + [+1] * 20)
n_B = len(y_B)

wi, bi = cp.Variable(2), cp.Variable()
infeas = cp.Problem(cp.Minimize(0.5 * cp.sum_squares(wi)),
                    [cp.multiply(y_B, X_B @ wi + bi) >= 1])
infeas.solve(solver=cp.CLARABEL)
print(f"hard margin on Dataset B: status = {infeas.status}")
assert infeas.status == "infeasible"
hard margin on Dataset B: status = infeasible

11.2 Primal formulation

Slack variables \(\xi_i\ge0\) permit margin violations at cost \(C\) per unit:

\[ \begin{aligned} \min_{w, b, \xi} \quad & \tfrac12 \lVert w \rVert^2 + C \sum_i \xi_i \\ \text{subject to} \quad & y_i \left( w^\top x_i + b \right) \ge 1 - \xi_i, \\ & \xi_i \ge 0, \qquad i = 1, \ldots, n. \end{aligned} \]

At optimum: \(\xi_i = \max(0, 1 - y_i f(x_i))\).

  • \(\xi_i=0\): on or outside margin.
  • \(0<\xi_i\le1\): inside margin, correct class.
  • \(\xi_i>1\): misclassified.

\(C\) trades margin width against total slack.

Solve the soft-margin QP for three values of C 
def solve_soft(X, y, C, solver=cp.CLARABEL):
    n = len(y)
    w_, b_, xi_ = cp.Variable(2), cp.Variable(), cp.Variable(n)
    cons = [cp.multiply(y, X @ w_ + b_) >= 1 - xi_, xi_ >= 0]
    prob = cp.Problem(cp.Minimize(0.5 * cp.sum_squares(w_) + C * cp.sum(xi_)),
                      cons)
    prob.solve(solver=solver)
    assert prob.status == "optimal", (C, prob.status)
    return dict(C=C, w=w_.value, b=b_.value, xi=np.maximum(xi_.value, 0),
                alpha=cons[0].dual_value, obj=prob.value)

C_values = [0.05, 1.0, 100.0]
fits = [solve_soft(X_B, y_B, C) for C in C_values]

rows = []
for f in fits:
    fm = y_B * (X_B @ f["w"] + f["b"])
    n_violate = int((f["xi"] > TOL).sum())          # ξ > tol: inside margin or worse
    n_miscls = int((fm < 0).sum())                  # y·f(x) < 0 (equivalently ξ > 1)
    n_sv = int((f["alpha"] > 1e-5 * f["C"]).sum())  # α > tol: touching or violating
    rows.append([f"{f['C']:g}",
                 f"({f['w'][0]:.3f}, {f['w'][1]:.3f})", f"{f['b']:.3f}",
                 f"{2/np.linalg.norm(f['w']):.3f}",
                 f"{f['xi'].sum():.3f}", n_violate, n_miscls, n_sv])
md_table(["$C$", "$w$", "$b$", "margin width $2/\\lVert w\\rVert$",
          "$\\sum_i \\xi_i$", "margin violations ($\\xi_i > 10^{-6}$)",
          "misclassified ($y_if_i<0$)", "SV-like points ($\\alpha_i>0$)"], rows)
\(C\) \(w\) \(b\) margin width \(2/\lVert w\rVert\) \(\sum_i \xi_i\) margin violations (\(\xi_i > 10^{-6}\)) misclassified (\(y_if_i<0\)) SV-like points (\(\alpha_i>0\))
0.05 (0.458, 0.552) -2.437 2.789 13.089 22 2 24
1 (0.809, 1.095) -4.849 1.470 8.964 10 3 12
100 (0.868, 2.019) -7.195 0.910 8.675 7 2 10
Per-point slack summary for the medium C = 1 fit 
f1 = fits[1]
fm1 = y_B * (X_B @ f1["w"] + f1["b"])
kinds = np.select(
    [fm1 < 0, f1["xi"] > TOL, f1["alpha"] > 1e-5],
    ["misclassified", "inside margin", "on margin"], "outside margin")
rows = [[k, int((kinds == k).sum()),
         f"{f1['xi'][kinds == k].sum():.3f}"]
        for k in ["outside margin", "on margin", "inside margin", "misclassified"]]
md_table(["point status at $C=1$", "count", "total slack $\\sum \\xi_i$"], rows)
point status at \(C=1\) count total slack \(\sum \xi_i\)
outside margin 29 0.000
on margin 2 0.000
inside margin 7 2.711
misclassified 3 6.252
Side-by-side decision boundaries for the three C values 
fig, axes = plt.subplots(1, 3, figsize=(12.6, 4.6), sharey=True)
for ax, f in zip(axes, fits):
    fm = y_B * (X_B @ f["w"] + f["b"])
    sv_like = f["alpha"] > 1e-5 * f["C"]
    miscls = fm < 0
    scatter_classes(ax, X_B, y_B, s=42, sv_mask=sv_like)
    ax.scatter(*X_B[miscls].T, s=120, marker="x", c=INK, lw=1.8, zorder=5,
               label="misclassified")
    draw_svm(ax, f["w"], f["b"], x1lim=(-2, 7))
    ax.set_xlim(-0.6, 5.6); ax.set_ylim(-0.6, 5.4); ax.set_aspect("equal")
    ax.set_xlabel("$x_1$")
    ax.set_title(rf"$C = {f['C']:g}$  —  width $= "
                 rf"{2/np.linalg.norm(f['w']):.2f}$")
axes[0].set_ylabel("$x_2$")
handles, labels = axes[0].get_legend_handles_labels()
fig.legend(handles, labels, frameon=False, loc="upper center",
           bbox_to_anchor=(0.5, 1.0), ncols=6, fontsize=9)
plt.tight_layout(rect=[0, 0, 1, 0.92])
plt.show()
Figure 4: The same non-separable data under three violation prices. Small \(C\) buys a wide corridor and tolerates several points inside it; large \(C\) narrows the band to reduce slack. Ringed points have \(\alpha_i > 0\) (support-vector-like); black × marks misclassified points — the planted outlier at (4.3, 3.7) is lost at every \(C\). Axes are identical across panels.
  • Small \(C\): Wide margin; more slack and violations tolerated.
  • Large \(C\): Narrow margin; lower \(\sum_i\xi_i\); outlier remains misclassified.

12 Non-unique intercept (soft margin)

For \(x_-=(-1,0)\), \(x_+=(+1,0)\), \(C=0.25\): both slack terms active, \(b\) cancels from the objective. Optimal \(w_1=2C=0.5\); every \(b\in[-0.5,+0.5]\) gives the same objective \(0.375\).

Flat-b demonstration: solver disagreement + objective scan 
X_flat = np.array([[-1.0, 0.0], [1.0, 0.0]])
y_flat = np.array([-1, +1])
C_flat = 0.25

sol_a = solve_soft(X_flat, y_flat, C_flat, solver=cp.CLARABEL)
sol_b = solve_soft(X_flat, y_flat, C_flat, solver=cp.OSQP)
print(f"CLARABEL: w = ({sol_a['w'][0]:.4f}, {sol_a['w'][1]:.4f}), "
      f"b = {sol_a['b']:+.4f}, objective = {sol_a['obj']:.6f}")
print(f"OSQP    : w = ({sol_b['w'][0]:.4f}, {sol_b['w'][1]:.4f}), "
      f"b = {sol_b['b']:+.4f}, objective = {sol_b['obj']:.6f}")
assert abs(sol_a["obj"] - sol_b["obj"]) < 1e-5      # same optimal value...
assert np.allclose(sol_a["w"], sol_b["w"], atol=1e-3)  # ...same w*

# scan: freeze b, minimize over (w, ξ) — the floor of this curve is the optimal set
b_grid = np.linspace(-1.2, 1.2, 97)
obj_b = []
for b_fix in b_grid:
    w_, xi_ = cp.Variable(2), cp.Variable(2)
    p = cp.Problem(
        cp.Minimize(0.5 * cp.sum_squares(w_) + C_flat * cp.sum(xi_)),
        [cp.multiply(y_flat, X_flat @ w_ + b_fix) >= 1 - xi_, xi_ >= 0])
    p.solve(solver=cp.CLARABEL)
    obj_b.append(p.value)
obj_b = np.array(obj_b)
flat = np.abs(b_grid) <= 0.5
assert obj_b[flat].max() - obj_b[flat].min() < 1e-6   # exactly flat inside
assert obj_b[np.abs(b_grid) > 0.55].min() > obj_b[flat].max() + 1e-4

fig, (axL, axR) = plt.subplots(1, 2, figsize=(11.5, 4.3))
axL.plot(b_grid, obj_b, color=BLUE, lw=2)
axL.axvspan(-0.5, 0.5, color="#2a78d61f", label=r"optimal set of $b$")
for sol, name, c in [(sol_a, "CLARABEL", INK), (sol_b, "OSQP", ORANGE)]:
    axL.scatter([sol["b"]], [sol["obj"]], s=70, c=c, zorder=5, label=name)
axL.set_xlabel("intercept $b$ (frozen per solve)")
axL.set_ylabel("optimal objective value")
axL.legend(frameon=False, fontsize=9)
axL.set_title(rf"Flat floor: every $b\in[-0.5,0.5]$ is optimal ($C={C_flat}$)")

scatter_classes(axR, X_flat, y_flat, s=120)
for b_show in np.linspace(-0.5, 0.5, 9):
    axR.axvline(-2 * b_show, color=MUTED, lw=1.0, alpha=0.55)
axR.axvline(0, color=INK, lw=1.6, label="equally optimal boundaries")
axR.set_xlim(-2.2, 2.2); axR.set_ylim(-1.4, 1.4)
axR.set_xlabel("$x_1$"); axR.set_ylabel("$x_2$")
axR.legend(frameon=False, fontsize=9, loc="upper left")
axR.set_title("All of these lines minimize the soft-margin objective")
plt.tight_layout()
plt.show()
CLARABEL: w = (0.5000, 0.0000), b = +0.0000, objective = 0.375000
OSQP    : w = (0.5000, 0.0000), b = -0.0000, objective = 0.375000
Figure 5: A valid two-class case with a non-unique intercept. Left: the optimal objective as a function of \(b\) (each dot is a full CVXPY solve with \(b\) frozen) is exactly flat on \([-0.5, 0.5]\); two solvers pick different points on the flat floor. Right: the corresponding band of equally optimal decision boundaries — the normal vector is pinned, the position is not.

Documented in Burges & Crisp, Uniqueness of the SVM Solution (NeurIPS 1999).

13 Verification

Constraint audits for all solved problems 
print(f"tolerance used in all checks: {TOL:g}\n")
print("hard margin (Dataset A):")
print(f"  min_i  y_i(w·x_i + b)          = {func_margins.min():.10f}  ≥ 1 − tol ✓")

print("\nsoft margin (Dataset B):")
for f in fits:
    resid = y_B * (X_B @ f["w"] + f["b"]) + f["xi"]
    print(f"  C = {f['C']:>6g}:  min_i [y_i(w·x_i+b) + ξ_i] = "
          f"{resid.min():.10f}  ≥ 1 − tol ✓,   min ξ_i = {f['xi'].min():.1e} ≥ 0 ✓")
    assert resid.min() >= 1 - 1e-5 and f["xi"].min() >= -TOL
tolerance used in all checks: 1e-06

hard margin (Dataset A):
  min_i  y_i(w·x_i + b)          = 1.0000000001  ≥ 1 − tol ✓

soft margin (Dataset B):
  C =   0.05:  min_i [y_i(w·x_i+b) + ξ_i] = 0.9999999963  ≥ 1 − tol ✓,   min ξ_i = 0.0e+00 ≥ 0 ✓
  C =      1:  min_i [y_i(w·x_i+b) + ξ_i] = 0.9999999945  ≥ 1 − tol ✓,   min ξ_i = 0.0e+00 ≥ 0 ✓
  C =    100:  min_i [y_i(w·x_i+b) + ξ_i] = 0.9999999998  ≥ 1 − tol ✓,   min ξ_i = 0.0e+00 ≥ 0 ✓

scikit-learn SVC (dual SMO) cross-check:

Cross-check against scikit-learn (optional, not the primary solve) 
from sklearn.svm import SVC

svc_hard = SVC(kernel="linear", C=1e8, tol=1e-8).fit(X_A, y_A)  # huge C ≈ hard margin
print("hard   : sklearn w =", np.round(svc_hard.coef_[0], 6),
      " b =", np.round(svc_hard.intercept_[0], 6))
assert np.allclose(svc_hard.coef_[0], w_hard, atol=1e-4)
assert abs(svc_hard.intercept_[0] - b_hard) < 1e-4

for f in fits:
    svc = SVC(kernel="linear", C=f["C"], tol=1e-8).fit(X_B, y_B)
    dw = np.linalg.norm(svc.coef_[0] - f["w"])
    db = abs(svc.intercept_[0] - f["b"])
    print(f"C={f['C']:>6g}: sklearn w = {np.round(svc.coef_[0], 4)}, "
          f"b = {svc.intercept_[0]:+.4f}   (‖Δw‖ = {dw:.1e}, |Δb| = {db:.1e})")
    assert dw < 1e-3 and db < 1e-3
hard   : sklearn w = [0.5 0.5]  b = -2.0
C=  0.05: sklearn w = [0.4575 0.5523], b = -2.4371   (‖Δw‖ = 5.0e-08, |Δb| = 1.6e-07)
C=     1: sklearn w = [0.8088 1.0946], b = -4.8491   (‖Δw‖ = 5.3e-07, |Δb| = 1.5e-06)
C=   100: sklearn w = [0.8676 2.0191], b = -7.1951   (‖Δw‖ = 1.8e-04, |Δb| = 4.2e-04)

14 Summary views

Four equivalent perspectives on one fit:

  • Input space: boundary, margin band, support vectors (Figure 2).
  • Parameter space: half-space constraints; norm-ball contact (Figure 3).
  • Dual: sparse \(\alpha_i>0\) subset (Section 10).
  • Regularization: \(C\) vs margin width and slack (Figure 4).

15 Common misconceptions

  1. Separating lines are equivalent. Same training accuracy; margins differ (Figure 1: \(\gamma=1.414\) vs \(0.86\)).
  2. Convex implies unique optimizer. Soft-margin flat-\(b\) example (Figure 5); needs extra conditions (Section 9).
  3. Margin equals one-sided distance. Full band width is \(2/\lVert w\rVert\) (Figure 2).
  4. Large \(C\) improves generalization. Tightens training fit; outlier stays wrong on Dataset B (Figure 4).
  5. Solver success implies feasibility. Hard margin returns infeasible on Dataset B.

16 References

  • CVXPY — convex modeling and solvers (CLARABEL, OSQP).
  • Burges & Crisp (1999), Uniqueness of the SVM Solution — soft-margin non-uniqueness at small \(C\).
  • scikit-learn SVC — dual SMO cross-check.