Global sensitivity inequality
ProvedConvexOptimization.global_sensitivityThe global sensitivity inequality — bound (5.57) of Boyd & Vandenberghe: optimal dual variables price the constraints.
Consider the standard problem and its perturbed version, in which the constraints are relaxed or tightened by and :
Let be feasible for the unperturbed problem and let , satisfy the zero-gap condition . Then every feasible for the -perturbed problem satisfies
Writing for the perturbed optimal value, this is : the multipliers bound how much can be gained by loosening a constraint. Loosening the -th inequality by cannot reduce the optimal value by more than , so a large multiplier marks a constraint that is expensive to violate and a zero multiplier marks one that is locally free. Unlike the differential reading of shadow prices, the bound is global — valid for every perturbation, however large.
Formalization Note The statement quantifies over an arbitrary point feasible for the perturbed constraints rather than over the perturbed optimal value, which avoids assuming that optimal value exists; the zero-gap hypothesis is an equality of the EReal-valued dual function with the coercion of . Source: B&V §5.6.1, p. 250, eq. (5.57).
import Mathlib import Definitions.Def_ConvexOptimization_lagrangeDuality open scoped RealInnerProductSpace ENNReal open MeasureTheory
theorem ConvexOptimization.global_sensitivity {n mm p : ℕ}
(f₀ : EuclideanSpace ℝ (Fin n) → ℝ)
(fc : Fin mm → EuclideanSpace ℝ (Fin n) → ℝ)
(a : Fin p → EuclideanSpace ℝ (Fin n)) (b : Fin p → ℝ)
(xs : EuclideanSpace ℝ (Fin n)) (hxs : xs ∈ feasibleSet fc a b)
(lam : Fin mm → ℝ) (hlam : ∀ i, 0 ≤ lam i) (nu : Fin p → ℝ)
(hzero : dualFunction f₀ fc a b lam nu = (f₀ xs : EReal))
(u : Fin mm → ℝ) (v : Fin p → ℝ) (x : EuclideanSpace ℝ (Fin n))
(hx_ineq : ∀ i, fc i x ≤ u i) (hx_eq : ∀ j, ⟪a j, x⟫ = b j + v j) :
f₀ xs - ∑ i, lam i * u i - ∑ j, nu j * v j ≤ f₀ x := by
sorry