Week 2: Lagrangian Duality in Depth

The Lagrangian#

Consider the primal problem in standard form:

The Lagrangian $\mathcal{L}: \mathbb{R}^d \times \mathbb{R}^m \times \mathbb{R}_+^p \to \mathbb{R}$ folds the constraints into the objective via multipliers:

$\mathcal{L}(x, \lambda, \nu) = f(x) + \sum_{i=1}^m \nu_i g_i(x) + \sum_{j=1}^p \lambda_j h_j(x)$

where $\nu_i \in \mathbb{R}$ (unrestricted — equality constraints) and $\lambda_j \geq 0$ (inequality constraints). The sign convention matters: we write the primal with $h_j(x) \leq 0$, and the Lagrangian adds $\lambda_j h_j(x)$ with $\lambda_j \geq 0$. If your primal uses $h_j(x) \geq 0$, the term becomes $-\lambda_j h_j(x)$.

Why this form? For a fixed $x$ that is feasible:

• Since $g_i(x) = 0$, the $\nu_i g_i(x)$ terms vanish regardless of $\nu_i$.
• Since $h_j(x) \leq 0$ and $\lambda_j \geq 0$, we have $\lambda_j h_j(x) \leq 0$. Thus

$\mathcal{L}(x, \lambda, \nu) \leq f(x)$

for any $\lambda \geq 0$ and any $\nu$. The Lagrangian is a lower bound on the objective at every feasible point. Maximising this lower bound over the multipliers gives the tightest possible bound — this is the dual problem.

Worked example — Simple QP with one inequality:

$\min_x \; \tfrac{1}{2}x^2 \quad \text{s.t.} \quad x - 1 \geq 0$

Rewrite as $1 - x \leq 0$ to match the standard form $h(x) \leq 0$. The Lagrangian is

$\mathcal{L}(x, \lambda) = \tfrac{1}{2}x^2 + \lambda(1 - x), \quad \lambda \geq 0$

For a fixed $\lambda$, the Lagrangian is a quadratic in $x$: $\tfrac{1}{2}x^2 - \lambda x + \lambda$. Its unconstrained minimum over $x$ is attained at $x = \lambda$ (set derivative $x - \lambda = 0$).

Dual function#

The dual function $g: \mathbb{R}_+^p \times \mathbb{R}^m \to \mathbb{R} \cup \{-\infty\}$ is defined as the pointwise infimum of the Lagrangian over the primal variable:

$g(\lambda, \nu) = \inf_{x} \mathcal{L}(x, \lambda, \nu) = \inf_x \left[ f(x) + \sum_i \nu_i g_i(x) + \sum_j \lambda_j h_j(x) \right]$

The domain of $g$ is $\{ (\lambda, \nu) \mid \lambda \geq 0,\; g(\lambda, \nu) > -\infty \}$. Outside this set, $g = -\infty$ and those dual variables are useless (they provide no lower bound).

Key property: $g$ is always concave, regardless of whether the primal problem is convex. Why? $g$ is a pointwise infimum of affine functions in $(\lambda, \nu)$ — specifically, for each fixed $x$, $\mathcal{L}(x, \cdot, \cdot)$ is affine in $(\lambda, \nu)$. The infimum of a family of affine functions is concave. This means the dual problem — maximising $g$ — is always a convex optimisation problem (maximise a concave function over a convex set). Even when the primal is nonconvex, the dual is well-behaved.

Continuing the QP example:

$g(\lambda) = \inf_x \left[ \tfrac{1}{2}x^2 + \lambda(1 - x) \right] = \inf_x \left[ \tfrac{1}{2}x^2 - \lambda x + \lambda \right]$

The minimiser is $x^*(\lambda) = \lambda$. Plugging in:

$g(\lambda) = \tfrac{1}{2}\lambda^2 - \lambda^2 + \lambda = -\tfrac{1}{2}\lambda^2 + \lambda$

The dual problem is $\max_{\lambda \geq 0} g(\lambda)$. Since $g$ is a concave quadratic, maximising: $g'(\lambda) = -\lambda + 1 = 0 \Rightarrow \lambda^* = 1$, and $g(1) = -\tfrac{1}{2} + 1 = \tfrac{1}{2}$.

