Lagrangian Duality: From Primal to Dual

Start with a constrained minimization in standard form:

$\begin{aligned}\min_{x \in \mathbb{R}^n}\;& f(x) \\ \text{s.t.}\;& g_i(x) \le 0,\quad i = 1, \dots, m \\ & h_j(x) = 0,\quad j = 1, \dots, p\end{aligned}$

We call this the primal. Write $p^\star$ for its optimal value (possibly $+\infty$ if infeasible). $f$, $g_i$, $h_j$ can be anything for the definitions below — convexity is what we'll need later for strong duality, not for the construction itself.

The primal might be hard: non-smooth, non-convex, combinatorial. The dual problem we build next is always concave, regardless. That's its point.

Pack every constraint into the objective with a per-constraint multiplier:

$L(x, \lambda, \nu) \;=\; f(x) \;+\; \sum_{i=1}^{m} \lambda_i\, g_i(x) \;+\; \sum_{j=1}^{p} \nu_j\, h_j(x)$

The rules on the multipliers are not symmetric:

• $\lambda_i \ge 0$ for inequalities (because we want the term to penalize infeasibility, $g_i > 0$).
• $\nu_j$ free for equalities (sign doesn't matter — only $h_j = 0$ does).

For a feasible $x$, every $\lambda_i g_i(x) \le 0$ and every $\nu_j h_j(x) = 0$, so $L(x, \lambda, \nu) \le f(x)$. Hold that thought — it's the seed of weak duality.

Minimize the Lagrangian over $x$ unconstrained, treating the multipliers as parameters:

$g(\lambda, \nu) \;=\; \inf_{x \in \mathbb{R}^n} L(x, \lambda, \nu)$

Two properties hold for free, no matter what the primal looks like:

1. $g$ is concave in $(\lambda, \nu)$. It's a pointwise infimum of affine functions of $(\lambda, \nu)$ — and the pointwise infimum of affine functions is concave.
2. $g$ can be $-\infty$. If $L$ is unbounded below in $x$ for some $(\lambda, \nu)$, we drop those multipliers from consideration.

The domain of $g$ — the set where $g > -\infty$ — is where the action is.

The dual problem is to make $g$ as large as possible while respecting the sign constraint on $\lambda$:

$\begin{aligned}\max_{\lambda, \nu}\;& g(\lambda, \nu) \\ \text{s.t.}\;& \lambda \ge 0\end{aligned}$

Write $d^\star$ for the optimal dual value. Because $g$ is concave and the constraint $\lambda \ge 0$ is convex, the dual is always a convex problem — even when the primal is wildly non-convex.

That's already a striking payoff: you can hand any optimization problem a convex relaxation by passing through the Lagrangian. The question is how tight the relaxation is.

Theorem (weak duality). For any primal-feasible $x$ and any dual-feasible $(\lambda, \nu)$,

$g(\lambda, \nu) \;\le\; f(x).$

In particular, $d^\star \le p^\star$. The proof fits on a postcard:

$g(\lambda, \nu) = \inf_{x'} L(x', \lambda, \nu) \;\le\; L(x, \lambda, \nu) = f(x) + \underbrace{\sum \lambda_i g_i(x)}_{\le\, 0} + \underbrace{\sum \nu_j h_j(x)}_{=\, 0} \;\le\; f(x).$

Every dual-feasible point gives a certified lower bound on the primal optimum. This is already useful: branch-and-bound, cutting-plane methods, and the simplex method's stopping certificate all live here.

Sometimes $d^\star = p^\star$ exactly — no duality gap. We call this strong duality. Without it, the dual is a relaxation; with it, the dual is the primal in disguise.

Strong duality is not automatic, even for convex problems. The most useful sufficient condition is:

Slater's condition. If the primal is convex and there exists a strictly feasible $x$ — meaning $g_i(x) < 0$ for all non-affine $g_i$ and $h_j(x) = 0$ — then strong duality holds.

For LPs (everything affine), Slater reduces to plain feasibility: strong duality holds whenever both primal and dual are feasible. Outside convexity, strong duality can fail in subtle ways (the duality gap is then $p^\star - d^\star > 0$).

When strong duality holds, the optimal $x^\star$ and $(\lambda^\star, \nu^\star)$ jointly satisfy the Karush–Kuhn–Tucker conditions:

1. Stationarity: $\nabla f(x^\star) + \sum \lambda_i^\star \nabla g_i(x^\star) + \sum \nu_j^\star \nabla h_j(x^\star) = 0$
2. Primal feasibility: $g_i(x^\star) \le 0$, $h_j(x^\star) = 0$
3. Dual feasibility: $\lambda_i^\star \ge 0$
4. Complementary slackness: $\lambda_i^\star\, g_i(x^\star) = 0$ for every $i$

For convex problems with strong duality, KKT is necessary and sufficient. Complementary slackness is the punchline: at the optimum, either a constraint is active ($g_i = 0$) or its multiplier is zero ($\lambda_i = 0$). The multipliers tell you which constraints actually matter.

How the four objects connect:

Take the canonical LP

$\min_{x \ge 0}\; c^\top x \quad \text{s.t.}\; Ax \ge b.$

The Lagrangian (with $y \ge 0$ for $b - Ax \le 0$, no equality constraints) is

$L(x, y) = c^\top x + y^\top(b - Ax) = b^\top y + (c - A^\top y)^\top x.$

Minimizing over $x \ge 0$: if any component of $c - A^\top y$ is negative, the infimum is $-\infty$; otherwise the optimal $x = 0$ and $g(y) = b^\top y$. So

$\boxed{\;\max_{y \ge 0}\; b^\top y \quad \text{s.t.}\; A^\top y \le c.\;}$

That's the dual LP. Slater holds whenever both are feasible, so $d^\star = p^\star$ — exactly. The simplex method exploits this: it walks both primal and dual at once and stops when complementary slackness holds.

Four places duality shows up that aren't obviously about optimization:

• Support Vector Machines. The SVM dual is the famous one — its number of variables equals the number of training points, not the feature dimension. Sparsity falls out: only support vectors have $\lambda_i > 0$.
• Max-flow / min-cut. Min-cut is the LP dual of max-flow. Strong duality gives you the celebrated equality $\text{max flow} = \text{min cut}$.
• Sensitivity analysis. The optimal multiplier $\lambda_i^\star$ is the shadow price of constraint $i$: how much $p^\star$ improves per unit relaxation of $b_i$. Economists, traders, and scheduling engineers live in this column.
• Interior-point methods. Modern solvers (Mosek, Gurobi, CVXPY backends) solve the KKT system itself — they march primal and dual variables together, terminating when the duality gap drops below a tolerance.

Duality is the optimization world's most overpowered theorem because it turns one problem into two views of the same problem — and you can pick whichever is easier to solve.