Dual Problem

optimisation machine-learning

Definition

Dual Problem

In mathematical optimisation, the dual problem is an alternative formulation of a constrained optimisation problem (the primal problem) derived using Lagrange multipliers. Formally, for a primal problem seeking to minimise $f(\mathbf{x})$ subject to $g_i(\mathbf{x})\le 0$, the dual objective $q(\lambda )$ is defined as the infimum of the Lagrangian over $\mathbf{x}$:

$q(\lambda )={\inf }_{\mathbf{x}}\mathcal{L}(\mathbf{x},\lambda )$

The dual problem then seeks to maximise $q(\lambda )$ subject to $\lambda \ge 0$. According to strong duality, if the primal is convex and satisfies certain regularity conditions, the optimal values of the primal and dual problems are identical.

Application in SVMs

Kernel Trick: Converting the primal SVM problem into its dual form is essential for kernel methods. The dual objective depends only on the inner products between data points:
${\max }_{\alpha }{\sum }_{i=1}^n{\alpha }_i-\frac{1}{2}{\sum }_{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j⟨{\mathbf{x}}_i,{\mathbf{x}}_j⟩$
By replacing the inner product with a kernel function $k({\mathbf{x}}_i,{\mathbf{x}}_j)$, the model can identify non-linear decision boundaries in high-dimensional feature spaces without explicitly computing the feature mapping $\varphi$.