The Lagrangian#
Consider the primal problem in standard form:
\min_x &\quad f(x) \\ \text{s.t.} &\quad g_i(x) = 0, \quad i = 1, \ldots, m \\ &\quad h_j(x) \leq 0, \quad j = 1, \ldots, p \end{aligned}$$ 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. <Exercise type="multiple-choice" question="Weak duality states that for any primal feasible $x$ and dual feasible $(\lambda, \nu)$:" options={["$g(\lambda, \\nu) \geq f(x)$", "$g(\lambda, \\nu) \leq f(x)$", "$g(\lambda, \\nu) = f(x)$", "$g(\lambda, \\nu) = 0$"]} correctIndex={1} explanation="Weak duality guarantees the dual value is a lower bound: $g(\lambda, \\nu) \leq f(x)$ for any feasible primal-dual pair." /> <Quiz questions={[ { type: "fill-blank", question: "The dual function is defined as $g(\lambda,\\nu) = \inf_x \mathcal{L}(x,\lambda,\\nu)$. It is always a ____ function of $(\lambda,\\nu)$.", correctAnswer: "concave", explanation: "The dual function is a pointwise infimum of affine functions, which is always concave. Maximising it is thus a convex optimisation problem." }, { type: "multiple-choice", question: "Weak duality guarantees $d^* \leq p^*$. When does strong duality ($d^* = p^*$) hold for a convex problem?", options: ["Always", "When Slater's condition holds", "Only for linear programs", "When the objective is quadratic"], correctIndex: 1, explanation: "Slater's condition (existence of a strictly feasible point) guarantees strong duality for convex problems. It is not always true — nonconvex problems may have a nonzero duality gap." }, { type: "multiple-choice", question: "Which of the following best describes Slater's condition?", options: ["All constraints are linear", "There exists a point strictly satisfying all nonlinear inequality constraints", "The gradients of active constraints are linearly independent", "The objective is strongly convex"], correctIndex: 1, explanation: "Slater requires a feasible point with $h_j(x) < 0$ for all nonlinear inequality constraints — a strictly interior (non-boundary) point." } ]} /> ## 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. ```python 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}") ```