[proofplan]
We show that every dual objective value is dominated by every primal objective value. The argument is a single chain of inequalities: the dual function $g(\lambda)$ is defined as an infimum of the Lagrangian over $X$, so it is bounded above by evaluating the Lagrangian at any particular feasible $x$. When $x$ satisfies the constraint $h(x) = b$, the Lagrangian reduces to $f(x)$, giving $g(\lambda) \leq f(x)$. The global weak duality bound follows by taking the supremum over $\lambda$ and the infimum over feasible $x$.
[/proofplan]
[step:Bound the dual function by evaluating the Lagrangian at a feasible point]
Let $x \in X(b)$ be primal feasible and $\lambda \in Y$ be dual feasible. Recall the definitions of the Lagrangian and the dual function:
\begin{align*}
L(x', \lambda) &= f(x') - \lambda^\top(h(x') - b), \\
g(\lambda) &= \inf_{x' \in X} L(x', \lambda).
\end{align*}
Since $g(\lambda)$ is the infimum of $L(\cdot, \lambda)$ over $X$, and $x \in X(b) \subseteq X$, we have
\begin{align*}
g(\lambda) = \inf_{x' \in X} L(x', \lambda) \leq L(x, \lambda).
\end{align*}
[guided]
The dual function $g(\lambda) = \inf_{x' \in X} L(x', \lambda)$ is defined as the infimum of the Lagrangian over the entire constraint set $X$. The infimum over a set is a lower bound on every value in that set. Since $x \in X(b)$ and $X(b) = \{x \in X : h(x) = b\} \subseteq X$, the point $x$ belongs to $X$. Therefore evaluating the Lagrangian at $x$ yields a value at least as large as the infimum:
\begin{align*}
g(\lambda) = \inf_{x' \in X} L(x', \lambda) \leq L(x, \lambda).
\end{align*}
This step uses nothing about the structure of $f$, $h$, or $\lambda$ — only the definition of infimum.
[/guided]
[/step]
[step:Use primal feasibility $h(x) = b$ to collapse the Lagrangian to $f(x)$]
Since $x \in X(b)$, we have $h(x) = b$, so
\begin{align*}
L(x, \lambda) = f(x) - \lambda^\top(h(x) - b) = f(x) - \lambda^\top \cdot 0 = f(x).
\end{align*}
Combining with the previous inequality:
\begin{align*}
g(\lambda) \leq f(x).
\end{align*}
[guided]
Why does the Lagrangian simplify so cleanly? The Lagrangian penalises constraint violation through the term $-\lambda^\top(h(x) - b)$. When $x$ is feasible, there is no constraint violation: $h(x) - b = 0$. The penalty vanishes regardless of the value of $\lambda$, and the Lagrangian reduces to the objective:
\begin{align*}
L(x, \lambda) = f(x) - \lambda^\top(h(x) - b) = f(x) - \lambda^\top \cdot 0 = f(x).
\end{align*}
This is the core mechanism of weak duality: the dual function, which searches over all $x' \in X$ (including infeasible points where the penalty may help), can never exceed the objective at a feasible point where the penalty is zero. Combined with the bound from the previous step:
\begin{align*}
g(\lambda) \leq L(x, \lambda) = f(x).
\end{align*}
[/guided]
[/step]
[step:Take the supremum over $\lambda$ and infimum over $x$ to obtain the global bound]
Since $g(\lambda) \leq f(x)$ holds for every $\lambda \in Y$ and every $x \in X(b)$, the inequality is preserved under taking the supremum on the left and infimum on the right:
\begin{align*}
\sup_{\lambda \in Y} g(\lambda) \leq \inf_{x \in X(b)} f(x).
\end{align*}
This is weak duality: the optimal dual value never exceeds the optimal primal value.
[guided]
The pointwise inequality $g(\lambda) \leq f(x)$ holds for every pair $(\lambda, x) \in Y \times X(b)$. We now pass to extrema. Fix any $\lambda \in Y$. The inequality $g(\lambda) \leq f(x)$ holds for all $x \in X(b)$, so $g(\lambda)$ is a lower bound on the set $\{f(x) : x \in X(b)\}$. Therefore $g(\lambda) \leq \inf_{x \in X(b)} f(x)$. Since this holds for every $\lambda \in Y$, the quantity $\inf_{x \in X(b)} f(x)$ is an upper bound on the set $\{g(\lambda) : \lambda \in Y\}$. Therefore:
\begin{align*}
\sup_{\lambda \in Y} g(\lambda) \leq \inf_{x \in X(b)} f(x).
\end{align*}
The gap $\inf_{x \in X(b)} f(x) - \sup_{\lambda \in Y} g(\lambda) \geq 0$ is the **duality gap**. Weak duality asserts it is non-negative; strong duality (when it holds) asserts it is zero.
[/guided]
[/step]
