Proof of Theorem 1, pp. 38–39 — f(γ), the optimal value of the dual (16), is quasiconvex on [γmin, γmax]^n with values in [0, 1]
ProvedProviderGuarantee.Bound.dualValue_quasiconvexOnlinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1provider-guaranteesquasiconvexity
Let and let be the optimal value of the dual problem (15), equivalently (16), of p. 38. Then maps the box into , and is quasiconvex on it: for every the sublevel set
is convex.
The page argues that each term of the objective of (16) is quasiconvex jointly in , that its feasible region is convex in , and that minimizing over preserves quasiconvexity. Quasiconvexity is what reduces the maximization of over the box to its vertices.
Formalization Note is dualValue, and quasiconvexity is Mathlib's QuasiconvexOn (convex sublevel sets) on the box Set.Icc (fun _ => γmin) (fun _ => γmax).
Differences from the source:
- encoding: f(γ) is the optimal value of problem (16) → dualValue γ, the infimum of s over the feasible (s, λ) of (15); reason: (16) is (15) with s eliminated (p. 38: 'Problem (15) in turn can be rewritten as'); dividing the first two families of constraints of (15) by γ_i, γ_k > 0 gives the max in (16), so the values coincide
- encoding: 'f(γ) : [γmin, γmax]^n → [0, 1]' and 'f(γ) must be quasiconvex in γ' → 0 ≤ dualValue γ ≤ 1 on the box, and QuasiconvexOn ℝ (box) dualValue; reason: Mathlib's quasiconvexity is convexity of every sublevel set, the standard definition
Preamble
import Mathlib import Definitions.Def_ProviderGuarantee_Bound_Model
Formal statement
namespace ProviderGuarantee.Bound
theorem dualValue_quasiconvexOn {n : ℕ} (γmin γmax : ℝ) (hγmin : 0 < γmin) (hγ : γmin ≤ γmax) :
QuasiconvexOn ℝ (Set.Icc (fun _ : Fin n => γmin) (fun _ => γmax)) dualValue ∧
∀ γ ∈ Set.Icc (fun _ : Fin n => γmin) (fun _ => γmax),
0 ≤ dualValue γ ∧ dualValue γ ≤ 1 := by sorry
end ProviderGuarantee.Bound
Source
Gur, Iancu & Warnes, Value Loss in Allocation Systems with Provider Guarantees, SSRN 3351509 (version of March 24, 2020), pp. 38–39, proof of Theorem 1, (16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.