Primal and dual problems

The primal problem

The original constrained problem (The Lagrangian and KKT conditions), with optimal value $p^\star$:

$$ p^\star = \min_x\ f(x) \quad \text{s.t.}\quad h_j(x)\leq0,\ \ g_i(x)=0. $$

Its Lagrangian: $L(x,\mu,\lambda) = f(x) + \sum_j\mu_jh_j(x) + \sum_i\lambda_ig_i(x)$, $\mu_j\geq0$.

The dual function

Minimize $L$ over $x$ alone, with $\mu,\lambda$ held fixed. No constraints on $x$ in this minimization:

$$ g(\mu,\lambda) := \min_x\ L(x,\mu,\lambda). $$

$g$ is a pointwise minimum, over $x$, of functions that are affine (linear plus a constant) in $(\mu,\lambda)$. A pointwise minimum of affine functions is always concave, no matter what $f,h,g$ are:

$$ g(\mu,\lambda) \text{ is concave in } (\mu,\lambda), \quad \text{always}. $$

Intuition: concavity of $g$ costs nothing and assumes nothing about the original problem; it comes free from taking a minimum over $x$ of a family of straight lines in $(\mu,\lambda)$.

The dual problem

Maximize the dual function over the multipliers, with optimal value $d^\star$:

$$ d^\star = \max_{\mu\geq0,\ \lambda}\ g(\mu,\lambda). $$

Maximizing a concave function is always tractable (The Lagrangian and KKT conditions, run in the other direction), so the dual is a well-behaved problem even when the primal is not.

Weak duality: $d^\star\leq p^\star$, always

For any feasible $x$ (meaning $h_j(x)\leq0$, $g_i(x)=0$) and any $\mu\geq0$:

$$ L(x,\mu,\lambda) = f(x) + \underbrace{\sum_j\mu_jh_j(x)}_{\leq0} + \underbrace{\sum_i\lambda_ig_i(x)}_{=0} \ \leq\ f(x). $$

Taking the minimum over $x$ on the left only shrinks it further, so $g(\mu,\lambda)\leq L(x,\mu,\lambda)\leq f(x)$ for every feasible $x$. Maximizing the left side over $(\mu,\lambda)$ and minimizing the right side over feasible $x$ preserves the inequality:

$$ d^\star \ \leq\ p^\star. $$

Intuition: the dual is a machine for generating lower bounds on $p^\star$ without ever solving the primal; every feasible $(\mu,\lambda)$ gives one such bound, and the dual problem just asks for the best one.

Strong duality: when the gap closes

$p^\star - d^\star\geq0$ is the duality gap. For a convex problem ($f,h_j$ convex, $g_i$ affine) satisfying Slater's condition (a point strictly feasible, $h_j(x)<0$ for all $j$, exists), the gap is exactly zero:

$$ d^\star = p^\star \quad \text{(strong duality).} $$

At a pair $(x^\star,\mu^\star,\lambda^\star)$ achieving strong duality, the KKT conditions hold, including complementary slackness $\mu_j^\star h_j(x^\star)=0$.

Intuition: strong duality says solving the easy (concave, unconstrained-in-$x$) dual problem is exactly as good as solving the hard primal one; Slater's condition rules out the one pathology (the feasible region being flat against a constraint everywhere) that can leave a gap.

Worked example

Reusing the running problem from The Lagrangian and KKT conditions: minimize $f(x,y)=x^2+y^2$ subject to $h(x,y)=1-x-y\leq0$.

$$ L(x,y,\mu) = x^2+y^2+\mu(1-x-y). $$

Minimize over $x,y$ (unconstrained): $\partial L/\partial x = 2x-\mu=0$, $\partial L/\partial y=2y-\mu=0$, so $x=y=\mu/2$. Substituting back:

$$ g(\mu) = 2\Big(\frac{\mu}{2}\Big)^2 + \mu\Big(1-\mu\Big) = \mu - \frac{\mu^2}{2}. $$

Maximizing over $\mu\geq0$: $g'(\mu)=1-\mu=0\ \Rightarrow\ \mu^\star=1$, $d^\star=g(1)=\tfrac12$. The primal optimum found earlier was $x^\star=y^\star=\tfrac12$, $p^\star=\tfrac12$, $\mu^\star=1$: an exact match, $d^\star=p^\star$, as strong duality predicts (the problem is convex and $x=y=1$ is strictly feasible).

Where duality is used

• Shadow prices. Replace the fixed $1$ in the constraint above with a parameter $b$ ($x+y\geq b$): the same computation gives $p^\star(b)=b^2/2$, and $dp^\star/db = b$, which equals $\mu^\star$ exactly at $b=1$. In general $\mu_j^\star$ measures the marginal change in the optimal value per unit relaxation of constraint $j$: the constraint's "price."
• The SVM dual and the kernel trick. The support vector machine's dual problem depends on the data only through inner products $x_i\cdot x_j$. Replacing that inner product with a kernel $k(x_i,x_j)$ (an inner product in some other, possibly infinite-dimensional, feature space) fits a nonlinear boundary without ever forming that feature space explicitly; this is only available because the dual, not the primal, is what gets solved.
• LP duality. For linear programs, strong duality always holds (no Slater's condition needed, beyond feasibility). Two classical results are special cases: max-flow equals min-cut, and the value of a zero-sum game (minimax theorem) is the shared optimum of a primal-dual LP pair.

Intuition: the dual is not just a proof device; its multipliers are prices, its structure enables kernels, and in the linear case its equality with the primal is itself the theorem being used.