The primal optimum: the constraint $x \geq 1$ is active at the minimum, so $x^* = 1$ and $f(1) = \tfrac{1}{2}$. Primal and dual optimal values agree: $f(x^*) = g(\lambda^*) = \tfrac{1}{2}$.

Weak duality#

Theorem (Weak Duality). For any primal feasible $x$ and any dual feasible $(\lambda, \nu)$ with $\lambda \geq 0$,

$g(\lambda, \nu) \leq f(x)$

Proof. $g(\lambda, \nu) = \inf_z \mathcal{L}(z, \lambda, \nu) \leq \mathcal{L}(x, \lambda, \nu) = f(x) + \sum_i \nu_i g_i(x) + \sum_j \lambda_j h_j(x)$

Since $g_i(x) = 0$ and $\lambda_j h_j(x) \leq 0$, the last two sums are $\leq 0$, so $\mathcal{L}(x, \lambda, \nu) \leq f(x)$. $\square$

Consequence: The optimal value of the dual, $d^* = \sup_{\lambda \geq 0, \nu} g(\lambda, \nu)$, is always a lower bound on the optimal value of the primal, $p^* = \inf_{x \in \mathcal{F}} f(x)$. That is,

$d^* \leq p^*$

The difference $p^* - d^* \geq 0$ is the duality gap. A zero gap means the dual provides a perfect certificate of optimality.

Weak duality always holds — no convexity, no constraint qualifications needed. This is why the dual is useful even for nonconvex problems: it gives a guaranteed lower bound (a "dual bound") that you can compute by solving a concave maximisation problem.

Strong duality and Slater#

Strong duality means $d^* = p^*$ — the duality gap is zero. This does not hold in general. For convex problems, Slater's condition provides a sufficient (and often easy-to-check) criterion.

