Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Convexity and minimum attainment of a finite-valued affine dual envelope

Proved
PandoraBO.Private20261023.abstract_dual_convex_and_attains

by QianJaneXie · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-analysisexpected-budgetpandoras-box

Let a family of alternatives have real rewards R and real costs C. Suppose the penalized rewards R(i)−tC(i) are bounded above for every real multiplier t, and some alternative has cost strictly below B. Then the dual envelope D(t)=sup_i(R(i)−tC(i))+tB is convex on the real line and attains a minimum on the nonnegative half-line. No maximizing alternative is assumed to exist. This isolates the real-analysis argument used for the budgeted Pandora dual problem.

Preamble
import Definitions.Def_PandoraBO_Model
import Mathlib.Topology.Semicontinuity.Basic
import Mathlib.Topology.Order.Compact

set_option autoImplicit false
Formal statement
theorem PandoraBO.Private20261023.abstract_dual_convex_and_attains {ι : Type*} (R C : ι → ℝ) (B : ℝ)
    (hbounded : ∀ t : ℝ, BddAbove (Set.range (fun i => R i - t * C i)))
    (hstrict : ∃ i : ι, C i < B) :
    (∀ x y a : ℝ, 0 ≤ a → a ≤ 1 →
      sSup (Set.range (fun i => R i - (a * x + (1 - a) * y) * C i)) +
          (a * x + (1 - a) * y) * B ≤
        a * (sSup (Set.range (fun i => R i - x * C i)) + x * B) +
        (1 - a) * (sSup (Set.range (fun i => R i - y * C i)) + y * B)) ∧
    ∃ t : ℝ, 0 ≤ t ∧ ∀ u : ℝ, 0 ≤ u →
      sSup (Set.range (fun i => R i - t * C i)) + t * B ≤
        sSup (Set.range (fun i => R i - u * C i)) + u * B := by sorry
Source
Abstract form of the dual-envelope argument in Xie et al., Cost-aware Bayesian Optimization via the Pandora’s Box Gittins Index, author revised manuscript reviewed 23 October 2026, Appendix B.5, Lemma 6, equations (38)–(39). This reusable generalization is derived for the formalization, rather than quoted verbatim.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me