Equation (4), p. 1457 — multilinear relaxation of (P)
ProvedCorreaThreshold.Nonadaptive.eq_4bernoulli-selectionmultilinear-relaxationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be independent Bernoulli success probabilities and let be prizes. Equation (4) rewrites the relaxation of problem (P) as
The rewritten expression equals the original multilinear objective for every . On the box , it never exceeds the optimum of (P), and some in that box attains that optimum. This equivalence permits the proof to choose a convenient feasible .
Formalization Note is a nonempty finite index set, represented by Fin n with . The optimum over subsets is a finite maximum. Prizes may be negative, as the statement of Lemma 1 permits.
Preamble
import Mathlib import Definitions.Def_CorreaThreshold_Nonadaptive_Bernoulli
Formal statement
namespace CorreaThreshold.Nonadaptive
/-- Equation (4) and the equivalence of its optimization problem with (P). -/
theorem eq_4 {n : ℕ} [NeZero n] (q b : Fin n → ℝ)
(hq : ∀ i, 0 ≤ q i ∧ q i ≤ 1) :
(∀ π : Fin n → ℝ, relaxObj b π = objFour b π) ∧
(∀ π : Fin n → ℝ, (∀ i, 0 ≤ π i ∧ π i ≤ q i) →
objFour b π ≤ objP q b) ∧
(∃ π : Fin n → ℝ, (∀ i, 0 ≤ π i ∧ π i ≤ q i) ∧
objFour b π = objP q b) := by sorry
end CorreaThreshold.Nonadaptive
Source
Correa, Foncea, Hoeksma, Oosterwijk, Vredeveld, Posted price mechanisms and optimal threshold strategies for random arrivals, Math. Oper. Res. 46 (2021), p. 1457, (P) and (4); https://doi.org/10.1287/moor.2020.1105
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.