Theorem (Slater's Condition). Consider a convex primal problem where $f$ and all $h_j$ are convex, and all $g_i$ are affine. If there exists a strictly feasible point — i.e., an $x$ with

$g_i(x) = 0,\quad h_j(x) < 0 \;\; \forall j$

(affine inequalities may be non-strict) — then strong duality holds: $d^* = p^*$, and the dual optimum is attained if $p^* > -\infty$.

Intuition. Slater says: if the feasible set has a non-empty interior relative to the affine equality constraints, then the dual captures the primal exactly. The strictly feasible point prevents the feasible set from "collapsing" to a lower-dimensional manifold where the dual could be weaker (recall the $x^2 \leq 0$ example from Week 1 where the constraint gradient vanished).

Refined Slater. If some $h_j$ are affine, strict feasibility is required only for the non-affine inequalities. Affine inequalities only need $h_j(x) \leq 0$.

When Slater fails but strong duality still holds. Slater is sufficient, not necessary. Many convex problems have zero duality gap without a strictly feasible point (e.g., semidefinite programs can have strong duality under subtler conditions). But Slater is the go-to check because it is simple and covers most practical convex programs.

Worked example — Quadratic with two inequalities:

$\min_x \; x^2 \quad \text{s.t.} \quad x \geq 1,\; x \leq 3$

In standard form: $h_1(x) = 1 - x \leq 0$, $h_2(x) = x - 3 \leq 0$. This is convex (quadratic objective, linear constraints). A strictly feasible point exists: $x = 2$ gives $h_1(2) = -1 < 0$, $h_2(2) = -1 < 0$. Slater holds, so strong duality applies. The primal optimum is $x^* = 1$ with $p^* = 1$.

Recovering primals#

When strong duality holds and both primal and dual optima are attained, the primal optimal $x^*$ is a minimiser of $\mathcal{L}(x, \lambda^*, \nu^*)$:

$x^* \in \arg\min_x \mathcal{L}(x, \lambda^*, \nu^*)$

If the Lagrangian is strictly convex in $x$ (e.g., a strictly convex $f$ plus affine constraints), this minimiser is unique and directly recoverable from the dual solution. This is the mechanism behind dual-based algorithms and kernel methods in ML (e.g., the SVM dual, where solving the dual in $\alpha$ is cheaper than solving the primal in $w$).

In the QP example above: $\lambda^* = 1$, the Lagrangian $\tfrac{1}{2}x^2 + (1 - x)$ is minimised at $x = \lambda^* = 1$, which recovers the primal optimum.

Knowledge Check#

Browser lab#

Consider the 1D problem $\min_x \; x^2$ subject to $x \geq 1$. Form the dual function $g(\lambda) = \inf_x [x^2 + \lambda(1 - x)]$, compute it analytically as $g(\lambda) = \lambda - \lambda^2/4$, and verify that $\max_{\lambda \geq 0} g(\lambda) = 1$ equals the primal optimal value.

import numpy as np
import matplotlib.pyplot as plt

def dual_func(lam):
    """g(lambda) = inf_x [x^2 + lambda*(1 - x)]
       Analytic: g(lambda) = lambda - lambda**2 / 4 for lambda >= 0"""
    return np.where(lam >= 0, lam - lam**2 / 4, -np.inf)

# Grid for dual variable
lams = np.linspace(0, 3, 200)
g_vals = dual_func(lams)

# Find the maximum analytically: g'(lambda) = 1 - lambda/2 = 0 => lambda* = 2
lam_star = 2.0
g_star = dual_func(lam_star)

fig, ax = plt.subplots(figsize=(7, 4.5))
ax.plot(lams, g_vals, "b-", linewidth=2, label=r"$g(\lambda) = \lambda - \lambda^2/4$")
ax.axvline(lam_star, color="gray", linestyle="--", alpha=0.6, label=f"$\\lambda^* = {lam_star}$")
ax.axhline(g_star, color="red", linestyle="--", alpha=0.6, label=f"$d^* = {g_star:.4f}$")
ax.plot(lam_star, g_star, "ro", markersize=8)

ax.set_xlabel(r"$\lambda$ (dual variable)")
ax.set_ylabel(r"$g(\lambda)$")
ax.set_title("Dual function for $\\min x^2$ s.t. $x \\geq 1$")
ax.legend()
ax.grid(True, alpha=0.3)
plt.show()

# Verify manually with explicit infimum computation
def lagrangian(x, lam):
    return x**2 + lam * (1 - x)

check_lams = [0.0, 0.5, 1.0, 1.5, 2.0, 2.5]
print("lambda | argmin_x | g(lambda) [analytic] | g(lambda) [numerical]")
for lam in check_lams:
    # Numerical infimum: the Lagrangian is convex in x, minimize via derivative x = lam/2
    x_opt = lam / 2
    g_num = lagrangian(x_opt, lam)
    g_an = dual_func(lam)
    print(f"  {lam:.1f}   |   {x_opt:.3f}   |   {g_an:.4f}   |   {g_num:.4f}")

print(f"\nPrimal optimum: x* = 1, p* = {1.0}")
print(f"Dual optimum:   lam* = {lam_star}, d* = {g_star}")
print(f"Strong duality holds: p* = d* = {1.0}")

print("Notice: the numerical infimum of the Lagrangian matches the analytic dual at every λ, and p* = d* = 1.0 confirms strong duality here.")

Key takeaways#

• The Lagrangian folds constraints into the objective with multipliers: $\nu_i$ free for equalities, $\lambda_j \geq 0$ for inequalities. At any feasible point it lower-bounds the objective.
• The dual function $g(\lambda, \nu) = \inf_x \mathcal{L}(x, \lambda, \nu)$ is always concave — a pointwise infimum of affine functions — so the dual problem is always convex, even when the primal is not.
• Weak duality $g(\lambda, \nu) \leq f(x)$ always holds, so the duality gap $p^* - d^*$ is never negative.
• Strong duality (zero gap) holds for convex problems under Slater's condition: a strictly feasible point for the nonlinear inequalities.
• When the Lagrangian is strictly convex in $x$, the primal optimum is recovered from the dual solution — the mechanism behind dual-based algorithms and kernel methods.
• A zero gap is a certificate of optimality, and the dual variables carry the sensitivity information.

Further reading#

• Stephen Boyd & Lieven Vandenberghe, Convex Optimization (Cambridge University Press, 2004) — Chapter 5 is the definitive treatment of the Lagrangian dual, weak/strong duality, and Slater's condition.
• Dimitri P. Bertsekas, Nonlinear Programming (3rd ed., Athena Scientific, 2016) — duality theory with careful proofs.
• Yurii Nesterov, Lectures on Convex Optimization (2nd ed., Springer, 2018) — duality alongside the analytic view of convex structure.