Lemma 6 — convexity and attainment of the dual minimum
ProvedPandoraBO.Private20261023.dual_convex_and_attains_minimumbayesian-optimizationexpected-budgetgittins-indexpandoras-box
Fix and suppose some box has cost strictly below . Define
Then is convex on and attains its minimum there. The supremum ranges over the full measurable adaptive randomized policy class. No positivity of the minimizing multiplier is asserted here.
Preamble
import Definitions.Def_PandoraBO_Model set_option autoImplicit false
Formal statement
namespace PandoraBO.Private20261023
theorem dual_convex_and_attains_minimum {n : ℕ} (M : Instance n)
(B : ℝ) (hslater : ∃ i : Box n, M.cost i < B) :
(∀ x y a : ℝ, 0 ≤ x → 0 ≤ y → 0 ≤ a → a ≤ 1 →
dualValue M B (a * x + (1 - a) * y) ≤
a * dualValue M B x + (1 - a) * dualValue M B y) ∧
∃ multiplier : ℝ, dualMinimizer M B multiplier := by sorry
end PandoraBO.Private20261023
Source
Qian Xie, Raul Astudillo, Peter I. Frazier, Ziv Scully, and Alexander Terenin. [Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index](https://arxiv.org/abs/2406.20062). NeurIPS 2024. Appendix B.5, Lemma 6 and the definition of the Lagrangian envelope.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.