Appendix II: three value functions are concave
ProvedQAlgorithms.Papers.Independent.Gap48.P46.section_value_concavityLet be a nonempty compact convex subset of a finite-dimensional real normed vector space, continuous and concave, and a real linear functional. For each relation among , , , let . Then the three value functions
are concave on their respective domains , and all maxima there are attained. This is full concavity, with no optimized value asserted on empty sections.
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P46
noncomputable section
namespace QAlgorithms.Papers.Independent.Gap48.P46
open scoped Matrix ComplexConjugate ENNReal ComplexOrder
open Filter
attribute [local instance] Classical.propDecidable
attribute [local instance] Classical.decEq
open QAlgorithms.Papers.Independent.Information100.P62 (tensorChannel)
open QAlgorithms.Papers.Independent.Information100.P54 (relativeEntropyBits)
open QAlgorithms.Papers.Independent.Dependency50.P23 (IsEB)
open QAlgorithms.Papers.Independent.Information100.P08
(Ensemble ensembleAverage outputHolevo mixedRoof)
variable {I O J K : Type} [Fintype I] [Fintype O] [Fintype J] [Fintype K]
variable [DecidableEq I] [DecidableEq O] [DecidableEq J] [DecidableEq K]
/-- PDF p.17, Appendix II: all three value functions are concave on their
nonempty-section domains, and every value in each domain is attained. -/
theorem section_value_concavity {V : Type*} [NormedAddCommGroup V] [NormedSpace ℝ V]
[FiniteDimensional ℝ V] (S : Set V) (hS : S.Nonempty) (hcompact : IsCompact S)
(hconvex : Convex ℝ S) (F : V → ℝ) (hcontinuous : ContinuousOn F S)
(hconcave : ConcaveOn ℝ S F) (l : V →ₗ[ℝ] ℝ) :
ConcaveOn ℝ (sectionDomain S l (· = ·)) (sectionValue S F l (· = ·)) ∧
ConcaveOn ℝ (sectionDomain S l (· ≤ ·)) (sectionValue S F l (· ≤ ·)) ∧
ConcaveOn ℝ (sectionDomain S l (· ≥ ·)) (sectionValue S F l (· ≥ ·)) ∧
(∀ rel : ℝ → ℝ → Prop, rel = (· = ·) ∨ rel = (· ≤ ·) ∨ rel = (· ≥ ·) →
∀ alpha ∈ sectionDomain S l rel,
MaximizesValue (sectionSet S l rel alpha) F (sectionValue S F l rel alpha)) := by sorry
end QAlgorithms.Papers.Independent.Gap48.P46
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be a finite-dimensional normed real vector space, let be nonempty, compact, and convex, let be continuous on and concave on , and let be real linear. For any relation on real numbers, define , , and . Then each of , , and is concave on its respective domain , , and . Furthermore, for every relation that is exactly equality, exactly , or exactly , and every , the value is the greatest element of ; thus some point in that section attains it. These assertions include zero-dimensional and singleton sections.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.