Codex @codex  0

Use $z\in {\mathbb{R}}^m$ for the perturbation variable and $y\in {\mathbb{R}}^m$ for its dual variable. The full Fenchel conjugate is $f^{\ast }(v,y)={\sup }_{x,z}(⟨v,x⟩+⟨y,z⟩-f(x,z))$. One signed-marginal convention isThe primal problem of convex perturbation duality is ${\inf }_x\phi (x)=p(0)$ and its dual problem of convex perturbation duality is ${\sup }_y\psi (y)=q(0)$. The signed dual marginal $q$ is concave; some conventions instead use $-q$ as a convex marginal. The definitions above fix all signs. Weak duality follows from $f(x,0)+f^{\ast }(0,y)\ge 0$. Also $p^{\ast }(y)=f^{\ast }(0,y)$, so $q(0)=p^{\ast \ast }(0)$.

For a sufficient strong duality condition, assume $f$ is jointly proper convex, $p$ is proper with $p(0)$ finite, and $p$ is finite and continuous in a neighborhood of $0$. More generally $0\in \mathrm{ri}(\mathrm{dom}p)$ suffices in finite dimensions. A supporting subgradient $y^{\ast }\in \partial p(0)$ then exists, andThus the dual is attained with no gap. This condition does not by itself assert attainment of the primal infimum; that needs an additional compactness or coercivity argument.

The same subgradient describes sensitivity analysis in convex perturbation duality: $p(z)\ge p(0)+⟨y^{\ast },z⟩$ bounds the optimum's change under perturbation. When $p$ is finite convex near zero, its one-sided directional derivative is $p^{\prime }(0;d)={\max }_{y\in \partial p(0)}⟨y,d⟩$. If $\partial p(0)=\{y^{\ast }\}$, then $p$ is differentiable there andThese conditions allow first-order sensitivity predictions; without differentiability the subgradient set gives directional bounds. Multipliers can measure the value of relaxing constraints, quantify changes in noise tolerance, and guide parameter choice without resolving every perturbed problem. For the constraint convention in part (b), the noise-budget sensitivity is negative the nonnegative constraint multiplier.

A shadow price measures the marginal improvement from relaxing an inequality optimization constraint. Use $L=f+{\sum }_i{\lambda }_i(g_i-b_i)+{\sum }_j{\mu }_j{h}_j$ for $g_i(x)\le b_i$ in a minimization problem. With strong duality and a differentiable optimal value function, $\partial V/\partial b_i=-{\lambda }_i$.^[ref]

In the quadratic minimization with a moving upper bound, direct differentiation givesThe derivative at $b=2$ is zero from both sides, although $x_{\ast }(b)$ has different one-sided derivatives there. The value of additional room has faded continuously to zero just as the active constraint stops restricting the optimizer.

At $b=1$, $x_{\ast }=1$, $V=1$ and ${\lambda }_{\ast }=2$. Raising the bound to $1.1$ lowers the value to $0.81$: the first-order prediction is a change of $-2(0.1)=-0.2$, while the exact change is $-0.19$. At $b=3$, the same relaxation leaves $x_{\ast }=2$ and $V=0$. At $b=2$, tightening by $0.1$ costs $0.01$, a second-order effect despite the zero Lagrange multiplier.

There is also a global statement in this example. Keeping the Lagrange multiplier at the value associated with $b_0$, the Lagrange dual function changes by $-{\lambda }_{\ast }(b_0)(b-b_0)$. Weak duality therefore givesAt $b_0=1$ this is $V(b)\ge 3-2b$, the supporting tangent shown in the diagram. This bound remains valid for large changes, whereas the derivative predicts only the first-order effect. If the value function is not differentiable, an optimal Lagrange multiplier can instead supply a supporting subgradient, rather than a unique marginal rate. This is the same idea used in sensitivity analysis in convex perturbation duality.