Chapter 07 — Optimization in Relative Scale

Proofs omitted. Hover over highlighted terms to see their Lean types.

Algorithm 7.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.1: a projected normalized subgradient run over an owner first-order convex minimization problem, together with a radius parameter R, a certificate that the owner simple-set method uses the constant stepsize R / √(N + 1) on the finite horizon 0, ..., N, and a chosen output index attaining the minimum sampled objective value among x₀, ..., x_N. The feasible set, objective, canonical projection, and oracle-selected subgradients are inherited from the owner problem/method rather than stored again as primitive data. Positivity of R is kept as theorem-level data, not as a field of the run.

variable {n N : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
structure ProjectedNormalizedSubgradientMethod (n N : ℕ) where
  /-- The owner first-order convex minimization problem. -/
  problem : FirstOrderConvexMinimizationProblem (EuclideanSpace ℝ (Fin n))
  /-- The owner simple-set subgradient run. -/
  run : SimpleSetSubgradientMethod problem
  /-- The radius parameter `R`. -/
  radius : ℝ
  /-- On the finite horizon `0, ..., N`, the owner stepsizes are constantly
  `R / √(N + 1)`. -/
  constant_stepsize :
    ∀ i : Fin (N + 1), run.stepsize i = radius / Real.sqrt (N + 1 : ℝ)
  /-- A chosen sampled minimizer index among `x₀, ..., x_N`. -/
  bestIndex : Fin (N + 1)
  /-- The chosen index attains the minimum sampled objective value. -/
  bestIndex_is_argmin :
    ∀ i : Fin (N + 1), problem.objective (run bestIndex) ≤ problem.objective (run i)

Definition 7.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.1: a value fBar has relative accuracy delta with respect to a positive optimal value fStar when it lies between fStar and (1 + delta) * fStar. The nonnegativity of delta is then forced by these bounds together with 0 < fStar.

universe u variable {α : Type u} [Semiring α] [Preorder α] def IsRelativeAccuracy (fStar delta fBar : α) : Prop := 0 < fStar ∧ fStar ≤ fBar ∧ fBar ≤ (1 + delta) * fStar

Lemma 7.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.1: if the family a has full row rank, encoded by Submodule.span ℝ (Set.range a) = ⊤, has at least two elements, and satisfies ∑ i, a i = 0, then the canonical pullback seminorm x ↦ (∑ i ⟪aᵢ, x⟫²)^(1/2) is a norm and the subdifferential at 0 of the Chapter 3 support function x ↦ (ξ[Set.range a] x).toReal satisfies the asphericity condition with γ₁ = 1 and γ₀ = 1 / √(m (m - 1)).

open scoped BigOperators open scoped SupportFunction universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable {m : ℕ} variable (a : Fin m → E) theorem supportFunction_range_toReal_norm_and_asphericity (hm : 2 ≤ m) (hfull_row_rank : Submodule.span ℝ (Set.range a) = ⊤) (hzero_sum : ∑ i : Fin m, a i = 0) : let p : Seminorm ℝ E := Seminorm.comp (normSeminorm ℝ (EuclideanSpace ℝ (Fin m))) (((EuclideanSpace.equiv (Fin m) ℝ).symm.toLinearMap).comp (LinearMap.pi fun i ↦ (innerSL ℝ (a i)).toLinearMap)) Seminorm.IsNorm p ∧ SatisfiesAsphericityCondition (fun x ↦ (ξ[Set.range a] x).toReal) p (1 / Real.sqrt ((m : ℝ) * (m - 1 : ℝ))) 1

Proposition 7.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.1: for a conic unconstrained minimization problem, the optimal value min_{x ∈ Q₁} f(x) is attained at a feasible point and that attained value is strictly positive.

open scoped WithTopConvexAnalysis universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable [ProperSpace E] theorem positive_homogeneous_convex_minimizer_exists_and_pos (problem : ConicUnconstrainedMinimizationProblem E) : ∃ x ∈ problem.feasibleSet, IsMinOn problem problem.feasibleSet x ∧ 0 < problem x

Theorem 7.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.1 (4): specializing the global convex-set setup of problem (7.1.1), the Euclidean norm case sharpens the source distance estimate (7.1.10) to the factor-1 / γ₀ comparison chain.

universe u v variable {E : Type u} [NormedAddCommGroup E] variable {f : E → ℝ} {γ₀ γ₁ : ℝ} theorem SatisfiesAsphericityCondition.optimal_solution_distance_of_inner_product [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] (h_asphericity : SatisfiesAsphericityCondition f (normSeminorm ℝ E) γ₀ γ₁) (hf_convex : ConvexOn ℝ Set.univ f) (hf_hom : IsPositivelyHomogeneousOn 1 Set.univ f) {Q₁ : Set E} {x₀ xStar : E} (hQ₁_convex : Convex ℝ Q₁) (hx₀_mem : x₀ ∈ Q₁) (hx₀_min : IsMinOn (fun x ↦ ‖x‖) Q₁ x₀) (hxStar_mem : xStar ∈ Q₁) (hxStar_min : IsMinOn f Q₁ xStar) : List.IsChain (· ≤ ·) [‖x₀ - xStar‖, (1 / γ₀) * f xStar, (1 / γ₀) * f x₀]

Algorithm 7.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.2 terminates when some stage satisfies the stopping criterion f(\hat x_{t+1}) ≥ (1 / √e) f(\hat x_t).

universe u open scoped RelativeScaleSubgradientApproximationNotation def relativeScaleSubgradientApproximationTerminates {X : Type u} (G : ℕ → ℝ → X) (f : X → ℝ) (x0 : X) (δ α γ0 : ℝ) : Prop := ∃ t : ℕ, relativeScaleSubgradientApproximationStoppingCriterion G f x0 δ α γ0 t

Definition 7.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.2: the textbook norm ball B_{‖·‖}(r) centered at the origin is exactly the canonical metric closed ball Metric.closedBall (0 : E) r.

universe u variable {E : Type u} [SeminormedAddGroup E] variable (r : ℝ) (a : E) #check (Metric.closedBall (0 : E) r : Set E)

Lemma 7.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.2: if Q₂ contains the p-ball of radius γ₀ and is contained in the p-ball of radius γ₁, then the real-valued support function of Aᵀ Q₂ = ∂f(0) is sandwiched between γ₀ and γ₁ times the pulled-back dual norm x ↦ ‖A x‖_*. The pointwise sandwich only needs the inner radius to be explicitly nonnegative; the outer-radius nonnegativity follows from the two ball inclusions. The stronger positivity hypotheses needed for the ratio γ₀ / γ₁ are kept separate in gammaRatio_pos_and_le_one.

open scoped Pointwise SupportFunction universe u v variable {X : Type v} [AddCommGroup X] [Module ℝ X] variable {F : Type u} [NormedAddCommGroup F] [InnerProductSpace ℝ F] variable [FiniteDimensional ℝ F] theorem supportFunction_toReal_comp_linearMap_dualNorm_bounds (A : X →ₗ[ℝ] F) (Q2 : Set F) (p : Seminorm ℝ F) [Seminorm.IsNorm p] (γ₀ γ₁ : ℝ) (hγ₀_nonneg : 0 ≤ γ₀) (hQ2_lower : p.closedBall 0 γ₀ ⊆ Q2) (hQ2_upper : Q2 ⊆ p.closedBall 0 γ₁) (x : X) : γ₀ * p.dualNorm (A x) ≤ (ξ[Q2] (A x)).toReal ∧ (ξ[Q2] (A x)).toReal ≤ γ₁ * p.dualNorm (A x)

Proposition 7.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.2 [Chapter7_1.json:26]: if f is convex on ℝⁿ, R is positive, and the Chapter 7 direct-structure method S_N(R) satisfies the source intermediate estimate f (S_N(R)) - f(x*) ≤ (2 γ₁(F) / √(N (N + 1))) ‖x₀ - x*‖ for every start point x₀ with ‖x₀ - x*‖ ≤ R, where the source complexity coefficient γ₁(F) is nonnegative, and a chosen global minimizer x* of f, then for every such x₀ its output also satisfies the displayed bound 2 γ₁(F) R / √(N (N + 1)).

variable {n : ℕ} local notation "Eₙ" => EuclideanSpace ℝ (Fin n) theorem direct_structure_method_output_sub_optimalValue_le (f : Eₙ → ℝ) (S : ℕ+ → ℝ → Eₙ → Eₙ) (γ₁ : ℝ) (N : ℕ+) (R : ℝ) (xStar : Eₙ) (hf_convex : ConvexOn ℝ Set.univ f) (hR_pos : 0 < R) (hγ₁_nonneg : 0 ≤ γ₁) (hxStar : IsMinOn f Set.univ xStar) (h_method : ∀ {x₀ : Eₙ}, ‖x₀ - xStar‖ ≤ R → f (S N R x₀) - f xStar ≤ (2 * γ₁ / Real.sqrt ((N : ℝ) * ((N : ℝ) + 1))) * ‖x₀ - xStar‖) : ∀ {x₀ : Eₙ}, ‖x₀ - xStar‖ ≤ R → f (S N R x₀) - f xStar ≤ (2 * γ₁ * R) / Real.sqrt ((N : ℝ) * ((N : ℝ) + 1))

Theorem 7.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.2 [Chapter7_1.json:15]: if α and δ are positive, fStar is nonnegative, and every iterate G k rhoHat satisfies the subgradient approximation estimate f (G k rhoHat) - fStar ≤ (1 / (α^2 * √(k + 1))) * fStar, then the iterate with index ⌊1 / (α^4 δ^2)⌋ satisfies f (G_N rhoHat) ≤ (1 + δ) fStar.

universe u variable {X : Type u} theorem subgradient_approximation_scheme_value_le_one_add_delta_mul_optimal_value (f : X → ℝ) (G : ℕ → ℝ → X) (rhoHat α δ fStar : ℝ) (hα : 0 < α) (hδ : 0 < δ) (hfStar_nonneg : 0 ≤ fStar) (hEstimate : ∀ k : ℕ, f (G k rhoHat) - fStar ≤ (1 / (α ^ (2 : ℕ) * Real.sqrt (k + 1 : ℝ))) * fStar) : f (G (Nat.floor (1 / (α ^ (4 : ℕ) * δ ^ (2 : ℕ)))) rhoHat) ≤ (1 + δ) * fStar

Algorithm 7.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.3 [Chapter7_2.json:24]: Method S_N(R) for the direct use of the support function uses a support-function problem problem with matrix A and support set Q₂, the localized feasible set Q₁(R) = boundedFeasibleSet problem.Q1 x₀ R, the radius parameter R, the input point x₀, and sequences x_k, v_k, and ν_k, with x₀ = v₀, and a positive horizon N ≥ 1, such that for every k = 0, …, N - 1 one has y_k = (k / (k + 2)) x_k + (2 / (k + 2)) v_k, the vector ν_k belongs to arg max_{u ∈ Q₂} {⟪A y_k, u⟫ - (μ / 2) ‖u‖²}, the point v_{k+1} belongs to arg min_{x ∈ Q₁(R)} {(1 / (2μ)) ‖x - x₀‖² + ⟪A x, ∑_{i=0}^k ((i + 1) / 2) ν_i⟫}, and x_{k+1} = (k / (k + 2)) x_k + (2 / (k + 2)) v_{k+1}, where μ = 2R / (γ₁(F) √(N (N + 1))) with the canonical Chapter 7 coefficient γ₁(F) = problem.supportBody.gammaOne.

open Matrix open scoped BigOperators ConstrainedArgmin variable {m n N : ℕ} local notation "Eₘ" => EuclideanSpace ℝ (Fin m) local notation "Eₙ" => EuclideanSpace ℝ (Fin n) structure SupportFunctionSmoothingMethod (m n N : ℕ) where /-- The support-function optimization problem supplying `A`, `Q₂`, and `Q₁`. -/ problem : SupportFunctionOptimizationProblem m n /-- The radius parameter `R` supplied to the method. -/ radius : ℝ /-- The input point `x₀`. -/ initialPoint : EuclideanSpace ℝ (Fin n) /-- The primal iterates `x₀, x₁, x₂, ...`. -/ x : ℕ → EuclideanSpace ℝ (Fin n) /-- The auxiliary proximal points `v₀, v₁, v₂, ...`. -/ v : ℕ → EuclideanSpace ℝ (Fin n) /-- The dual maximizers `ν₀, ν₁, ν₂, ...`. -/ nu : ℕ → EuclideanSpace ℝ (Fin m) /-- The initial iterate is the input point `x₀`. -/ x_zero : x 0 = initialPoint /-- The initial proximal point is the input point `x₀`. -/ v_zero : v 0 = initialPoint /-- The source method uses a positive iteration horizon `N ≥ 1`. -/ iteration_count_pos : 1 ≤ N /-- For each `k = 0, …, N - 1`, the chosen dual point `ν_k` maximizes the regularized dual objective over `Q₂` at the extrapolated point `y_k`. -/ nu_mem_argmax : ∀ k : ℕ, k < N → nu k ∈ smoothedPrimalObjectiveArgmax (supportFunctionSmoothingMap problem.A) problem.Q2 0 (quadraticDistanceTo (0 : EuclideanSpace ℝ (Fin m))) (supportFunctionSmoothingParameter radius problem.supportBody.gammaOne N) (acceleratedSchemeSearchPoint x v k) /-- For each `k = 0, …, N - 1`, the successor proximal point `v_{k+1}` minimizes the proximal primal objective over `Q₁(R)`. -/ v_succ_mem_argmin : ∀ k : ℕ, k < N → v (k + 1) ∈ argmin[boundedFeasibleSet problem.Q1 initialPoint radius] (supportFunctionSmoothingPrimalMinimand problem.A (supportFunctionSmoothingParameter radius problem.supportBody.gammaOne N) initialPoint nu k) /-- For each `k = 0, …, N - 1`, the successor iterate is the convex combination `x_{k+1} = (k / (k + 2)) x_k + (2 / (k + 2)) v_{k+1}`. -/ x_succ : ∀ k : ℕ, k < N → x (k + 1) = ((k : ℝ) / (k + 2)) • x k + ((2 : ℝ) / (k + 2)) • v (k + 1)

Definition 7.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.3: a point p ∈ Q is a projection of x onto Q when its distance to x realizes the distance from x to the set Q.

open Metric universe u variable {E : Type u} [PseudoMetricSpace E] def IsProjectionPointOn (Q : Set E) (x p : E) : Prop := p ∈ Q ∧ dist x p = infDist x Q

Lemma 7.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.3: for a real symmetric matrix X, the spectral radius ρ(X) is the support function of Q₂.

open Matrix
open RealSymmetricMatrixSpace
open scoped BigOperators MatrixOrder SupportFunction RealSymmetricMatrixSpace
variable {n : ℕ}
local notation "SymmMat" => 𝕊^n
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
theorem realSymmetricMatrix_toReal_spectralRadius_eq_supportFunction_Q2
    (X : SymmMat) :
    ρ(X) = (ξ[spectral_eigenvalue_l1_unit_ball n] X).toReal

Proposition 7.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.3: the box-constrained dual optimal value max {⟪c, u⟫ : \hat Aᵀ u = 0, |uᵢ| ≤ 1} is the minimum value attained by the function y ↦ homogeneousLinearProgrammingPhi1 hatA c y.

open Matrix
open scoped BigOperators SupportFunction NormalCone WithTopConvexAnalysis
variable {m n : ℕ}
local notation "Eₘ" => EuclideanSpace ℝ (Fin m)
local notation "Eₙ₋₁" => EuclideanSpace ℝ (Fin (n - 1))
theorem homogeneousLinearProgrammingOptimalValue_isLeast_phi1_values
    (hatA : Matrix (Fin m) (Fin (n - 1)) ℝ) (c : Eₘ) :
    IsLeast (Set.range (homogeneousLinearProgrammingPhi1 hatA c))
      (homogeneousLinearProgrammingOptimalValue hatA c)

Theorem 7.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.3 (1): under the canonical stopping-time setup for Algorithm 7.2, the stopping time T is bounded above by 1 + 2 log (1 / α) once the initial value f x0 is positive.

universe u variable {X : Type u} variable [NormedAddCommGroup X] variable {f : X → ℝ} {G : ℕ → ℝ → X} {x0 xStar : X} {δ α γ0 γ1 : ℝ} local notation "x̂" => relativeScaleSubgradientApproximationIterate G f x0 δ α γ0 variable (hTerminate : relativeScaleSubgradientApproximationTerminates G f x0 δ α γ0) local notation "s" => relativeScaleSubgradientApproximationStoppingIndex hTerminate local notation "T" => relativeScaleSubgradientApproximationStoppingTime hTerminate theorem relativeScaleSubgradientApproximation_stopping_time_bound (hα : 0 < α) (hα_le_one : α ≤ 1) (hInitialValue_pos : 0 < f x0) (hxStar : IsMinOn f Set.univ xStar) (hOptimalValue_lower : α * f x0 ≤ f xStar) : (T : ℝ) ≤ 1 + 2 * Real.log (1 / α)

Algorithm 7.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.4 terminates when some stage satisfies the acceptance test f(\hat x_{t+1}) ≥ (1 / e) f(\hat x_t).

universe u variable {X : Type u} open scoped SchemeSNRestartingNotation def schemeSNRestartingTerminates (S : ℕ → ℝ → X) (f : X → ℝ) (x0 : X) (δ alphaF gamma0F : ℝ) : Prop := ∃ t : ℕ, schemeSNRestartingStoppingCriterion S f x0 δ alphaF gamma0F t

Definition 7.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.4: a conic unconstrained minimization problem on a real inner product space consists of a nonempty closed convex feasible set Q₁ avoiding the origin together with a convex positively 1-homogeneous real-valued objective f, under the standing nondegeneracy condition 0 ∈ interior (∂f(0)). Since the objective is E → ℝ, the textbook assumption dom f = E is built into the type, while the ambient constrained-problem data are owned canonically by SetConstrainedMinimizationProblem.

open scoped WithTopConvexAnalysis universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] structure ConicUnconstrainedMinimizationProblem (E : Type u) [NormedAddCommGroup E] [InnerProductSpace ℝ E] extends SetConstrainedMinimizationProblem E where /-- The feasible set `Q₁` is nonempty. -/ feasibleSet_nonempty : feasibleSet.Nonempty /-- The feasible set `Q₁` is closed. -/ feasibleSet_isClosed : IsClosed feasibleSet /-- The feasible set `Q₁` is convex. -/ feasibleSet_convex : Convex ℝ feasibleSet /-- The origin does not belong to `Q₁`. -/ zero_not_mem_feasibleSet : (0 : E) ∉ feasibleSet /-- The objective `f : E → ℝ` is convex on the whole space. -/ objective_convex : ConvexOn ℝ Set.univ objective /-- The objective `f` is positively homogeneous of degree `1`. -/ objective_posHomogeneous : IsPositivelyHomogeneousOn 1 Set.univ objective /-- The origin lies in the interior of the subdifferential `∂f(0)`. -/ zero_mem_interior_subdifferential : (0 : E) ∈ interior (∂ (fun y ↦ (objective y : WithTop ℝ))(0))

Lemma 7.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.4: if 2 ≤ n and σ = (1 / n) ‖g‖_{G,*}^2 - 1 is positive, then the optimal value of V is bounded below by σ² / ((1 + σ) (2 + σ)).

open Matrix open scoped EllipsoidNotation PositiveDefMatrixNorm SupportFunction variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ theorem rankOneUpdatePotential_optimalAlpha_lower_bound_rational (G : Mat) (hG : G.PosDef) (g : E) (hn : 2 ≤ n) (hσ : 0 < rankOneUpdateSigma G hG g) : (rankOneUpdateSigma G hG g ^ (2 : ℕ)) / ((1 + rankOneUpdateSigma G hG g) * (2 + rankOneUpdateSigma G hG g)) ≤ rankOneUpdatePotential G hG g (rankOneUpdateOptimalAlpha G hG g)

Proposition 7.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.4: along the restricted-dimension regime where n → ∞ and 0 < p < n (n + 1) / 2, if one iteration of Method S_N(R) has gradient work O(p n^2), Frobenius-projection work O(n^3), and auxiliary ℝ^p arithmetic work O(p^2), then the total one-step arithmetic work, obtained by summing those three component profiles, is O(n^2 (n + p)).

open Asymptotics open Filter local notation "DimPair" => ℕ × ℕ theorem supportFunctionSmoothingIterationWork_isBigO_n_sq_mul_n_add_p (gradientWork projectionWork auxiliaryWork : DimPair → ℝ) (hgradient : gradientWork =O[restrictedDimensionFilter] (fun dims ↦ (dims.2 : ℝ) * (dims.1 : ℝ) ^ (2 : ℕ))) (hprojection : projectionWork =O[restrictedDimensionFilter] (fun dims ↦ (dims.1 : ℝ) ^ (3 : ℕ))) (hauxiliary : auxiliaryWork =O[restrictedDimensionFilter] (fun dims ↦ (dims.2 : ℝ) ^ (2 : ℕ))) : (fun dims ↦ gradientWork dims + projectionWork dims + auxiliaryWork dims) =O[ restrictedDimensionFilter] (fun dims ↦ (dims.1 : ℝ) ^ (2 : ℕ) * ((dims.1 : ℝ) + dims.2))

Theorem 7.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.4 [Chapter7_1.json:27]: if f : ℝⁿ → ℝ is convex, α > 0, γ0 > 0, 0 < δ < 1, fStar is the infimum value of f, and every direct-structure iterate at radius aPrioriRadiusEstimate f γ0 x0 = (1 / γ₀(F)) f(x₀) satisfies the estimate f (S_k ((1 / γ₀(F)) f(x₀))) ≤ f* + (2 / (α(F)^2 (k + 1))) * f*, then the iterate with index ⌊2 / (α(F)^2 δ)⌋ satisfies f (S_N ((1 / γ₀(F)) f(x₀))) ≤ (1 + δ) f*.

variable {n : ℕ} local notation "Eₙ" => EuclideanSpace ℝ (Fin n) theorem direct_structure_iterate_value_le_one_add_delta_mul_optimal_value (f : Eₙ → ℝ) (S : ℕ → ℝ → Eₙ) (x0 : Eₙ) (α γ0 δ fStar : ℝ) (hf_convex : ConvexOn ℝ Set.univ f) (hα : 0 < α) (hγ0 : 0 < γ0) (hδ : 0 < δ) (hδ_lt_one : δ < 1) (hOptimalValue : IsGLB (Set.range f) fStar) (hEstimate : ∀ k : ℕ, f (S k (aPrioriRadiusEstimate f γ0 x0)) ≤ fStar + (2 / (α ^ (2 : ℕ) * (k + 1 : ℝ))) * fStar) : f (S (Nat.floor (2 / (α ^ (2 : ℕ) * δ))) (aPrioriRadiusEstimate f γ0 x0)) ≤ (1 + δ) * fStar

Algorithm 7.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.5 reuses the Chapter 7 weighted dual-norm owner.

open Matrix open scoped PositiveDefMatrixNorm variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ recall positiveDefMatrixNorm_dualNorm_apply

Definition 7.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.5: the homogenized objective of φ is the existing perspective transform on ℝ × E, with its natural cone domain perspectiveCone E.

universe u variable {E : Type u} [AddCommMonoid E] [Module ℝ E] local notation "P" => ℝ × E recall perspectiveCone

Lemma 7.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.5 (1): for every α ∈ [0, 1), if ‖g‖*_G ≠ 0, then the source one-sided ellipsoid W[1]((((r - 1) / (2r)) * α) • g, G(α)) belongs to the source hull C_g(G), written directly as convexHull ℝ (W[1](G.1) ∪ ({g} : Set E)). The zero-radius boundary case is recorded separately by centeredOneSidedRoundingEllipsoid_subset_convexHullOfWeightedUnitBallAndPoint_of_dualNorm_eq_zero.

open Matrix open scoped EllipsoidNotation PositiveDefMatrixNorm OneSidedHullNotation SupportFunction variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ theorem oneSidedRoundingEllipsoid_subset_convexHullOfWeightedUnitBallAndPoint (G : {A : Mat // A.PosDef}) (g : E) {α : ℝ} (hr0 : ‖g‖[G,*] ≠ 0) (hα : α ∈ Set.Ico (0 : ℝ) 1) : W[1](((((‖g‖[G,*] - 1) / (2 * ‖g‖[G,*])) * α) • g), (oneSidedRoundingUpdatedMatrix G g α)) ⊆ convexHull ℝ (W[1](G.1) ∪ ({g} : Set E))

Proposition 7.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.5 [Chapter7_2.json:38]: if A₁, …, Aₚ ∈ ℝ^(n × n) and G is the Frobenius Gram matrix with entries G^(i,j) = ⟪Aᵢ, Aⱼ⟫_F, then under the size condition p < n(n + 1) / 2 the preliminary computation modeled by frobeniusGramPreliminaryArithmeticWorkBound n p has total arithmetic work bounded by a constant multiple of p^2 n^2, i.e. of order O(p^2 n^2).

open Matrix variable {p n : ℕ} local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ theorem frobeniusGramPreliminaryArithmeticWork_has_quadratic_bound {n p : ℕ} (hpn : p < n * (n + 1) / 2) : ∃ C : ℕ, frobeniusGramPreliminaryArithmeticWorkBound n p ≤ C * (p ^ 2 * n ^ 2)

Theorem 7.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.5 [Chapter7_1.json:29]: if Algorithm 7.4 terminates at its canonical stopping time and xStar is a global minimizer whose value satisfies the homogeneous-model normalization alphaF * f(x₀) ≤ f(xStar), then the number T of generated restart points is bounded by 1 + log (1 / alphaF).

universe u variable {X : Type u} variable {f : X → ℝ} {S : ℕ → ℝ → X} {x0 xStar : X} {δ alphaF gamma0F : ℝ} variable (hTerminate : schemeSNRestartingTerminates S f x0 δ alphaF gamma0F) local notation "x̂" => schemeSNRestartingIterate S f x0 δ alphaF gamma0F local notation "s" => schemeSNRestartingStoppingIndex hTerminate local notation "T" => schemeSNRestartingStoppingTime hTerminate theorem schemeSNRestarting_stopping_time_bound (hAlphaF_pos : 0 < alphaF) (hInitialValue_pos : 0 < f x0) (hxStar : IsMinOn f Set.univ xStar) (hOptimalValue_lower : alphaF * f x0 ≤ f xStar) : (schemeSNRestartingStoppingTime hTerminate : ℝ) ≤ 1 + Real.log (1 / alphaF)

Algorithm 7.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.6: the finite-family inverse-matrix presentation of the centrally symmetric rounding process. The core owner is the Chapter 7 Gₖ-matrix method toCentralSymmetricRoundingMethod; the extra source-facing data are the generating family a₁, …, aₘ, the identification of the body with conv {±aᵢ}, the chosen maximizing indices, and the inverse-side update formulas for Hₖ = Gₖ⁻¹.

open Matrix open scoped BigOperators variable {m n : ℕ} local notation "Eₙ" => EuclideanSpace ℝ (Fin n) local notation "Eₘ" => EuclideanSpace ℝ (Fin m) structure CentralSymmetryRoundingAlgorithm (m n : ℕ) where /-- The core Chapter 7 centrally symmetric rounding method in `Gₖ`-matrix form. -/ toCentralSymmetricRoundingMethod : CentralSymmetricRoundingMethod n /-- The input vectors `a₁, …, aₘ ∈ ℝⁿ`. -/ vectors : Fin m → EuclideanSpace ℝ (Fin n) /-- The rounded body is the canonical absolutely convex hull `absConvexHull ℝ (Set.range a)`, equivalently the textbook symmetric convex hull `conv {±aᵢ}`. -/ body_eq : ((toCentralSymmetricRoundingMethod.body : ConvexBody (EuclideanSpace ℝ (Fin n))) : Set (EuclideanSpace ℝ (Fin n))) = absConvexHull ℝ (Set.range vectors) /-- The core method starts from the textbook Gram matrix `G₀ = (1 / m) ∑ᵢ aᵢ aᵢᵀ`. -/ initialMatrix_eq : toCentralSymmetricRoundingMethod.initialMatrix = centralSymmetryGramMatrix vectors /-- A choice of maximizing index `iₖ` at each iteration. -/ maximizingIndex : ℕ → Fin m /-- The core maximizer `gₖ` is the chosen generator `a_{iₖ}`. -/ maximizer_eq : ∀ k : ℕ, toCentralSymmetricRoundingMethod.maximizer k = vectors (maximizingIndex k) /-- Each chosen index `iₖ` realizes the maximum of the current score vector `vₖ`. -/ maximizingIndex_isMaxOn : ∀ k : ℕ, IsMaxOn (fun i ↦ centralSymmetryScore vectors ((toCentralSymmetricRoundingMethod k)⁻¹) i) Set.univ (maximizingIndex k) /-- If the stopping criterion fails at iteration `k`, then `Hₖ₊₁` is given by the rank-one matrix update from Algorithm 7.6. -/ inverse_succ : ∀ k : ℕ, ¬ centralSymmetryShouldStop toCentralSymmetricRoundingMethod.gamma n (centralSymmetrySelectedRadius vectors ((toCentralSymmetricRoundingMethod k)⁻¹) (maximizingIndex k)) → (toCentralSymmetricRoundingMethod (k + 1))⁻¹ = centralSymmetryNextInverseMatrix ((toCentralSymmetricRoundingMethod k)⁻¹) (centralSymmetryAlpha n (centralSymmetrySelectedRadius vectors ((toCentralSymmetricRoundingMethod k)⁻¹) (maximizingIndex k))) (centralSymmetryUpdateDirection ((toCentralSymmetricRoundingMethod k)⁻¹) vectors (maximizingIndex k)) /-- If the stopping criterion fails at iteration `k`, then the score vector derived from `Hₖ₊₁` is given coordinatewise by the textbook update formula. -/ score_succ : ∀ k : ℕ, ¬ centralSymmetryShouldStop toCentralSymmetricRoundingMethod.gamma n (centralSymmetrySelectedRadius vectors ((toCentralSymmetricRoundingMethod k)⁻¹) (maximizingIndex k)) → centralSymmetryScoreVector vectors ((toCentralSymmetricRoundingMethod (k + 1))⁻¹) = centralSymmetryNextScoreVector vectors (centralSymmetryScoreVector vectors ((toCentralSymmetricRoundingMethod k)⁻¹)) (centralSymmetryAlpha n (centralSymmetrySelectedRadius vectors ((toCentralSymmetricRoundingMethod k)⁻¹) (maximizingIndex k))) (centralSymmetryUpdateDirection ((toCentralSymmetricRoundingMethod k)⁻¹) vectors (maximizingIndex k))

Definition 7.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.6: the dual norm is the canonical norm on the continuous dual StrongDual ℝ E.

open Metric universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] #check (‖·‖ : StrongDual ℝ E → ℝ)

Lemma 7.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.6: if the convex hull of the vertices a i has nonempty interior, then the empirical ellipsoid centered at the arithmetic mean gives a polytopeRoundingRadius m-rounding of that convex hull.

open Matrix open scoped BigOperators open scoped EllipsoidNotation open scoped Pointwise open scoped PositiveDefMatrixNorm open scoped SupportFunction variable {m n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) theorem convexHull_range_between_empirical_ellipsoids_of_interior_nonempty (a : Fin m → E) (hinterior : (interior (convexHull ℝ (Set.range a))).Nonempty) : IsBetaRounding (convexHull ℝ (Set.range a)) (polytopeRoundingRadius m) (polytopeRoundingMatrix a) (polytopeArithmeticMean a)

Proposition 7.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.6 [Chapter7_1.json:40]: along the admissible regime 0 < p < n (n + 1) / 2 with n → ∞, if the accuracy profile δ(n, p) satisfies the displayed regime 0 < δ(n, p) ≤ n, then there exists an absolute constant C > 0 such that the eventual upper threshold δ(n, p) ≤ C / p implies that the displayed gradient-method complexity profile n^2 p^2 + (1 / 8) n^(5 / 2) (p + n) log n is asymptotically dominated by the displayed short-step path-following interior-point scale p n^(5 / 2) (p + n) log (n / δ(n, p)), i.e. whenever the accuracy parameter satisfies δ(n, p) = O(1 / p).

open Asymptotics open Filter local notation "DimPair" => ℕ × ℕ theorem gradientMethod_isBigO_interiorPointComplexity_of_const_inv_p_eventually_le_accuracy (δ : DimPair → ℝ) (hδ_pos : ∀ᶠ dims in restrictedDimensionFilter, 0 < δ dims) (hδ_le : ∀ᶠ dims in restrictedDimensionFilter, δ dims ≤ (dims.1 : ℝ)) : ∃ C > 0, (∀ᶠ dims in restrictedDimensionFilter, δ dims ≤ C / (dims.2 : ℝ)) → (fun dims : DimPair ↦ (dims.1 : ℝ) ^ (2 : ℕ) * (dims.2 : ℝ) ^ (2 : ℕ) + (1 / (8 : ℝ)) * Real.rpow (dims.1 : ℝ) (5 / 2 : ℝ) * ((dims.2 : ℝ) + (dims.1 : ℝ)) * Real.log (dims.1 : ℝ)) =O[ restrictedDimensionFilter] (fun dims ↦ (dims.2 : ℝ) * Real.rpow (dims.1 : ℝ) (5 / 2 : ℝ) * ((dims.2 : ℝ) + (dims.1 : ℝ)) * Real.log ((dims.1 : ℝ) / δ dims))

Theorem 7.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.6: if an Algorithm 7.5 run starts from the centered R-rounding W₁(G₀) ⊆ C ⊆ W_R(G₀), if every post-update iterate before the first stopping index still satisfies W₁(Gₖ) ⊆ C, and if every genuinely continuing step k < s gains at least 2 log γ - (γ² - 1) / γ² in log det Gₖ, then the canonical first stopping index s is bounded by 2 n γ² / (γ - 1)² * log R.

open Matrix open MeasureTheory open scoped EllipsoidNotation MatrixOrder variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) namespace CentralSymmetricRoundingMethod variable (method : CentralSymmetricRoundingMethod n) variable (hTerminate : method.Terminates) local notation "s" => method.stoppingIndex hTerminate theorem stoppingIndex_le {R : ℝ} (hInitial : IsBetaRounding (method.body : Set E) R (method 0) (0 : E)) (hinner : ∀ k : ℕ, k < s → W[1]((method (k + 1))) ⊆ (method.body : Set E)) (hlogDet : ∀ k : ℕ, k < s → Real.log (Matrix.det (method (k + 1))) ≥ Real.log (Matrix.det (method k)) + (2 * Real.log method.gamma - (method.gamma ^ (2 : ℕ) - 1) / method.gamma ^ (2 : ℕ))) : (s : ℝ) ≤ 2 * (n : ℝ) * method.gamma ^ (2 : ℕ) / (method.gamma - 1) ^ (2 : ℕ) * Real.log R

Algorithm 7.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.7: an iterative scheme for computing a γ n-rounding of a convex set C with nonempty interior consists of a parameter γ > 1, initial data v₀ ∈ ℝⁿ and G₀ ≻ 0, sequences of centers v_k, positive-definite shape matrices G_k, and maximizers g_k ∈ argmax_{g ∈ C} ‖g - v_k‖_{G_k}^*, where r_k = max_{g ∈ C} ‖g - v_k‖_{G_k}^* is the corresponding maximal value, such that whenever r_k > γ n the updates for v_{k+1} and G_{k+1} are exactly the displayed formulas with α_k = (2 / (n + 1)) ((r_k - n) / (r_k - 1)) and β_k = α_k / r_k + ((r_k - 1) / 2)^2 (α_k / r_k)^2.

open Matrix open scoped PositiveDefMatrixNorm variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ structure GeneralConvexRoundingAlgorithm (C : Set E) (gamma : ℝ) (v0 : E) (G0 : Mat) where /-- The ambient set `C` is convex. -/ convexSet : Convex ℝ C /-- The ambient convex set `C` has nonempty interior. -/ interior_nonempty : (interior C).Nonempty /-- The rounding parameter satisfies `γ > 1`. -/ gamma_one_lt : 1 < gamma /-- The center sequence `v₀, v₁, v₂, ...`. -/ center : ℕ → E /-- The shape-matrix sequence `G₀, G₁, G₂, ...`. -/ shape : ℕ → Mat /-- The chosen maximizers `g₀, g₁, g₂, ...`. -/ maximizer : ℕ → E /-- The center sequence starts from the prescribed initial point `v₀`. -/ center_zero : center 0 = v0 /-- The shape sequence starts from the prescribed initial matrix `G₀`. -/ shape_zero : shape 0 = G0 /-- Every shape matrix `G_k` is positive definite. -/ shape_posDef : ∀ k : ℕ, (shape k).PosDef /-- Each chosen point `g_k` lies in the canonical argmax set of the current `G_k`-dual distance on `C`. -/ maximizer_mem_argmax : ∀ k : ℕ, let G : {G : Mat // G.PosDef} := ⟨shape k, shape_posDef k⟩ maximizer k ∈ generalConvexRoundingArgmax C G (center k) /-- If the stopping test fails at step `k`, then the next center is updated by `v_{k+1} = v_k + α_k ((r_k - 1) / (2 r_k)) (g_k - v_k)`, where `r_k = max_{g ∈ C} ‖g - v_k‖_{G_k}^*`. -/ center_succ : ∀ k : ℕ, let G : {G : Mat // G.PosDef} := ⟨shape k, shape_posDef k⟩ let r := generalConvexRoundingRadius C G (center k) ¬ generalConvexRoundingShouldStop gamma n r → center (k + 1) = generalConvexRoundingNextCenter n r (center k) (maximizer k) /-- If the stopping test fails at step `k`, then the next shape matrix is updated by `G_{k+1} = (1 - α_k) G_k + β_k (g_k - v_k) (g_k - v_k)ᵀ`, where `r_k = max_{g ∈ C} ‖g - v_k‖_{G_k}^*`. -/ shape_succ : ∀ k : ℕ, let G : {G : Mat // G.PosDef} := ⟨shape k, shape_posDef k⟩ let r := generalConvexRoundingRadius C G (center k) ¬ generalConvexRoundingShouldStop gamma n r → shape (k + 1) = generalConvexRoundingNextShape n r (shape k) (center k) (maximizer k)

Definition 7.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.7: positive scalars γ₀ ≤ γ₁ satisfy the asphericity condition for f with respect to the chosen seminorm p when the dual affine supports of f at the origin are sandwiched between the corresponding dual closed balls of radii γ₀ and γ₁.

universe u v open Metric open scoped WithTopConvexAnalysis variable {E : Type u} [SeminormedAddCommGroup E] [NormedSpace ℝ E] def SatisfiesAsphericityCondition (f : E → ℝ) (p : Seminorm ℝ E) (γ₀ γ₁ : ℝ) : Prop := 0 < γ₀ ∧ γ₀ ≤ γ₁ ∧ dualClosedBall p γ₀ ⊆ {g : StrongDual ℝ E | ∀ y : E, f 0 + g y ≤ f y} ∧ {g : StrongDual ℝ E | ∀ y : E, f 0 + g y ≤ f y} ⊆ dualClosedBall p γ₁

Lemma 7.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.7 (3): assume S = ‖g‖*_D² > n, and let α* = (S - n) / ((2 S - n) S). Then for every γ ∈ (1, ‖g‖*_D / √n], the logarithmic potential at α* satisfies V(α*) ≤ log (1 + (γ² - 1) / γ²) - (γ² - 1) / γ² < 0.

open EuclideanSpace (nonnegativeOrthant)
open Matrix
open scoped BigOperators EllipsoidNotation Pointwise PositiveDefMatrixNorm SupportFunction
  SymmetricBox
variable {n : ℕ}
local notation "Eₙ" => EuclideanSpace ℝ (Fin n)
local notation "Matₙ" => Matrix (Fin n) (Fin n) ℝ
theorem ellipsoidBoxLogVolumePotential_alphaStar_le_gammaComparison_and_lt_zero
    (D : Matₙ) (hDdiag : D.IsDiag) (hDpos : D.PosDef) (g : Eₙ)
    (hS : (n : ℝ) < ‖g‖[⟨D, hDpos⟩,*] ^ (2 : ℕ)) (γ : ℝ)
    (hγ :
      γ ∈
        Set.Ioc
          (1 : ℝ)
          (‖g‖[⟨D, hDpos⟩,*] / Real.sqrt (n : ℝ))) :
    ellipsoidBoxLogVolumePotential D g (ellipsoidBoxAlphaStar D hDpos g) ≤
      Real.log (1 + (γ ^ (2 : ℕ) - 1) / γ ^ (2 : ℕ)) -
        (γ ^ (2 : ℕ) - 1) / γ ^ (2 : ℕ) ∧
    Real.log (1 + (γ ^ (2 : ℕ) - 1) / γ ^ (2 : ℕ)) -
        (γ ^ (2 : ℕ) - 1) / γ ^ (2 : ℕ) < 0

Proposition 7.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.7: if every interior simplex combination B(t) is invertible, then ψ* coincides with both the quadratic max formulation and the ratio max formulation, provided the index family is nonempty and the ambient space has positive dimension.

open scoped BigOperators Matrix
open scoped WeightedGramMatrix
variable {ι : Type} [Fintype ι]
variable [Nonempty ι]
theorem psiStar_eq_max_formulations
    (n : ℕ) (hn : 0 < n) (a : ι → EuclideanSpace ℝ (Fin (2 * n)))
    (f : EuclideanSpace ℝ (Fin (2 * n)))
    (hinv : ∀ t : StdSimplex.Strict ℝ ι, IsUnit (B[a](t.1.weights))) :
    psiStar a f = maxQuadraticValue a f ∧ maxQuadraticValue a f = maxRatioValue a f

Theorem 7.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.7: if n ≥ 1, an Algorithm 7.7 run starts from an R-rounding W₁(v₀,G₀) ⊆ C ⊆ W_R(v₀,G₀), every k < T is a genuine continuing step in the current owner API and satisfies the source continuation threshold (n / (n + 1)) (γ - 1) ≤ σₖ, and the first post-continuation iterate T falls below that threshold, then T ≤ ((1 + 2γ) (2 + γ) / (2 (γ - 1)²)) n log R.

open Matrix
open MeasureTheory
open scoped EllipsoidNotation MatrixOrder
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
namespace GeneralConvexRoundingAlgorithm
variable {C : Set E} {gamma R : ℝ} {v0 : E} {G0 : Mat}
theorem iterations_le
    (algorithm : GeneralConvexRoundingAlgorithm C gamma v0 G0)
    (hn : 1 ≤ n)
    {T : ℕ}
    (hInitial : IsBetaRounding C R G0 v0)
    (hContinueStrict :
      ∀ k : ℕ, k < T →
        ¬ algorithm.stoppingCriterion k)
    (hContinue :
      ∀ k : ℕ, k < T →
        ((n : ℝ) / (n + 1 : ℝ)) * (gamma - 1) ≤ algorithm.oneSidedRoundingSigma k)
    (hStop :
      algorithm.oneSidedRoundingSigma T <
        ((n : ℝ) / (n + 1 : ℝ)) * (gamma - 1)) :
    (T : ℝ) ≤
      ((1 + 2 * gamma) * (2 + gamma)) / (2 * (gamma - 1) ^ (2 : ℕ)) *
        (n : ℝ) * Real.log R

Algorithm 7.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.8: the accelerated scheme S(φ, L, Q, G, x₀, N) for a differentiable convex objective φ on a feasible set Q ⊆ ℝⁿ with positive-definite weight matrix G and parameter L > 0 consists of sequences x_k and v_k started from x₀, such that for every k = 0, …, N - 1 one has y_k = (k / (k + 2)) x_k + (2 / (k + 2)) v_k, v_{k+1} ∈ arg min_{v ∈ Q} [⟪∑_{i=0}^k ((i + 1) / 2) ∇φ(y_i), v - x₀⟫ + (L / 2) ‖v - x₀‖_G^2], and x_{k+1} = (k / (k + 2)) x_k + (2 / (k + 2)) v_{k+1}. The owner stores only the run-defining data and update laws; auxiliary assumptions such as closedness of Q or positivity of N belong to theorem-level bridges and analyses. The output of the scheme is x_N.

open Matrix open scoped BigOperators ConstrainedArgmin PositiveDefMatrixNorm variable {n N : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) structure AcceleratedConvexMinimizationScheme (n N : ℕ) where /-- The constrained problem owner supplying the feasible set `Q ⊆ ℝⁿ` and the objective `φ : ℝⁿ → ℝ`. -/ problem : SetConstrainedMinimizationProblem (EuclideanSpace ℝ (Fin n)) /-- The objective is convex on `Q`. -/ objective_convex : ConvexOn ℝ problem.feasibleSet problem /-- A chosen gradient field for the objective on `Q`. -/ gradient : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n) /-- The chosen field agrees with the gradient of the objective at each feasible point. -/ gradient_hasGradientAt {x : EuclideanSpace ℝ (Fin n)} (hx : x ∈ problem.feasibleSet) : HasGradientAt problem (gradient x) x /-- The positive-definite matrix owner defining the proximal quadratic term. -/ metricMatrix : {G : Matrix (Fin n) (Fin n) ℝ // G.PosDef} /-- The smoothness parameter `L > 0`, encoded canonically as a positive nonnegative real. -/ smoothness : NNRealˣ /-- The initial point `x₀`. -/ initialPoint : EuclideanSpace ℝ (Fin n) /-- The initial point belongs to the feasible set. -/ initialPoint_mem : initialPoint ∈ problem.feasibleSet /-- The primal iterates `x₀, x₁, x₂, ...`. -/ x : ℕ → EuclideanSpace ℝ (Fin n) /-- The auxiliary points `v₀, v₁, v₂, ...`. -/ v : ℕ → EuclideanSpace ℝ (Fin n) /-- The primal sequence starts at `x₀`. -/ x_zero : x 0 = initialPoint /-- The auxiliary sequence starts at `v₀ = x₀`. -/ v_zero : v 0 = initialPoint /-- For each `k = 0, …, N - 1`, the successor point `v_{k+1}` minimizes the proximal objective over `Q`. -/ v_succ_mem_argmin (k : ℕ) (hk : k < N) : v (k + 1) ∈ argmin[problem.feasibleSet] (acceleratedSchemeProximalMinimand gradient metricMatrix smoothness initialPoint x v k) /-- For each `k = 0, …, N - 1`, the successor iterate is the convex combination `x_{k+1} = (k / (k + 2)) x_k + (2 / (k + 2)) v_{k+1}`. -/ x_succ (k : ℕ) (hk : k < N) : x (k + 1) = ((k : ℝ) / (k + 2)) • x k + ((2 : ℝ) / (k + 2)) • v (k + 1)

Definition 7.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.8: the projection of the origin onto Q1 with respect to the norm is the existing projection-point predicate specialized to the base point 0.

universe u variable {E : Type u} [NormedAddCommGroup E] variable (Q1 : Set E) (x0 : E) #check (IsProjectionPointOn Q1 (0 : E) x0 : Prop)

Lemma 7.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.8: if the convex hull of the boxes B(a_i) with nonnegative generators contains W₁(D) and is contained in W_{γ √n}(D), then on the nonnegative orthant the support function of that box hull is sandwiched between ‖x‖_D and γ √n ‖x‖_D.

open EuclideanSpace (nonnegativeOrthant) open Matrix open scoped EllipsoidNotation PositiveDefMatrixNorm SupportFunction SymmetricBox variable {m n : ℕ} local notation "Eₙ" => EuclideanSpace ℝ (Fin n) local notation "Matₙ" => Matrix (Fin n) (Fin n) ℝ theorem supportFunction_signSymmetricConvexHull_bounds_on_nonnegativeOrthant (a : Fin m → Eₙ) {D : Matₙ} {γ : ℝ} (ha_nonneg : ∀ i : Fin m, a i ∈ nonnegativeOrthant n) (hrounding : IsEllipsoidalRounding (signSymmetricConvexHull a) γ D) (x : Eₙ) (hx_nonneg : x ∈ nonnegativeOrthant n) : ‖x‖[⟨D, hrounding.posDef⟩] ≤ (ξ[signSymmetricConvexHull a] x).toReal ∧ (ξ[signSymmetricConvexHull a] x).toReal ≤ γ * Real.sqrt (n : ℝ) * ‖x‖[⟨D, hrounding.posDef⟩]

Proposition 7.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.8: among feasible points α ∈ [0, 1), the scalar objective V is maximized exactly at α* = σ / (n (1 + σ) - 1).

theorem centralSymmetryRoundingObjective_isMaxOn_iff {n : ℕ} {σ : ℝ} (hn : 2 ≤ n) (hσ : 0 ≤ σ) {α : ℝ} (hα : α ∈ Set.Ico (0 : ℝ) 1) : IsMaxOn (centralSymmetryRoundingObjective n σ) (Set.Ico (0 : ℝ) 1) α ↔ α = centralSymmetryRoundingAlphaStar n σ

Theorem 7.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.8: if C ⊆ ℝⁿ is a sign-symmetric compact convex set with nonempty interior, then there exists a diagonal matrix D with D ≻ 0 such that W_1(D) ⊆ C ⊆ W_(sqrt n)(D).

open Matrix
open scoped BigOperators ConvexAnalysis EllipsoidNotation PositiveDefMatrixNorm SupportFunction
  SymmetricBox
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
local notation "DiagVec" => Fin n → ℝ
theorem exists_diagonal_rounding_of_signInvariant_convex_interior_nonempty
    {C : Set E} (h_sign : IsSignInvariant C) (h_convex : Convex ℝ C)
    (h_interior : (interior C).Nonempty) (h_compact : IsCompact C) :
    ∃ D : Mat, D.IsDiag ∧ IsEllipsoidalRounding C 1 D

Algorithm 7.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.9: termination means that some outer stage satisfies the acceptance test f(\hat x_{t+1}) ≥ (1 / e) f(\hat x_t).

open Matrix open scoped BigOperators PositiveDefMatrixNorm variable {m : ℕ+} {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "PosMat" => { G : Matrix (Fin n) (Fin n) ℝ // Matrix.PosDef G } local notation "ConstraintVec" => { d : E // d ≠ 0 } def iterativeSmoothingTerminates (a : Fin (m : ℕ) → E) (xHat : ℕ → E) : Prop := ∃ t : ℕ, iterativeSmoothingStoppingCriterion a xHat t

Definition 7.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.9: the a priori radius estimate attached to a function f, a base point x0, and a scalar γ₀ is the quantity γ₀⁻¹ f(x₀).

universe u def aPrioriRadiusEstimate {X : Type u} (f : X → ℝ) (γ₀ : ℝ) (x0 : X) : ℝ := f x0 / γ₀

Lemma 7.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.9: if a set C lies between the boxes B(d) and B(m d), where the semiaxes d i are positive, then C lies between the corresponding diagonal ellipsoids W₁(D²) and W_{m √n}(D²), where D = diag(d). Equivalently, the diagonal-square matrix D² is an ellipsoidal rounding of C with parameter m.

open EuclideanSpace (positiveOrthant) open Matrix open scoped BigOperators EllipsoidNotation SymmetricBox variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ theorem symmetricBox_sandwich_implies_diagonalEllipsoid_sandwich (a : E) (ha : a ∈ positiveOrthant n) {m : ℝ} {C : Set E} (h_left : B(a) ⊆ C) (h_right : C ⊆ B((m • a))) : IsEllipsoidalRounding C m (diagonalSquareMatrix a)

Proposition 7.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.9 [Chapter7_1.json:55]: if a matrix sequence starts from a convex combination of the rank-one matrices aᵢ aᵢᵀ and each step applies the Algorithm 7.6 rank-one update with some coefficient αₖ ∈ [0, 1] and some chosen generator a_{jₖ}, then every Gₖ is again a convex combination of the same rank-one matrices.

open Matrix
open scoped BigOperators Matrix
universe u
variable {ι : Type u} [Fintype ι]
variable {m : ℕ}
variable {n : ℕ}
local notation "Eₙ" => EuclideanSpace ℝ (Fin n)
open scoped WeightedGramMatrix

-- Proof sketch: expand the `(p, q)` entry of each rank-one matrix `aᵢ aᵢᵀ` and distribute the
-- finite sum over the matrix entries.
theorem exists_simplex_weights_for_rank_one_update_sequence
    (a : Fin m → Eₙ) (G : ℕ → Matrix (Fin n) (Fin n) ℝ)
    (choice : ℕ → Fin m) (α : ℕ → ℝ) (weights0 : StdSimplex ℝ (Fin m))
    (hG0 : G 0 = B[a](weights0.weights))
    (hα : ∀ k : ℕ, 0 ≤ α k ∧ α k ≤ 1)
    (hGsucc :
      ∀ k : ℕ,
        G (k + 1) =
          centralSymmetricRoundingUpdatedMatrix (G k) (a (choice k)) (α k)) :
    ∀ k : ℕ, ∃ weightsk : StdSimplex ℝ (Fin m), G k = B[a](weightsk.weights)

Theorem 7.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.9: if a_i ∈ ℝⁿ_+, b_i > 0 for i = 1, …, m, and the orthant polyhedron {x ∈ ℝⁿ_+ | ⟪a_i, x⟫ ≤ b_i for all i} is bounded, then it is sandwiched between W₁(D) ∩ ℝⁿ_+ and W_{√n}(D) ∩ ℝⁿ_+ for some diagonal positive-definite matrix D.

open EuclideanSpace (nonnegativeOrthant)
open Matrix
open scoped EllipsoidNotation Pointwise
variable {m n : ℕ}
local notation "Eₙ" => EuclideanSpace ℝ (Fin n)
local notation "Matₙ" => Matrix (Fin n) (Fin n) ℝ
theorem exists_positive_diagonal_rounding_of_orthant_polyhedron
    (a : Fin m → Eₙ) (b : Fin m → ℝ)
    (ha_nonneg : ∀ i : Fin m, a i ∈ nonnegativeOrthant n)
    (hb_pos : ∀ i : Fin m, 0 < b i)
    (h_bounded : Bornology.IsBounded (orthantHalfspacePolyhedron a b)) :
    ∃ D : Matₙ, D.IsDiag ∧
      IsOrthantEllipsoidalRounding (orthantHalfspacePolyhedron a b) 1 D

Algorithm 7.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.10: the normalized reciprocal vector defining x₀ belongs to the standard simplex.

open Matrix open scoped BigOperators PositiveDefMatrixNorm StandardSimplex variable {m n : ℕ+} local notation "Δₙ" => Δ[(n : ℕ)] local notation "Eₙ" => EuclideanSpace ℝ (Fin (n : ℕ)) local notation "PosMat" => { G : Matrix (Fin (n : ℕ)) (Fin (n : ℕ)) ℝ // Matrix.PosDef G } local notation "DiagPosMat" => { G : Matrix (Fin (n : ℕ)) (Fin (n : ℕ)) ℝ // Matrix.IsDiag G ∧ Matrix.PosDef G } local notation "Solver" => (Δₙ → ℝ) → ℝ → Set Δₙ → PosMat → Δₙ → ℕ → Δₙ theorem matrixGameRelativeScaleInitialPointVector_mem_stdSimplex (D : DiagPosMat) : matrixGameRelativeScaleInitialPointVector D ∈ (Δ[(n : ℕ)] : Set (Fin (n : ℕ) → ℝ))

Definition 7.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.10: a support-function minimization problem consists of a closed bounded convex set Q₂ ⊆ ℝᵐ with 0 ∈ interior Q₂, a matrix A ∈ ℝ^(m × n) with full column rank, and a closed convex set Q₁ ⊆ ℝⁿ; its canonical support-function objective is x ↦ ξ[Q₂] (A x), and the associated real-valued minimization objective is obtained from that Chapter 3 owner by the standard toReal bridge.

open Matrix open scoped SupportFunction variable {m n : ℕ} local notation "Eₘ" => EuclideanSpace ℝ (Fin m) local notation "Eₙ" => EuclideanSpace ℝ (Fin n) structure SupportFunctionOptimizationProblem (m n : ℕ) where /-- The closed bounded convex set `Q₂ ⊆ ℝᵐ` defining the support function. -/ Q2 : Set (EuclideanSpace ℝ (Fin m)) /-- The set `Q₂` is closed. -/ Q2_closed : IsClosed Q2 /-- The set `Q₂` is bounded. -/ Q2_bounded : Bornology.IsBounded Q2 /-- The set `Q₂` is convex. -/ Q2_convex : Convex ℝ Q2 /-- The origin belongs to the interior of `Q₂`. -/ zero_mem_interior_Q2 : (0 : EuclideanSpace ℝ (Fin m)) ∈ interior Q2 /-- The matrix `A ∈ ℝ^(m × n)` defining the linear map `x ↦ A x`. -/ A : Matrix (Fin m) (Fin n) ℝ /-- The matrix `A` has full column rank, encoded as injectivity of its Euclidean linear map. -/ A_full_column_rank : Function.Injective (Matrix.toEuclideanLin A) /-- The closed convex feasible set `Q₁ ⊆ ℝⁿ`. -/ Q1 : Set (EuclideanSpace ℝ (Fin n)) /-- The feasible set `Q₁` is closed. -/ Q1_closed : IsClosed Q1 /-- The feasible set `Q₁` is convex. -/ Q1_convex : Convex ℝ Q1

Lemma 7.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.10. In the Definition 7.53 setup, assume x₀ is the constrained analytic center x0 ∈ argmin[hatP ∩ interior Q] F. If x = u^*_β(s) is the unique active maximizer in hatP, hatP ⊆ interior Q, the unperturbed tilted objective z ↦ β * F z - s z is stationary at x, and F is standard self-concordant on interior Q, then the support-function approximation is differentiable at s with derivative x - x₀; moreover, for perturbations g satisfying the source-facing active-point local-dual-norm condition ‖g‖_x^* < β encoded by supportFunctionApproximationDualLocalNormLt, it satisfies the one-step ω_* upper model. The determinant, invertibility, and positive-definite-domain readers remain separate companion bridge theorems.

open scoped ConstrainedArgmin Topology Gradient WithTopConvexAnalysis HessianDualLocalNorm
  HessianLocalNorm SelfConcordantAuxiliaryFunction
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
variable (hatP Q : Set E) (F : E → ℝ) (x0 : E) (β : {β : ℝ // 0 < β})
theorem smoothSupportFunctionApproximation_hasFDerivAt_and_omegaStar_upper_bound
    {s : StrongDual ℝ E} {x : E}
    [IsStandardSelfConcordantOn (interior Q) F]
    (hx_argmax : x ∈ Argmaxβ hatP F β s)
    (hx_unique : ∀ u : E, u ∈ Argmaxβ hatP F β s → u = x)
    (hhatP_int : hatP ⊆ interior Q)
    (hx0 : x0 ∈ argmin[hatP ∩ interior Q] F)
    (hstationary : ∇ (fun z : E ↦ (β : ℝ) * F z - s z) x = 0) :
    HasFDerivAt (Uβ hatP F x0 β)
      (ContinuousLinearMap.apply ℝ ℝ (x - x0)) s ∧
      ∀ g : StrongDual ℝ E,
      ∀ hg : supportFunctionApproximationDualLocalNormLt hatP Q F β hx_argmax hhatP_int g,
      Uβ hatP F x0 β (s + g) ≤
      Uβ hatP F x0 β s +
          g (x - x0) +
            supportFunctionApproximationOmegaStarUpperTerm
              hatP Q F β hx_argmax hhatP_int g hg

Proposition 7.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.10 [Chapter7_1.json:56] (1): if the positive-definite matrix G is represented as the weighted Gram matrix B[a](weights.weights) = ∑ᵢ λᵢ aᵢ aᵢᵀ, then the equivalent canonical matrix identity G⁻¹ B[a](weights.weights) = Iₙ holds.

open Matrix open scoped BigOperators PositiveDefMatrixNorm variable {m n : ℕ} local notation "Eₙ" => EuclideanSpace ℝ (Fin n) open scoped WeightedGramMatrix theorem inv_mul_weightedGramMatrix_eq_one (a : Fin m → Eₙ) (weights : StdSimplex ℝ (Fin m)) (G : {A : Matrix (Fin n) (Fin n) ℝ // A.PosDef}) (hG : (G : Matrix (Fin n) (Fin n) ℝ) = B[a](weights.weights)) : ((G : Matrix (Fin n) (Fin n) ℝ)⁻¹) * B[a](weights.weights) = (1 : Matrix (Fin n) (Fin n) ℝ)

Theorem 7.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.10: assume n ≥ 1, let m : ℕ+, and assume γ ≥ √(1 + 1 / √n). Then the Chapter 7 sign-invariant recursive rounding scheme (7.2.18) encoded by algorithm terminates after at most [(γ² - 1) / γ² - log (1 + (γ² - 1) / γ²)]⁻¹ n (log n + 2 log m) iterations.

open Matrix
open MeasureTheory
open scoped EllipsoidNotation MatrixOrder PositiveDefMatrixNorm
variable {n : ℕ} {m : ℕ+}
local notation "Eₙ" => EuclideanSpace ℝ (Fin n)
local notation "Matₙ" => Matrix (Fin n) (Fin n) ℝ
local notation "PosMatₙ" => { G : Matₙ // Matrix.PosDef G }
namespace SignInvariantRoundingAlgorithm
local notation "SignAlg" => @SignInvariantRoundingAlgorithm n m
theorem stoppingTime_le
    (algorithm : SignAlg)
    (γ : ℝ) (hn : 1 ≤ n)
    (hγ : Real.sqrt (1 + 1 / Real.sqrt (n : ℝ)) ≤ γ)
    :
    ∃ hTerminate : algorithm.Terminates γ,
      (algorithm.stoppingTime hTerminate : ℝ) ≤
        (((γ ^ (2 : ℕ) - 1) / γ ^ (2 : ℕ) -
            Real.log (1 + (γ ^ (2 : ℕ) - 1) / γ ^ (2 : ℕ)))⁻¹ *
          (n : ℝ) * (Real.log (n : ℝ) + 2 * Real.log (m : ℝ)))

Algorithm 7.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.11: the repeated-squaring recursion returns the pair (X_k, Y_k) = (A^(2^k), A^(2^k - 1)); equivalently, for p = 2^k it outputs A^p and A^(p - 1).

universe u variable {α : Type u} [Monoid α] theorem repeatedSquaringOutputs_eq_powers (A : α) (k : ℕ) : repeatedSquaringOutputs A k = (A ^ (2 ^ k), A ^ (2 ^ k - 1))

Definition 7.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.11: for the support function F(v) = max_{u ∈ Q₂} ⟪v, u⟫ of a convex body Q₂, the relative-scale ratio α(F) is the quotient γ₀(F) / γ₁(F) of the inner and outer Euclidean radii of ∂F(0). The textbook hypothesis 0 ∈ interior Q₂ is not needed to define this quotient itself, so it is left to later positivity/nondegeneracy results instead of being packaged as primitive data here.

open scoped SupportFunction WithTopConvexAnalysis universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] namespace ConvexBody def relativeScaleRatio (Q2 : ConvexBody E) : ℝ := Q2.gammaZero / Q2.gammaOne

Lemma 7.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.11 (1): if xBeta belongs to P and maximizes the barrier-regularized affine payoff there, xStar belongs to P and maximizes ℓ there, and x₀ minimizes F on P, then ℓ⋆(β) ≤ ℓ⋆.

universe u open scoped ConstrainedArgmin variable {E : Type u} [AddCommGroup E] [Module ℝ E] variable {P : Set E} {F : E → ℝ} {ℓ : AffineMap ℝ E ℝ} variable {x0 xStar xBeta : E} {β v : ℝ} local notation "Φβ" => affineBarrierRegularizedPayoff x0 β ℓ F -- Proof sketch: since `x₀` minimizes `F` on `P`, every feasible value satisfies -- `F(x) - F(x₀) ≥ 0`. Hence the regularized payoff is bounded above pointwise on `P` by the -- affine functional `ℓ`, and comparing the maximizers `xBeta` and `xStar` gives the result. theorem affineBarrierRegularizedPayoff_max_le_affine_max (hβ : 0 < β) (hx0 : x0 ∈ argmin[P] F) (hxStar_mem : xStar ∈ P) (hxStar_max : IsMaxOn ℓ P xStar) (hxBeta_mem : xBeta ∈ P) (hxBeta_max : IsMaxOn Φβ P xBeta) : Φβ xBeta ≤ ℓ xStar

Proposition 7.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.11 (1): if a matrix path G is twice differentiable on a neighborhood of 0, stays positive definite near 0, and its first and second trace identities are encoded by the parameters τ₁, …, τₙ, then the determinant-ratio potential V(α) = log (det G(0) / det G(α)) satisfies the stated formula for V'(0).

open Matrix
open scoped BigOperators RealSymmetricMatrixSpace Topology
variable {n : ℕ}
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
local notation "SymmMat" => 𝕊^n
variable (G : ℝ → Mat) (τ : Fin n → ℝ)
variable (hpos : ∃ ε > 0, ∀ ⦃α : ℝ⦄, |α| < ε → (G α).PosDef)
variable
  (hGtwice :
    ∃ ε > 0, ∀ ⦃α : ℝ⦄, |α| < ε →
      DifferentiableAt ℝ G α ∧ DifferentiableAt ℝ (deriv G) α)
variable (htrace₁ : Matrix.trace ((G 0)⁻¹ * deriv G 0) = ∑ i : Fin n, (τ i - 1))
variable
  (htrace₂ :
    Matrix.trace
        ((G 0)⁻¹ * deriv (deriv G) 0 - (G 0)⁻¹ * deriv G 0 * (G 0)⁻¹ * deriv G 0) =
      -∑ i : Fin n, (τ i - 1) ^ (2 : ℕ))

-- Proof sketch: differentiate `V(α) = log (det G(0) / det G(α))` using Jacobi's formula for
-- `det`, the derivative of matrix inversion, and the cyclicity of the trace; then substitute the
-- two assumed trace identities at `α = 0`.
theorem logDetRatioPotential_deriv_at_zero
    (hpos : ∃ ε > 0, ∀ ⦃α : ℝ⦄, |α| < ε → (G α).PosDef)
    (hGtwice :
      ∃ ε > 0, ∀ ⦃α : ℝ⦄, |α| < ε →
        DifferentiableAt ℝ G α ∧ DifferentiableAt ℝ (deriv G) α)
    (htrace₁ : Matrix.trace ((G 0)⁻¹ * deriv G 0) = ∑ i : Fin n, (τ i - 1))
    (htrace₂ :
      Matrix.trace
          ((G 0)⁻¹ * deriv (deriv G) 0 - (G 0)⁻¹ * deriv G 0 * (G 0)⁻¹ * deriv G 0) =
        -∑ i : Fin n, (τ i - 1) ^ (2 : ℕ))
    :
    deriv (logDetRatioPotential G) 0 = (n : ℝ) - ∑ i : Fin n, τ i

Theorem 7.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.11 (1): if the generated points are feasible, feasible points have value at least f*, the initial value satisfies f(\hat x_0) ≤ γ √n f*, and the stagewise smoothing parameters are positive, then the stopping time is bounded by 1 + log (γ √n) once the scale parameter is positive.

variable {m : ℕ+} {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "PosMat" => { G : Matrix (Fin n) (Fin n) ℝ // Matrix.PosDef G } local notation "ConstraintVec" => { d : E // d ≠ 0 } variable {S : (E → ℝ) → ℝ → Set E → PosMat → E → ℕ → E} {a : Fin (m : ℕ) → E} {d : ConstraintVec} {G : PosMat} {δ γ fStar : ℝ} {feasibleSet : Set E} {xHat : ℕ → E} variable (hZero : xHat 0 = iterativeSmoothingInitialPoint d G) (hParameterPos : ∀ t : ℕ, 0 < iterativeSmoothingParameter a δ (xHat t)) (hSucc : ∀ t : ℕ, xHat (t + 1) = iterativeSmoothingStep S a d G δ γ (xHat t) (hParameterPos t)) variable (hTerminate : iterativeSmoothingTerminates a xHat) local notation "x̂" => xHat local notation "F" => maxTypeObjective (fun i y ↦ |inner ℝ (a i) y|) local notation "s" => iterativeSmoothingStoppingIndex hTerminate local notation "T" => iterativeSmoothingStoppingTime hTerminate local notation "x̂T" => iterativeSmoothingOutputPoint hTerminate theorem iterativeSmoothing_stoppingTime_le (hParameterPos : ∀ t : ℕ, 0 < iterativeSmoothingParameter a δ (xHat t)) (hScale_pos : 0 < γ * Real.sqrt (n : ℝ)) (hGenerated_feasible : ∀ t : ℕ, x̂ t ∈ feasibleSet) (hOptimal_value_le_of_feasible : ∀ x : E, x ∈ feasibleSet → fStar ≤ F x) (hInitial_value_le : F (x̂ 0) ≤ γ * Real.sqrt (n : ℝ) * fStar) : (T : ℝ) ≤ 1 + Real.log (γ * Real.sqrt (n : ℝ))

Algorithm 7.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.12: for a feasible set P ⊆ E, a concave function f on P, a barrier term F, a canonical auxiliary maximizer u^*_β(s) for the owner Argmaxβ P F β s, and an available subgradient map ∇f, a dual barrier subgradient method is determined by positive parameter sequences β₀, β₁, β₂, ... and λ₀, λ₁, λ₂, ...; the dual iterates s₀, s₁, s₂, ... ∈ E* are then defined recursively by s₀ = 0, x_k = u^*_{β_k}(s_k), and s_{k+1} = s_k + λ_k ∇f(x_k) for every k.

universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
structure DualBarrierSubgradientMethod (P : Set E) (f : E → ℝ) where
  /-- The barrier/prox term used in the auxiliary maximization problem `Argmaxβ`. -/
  F : E → ℝ
  /-- The canonical auxiliary maximizer `u^*_β(s)` for the barrier-smoothed support problem. -/
  uStar : {β : ℝ // 0 < β} → StrongDual ℝ E → P
  /-- Each chosen point is the canonical maximizer of the auxiliary problem owned by `Argmaxβ`. -/
  uStar_argmax :
    ∀ (β : {β : ℝ // 0 < β}) (s : StrongDual ℝ E),
      (uStar β s : E) ∈ Argmaxβ P F β s
  /-- The auxiliary problem has the chosen point as its unique maximizer. -/
  uStar_unique :
    ∀ (β : {β : ℝ // 0 < β}) (s : StrongDual ℝ E) {u : E},
      u ∈ Argmaxβ P F β s → u = (uStar β s : E)
  /-- The objective `f` is concave on the feasible set `P`. -/
  concaveOn_objective : ConcaveOn ℝ P f
  /-- The available primal subgradient vector `x ↦ ∇f(x)` on `P`. -/
  subgradient : P → E
  /-- Each chosen vector is a genuine concave subgradient of `f` at the corresponding feasible
  point. -/
  subgradient_spec :
    ∀ x : P, IsConcaveSubgradientAt f (x : E) (subgradient x)
  /-- The positive barrier parameters `β₀, β₁, β₂, ...`. -/
  beta : ℕ → {β : ℝ // 0 < β}
  /-- The positive stepsizes `λ₀, λ₁, λ₂, ...`. -/
  stepSize : ℕ → {t : ℝ // 0 < t}

Definition 7.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.12: if A has full column rank, then the dual norm of the induced Euclidean seminorm is g ↦ √⟪g, (Aᵀ A)⁻¹ g⟫.

open Matrix open Seminorm open scoped BigOperators variable {m n : ℕ} local notation "Eₘ" => EuclideanSpace ℝ (Fin m) local notation "Eₙ" => EuclideanSpace ℝ (Fin n) theorem dualNorm_matrixInducedEuclideanSeminorm_eq_sqrt_inverse_gram (A : Matrix (Fin m) (Fin n) ℝ) (hA : Function.Injective A.toEuclideanLin) (g : Eₙ) : by let _ : Seminorm.IsNorm (matrixInducedEuclideanSeminorm A : Seminorm ℝ Eₙ) := matrixInducedEuclideanSeminorm_isNorm A hA exact (matrixInducedEuclideanSeminorm A).dualNorm g = Real.sqrt (inner ℝ g (((A.transpose * A)⁻¹).toEuclideanLin g))

Lemma 7.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.12: with the canonical weighted averages \bar w_k = (1 / S_k) ∑_{i=0}^k λ_i w(x_i) and \bar x_k = (1 / S_k) ∑_{i=0}^k λ_i x_i, one has η(\bar w_k) - f(\bar x_k) ≤ (1 / S_k) ℓ_k^⋆.

open scoped BigOperators
universe u v
variable {E : Type u} {U : Type v}
variable [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable [AddCommGroup U] [Module ℝ U]
theorem barrierSubgradientAverageDualityGap_le_maximalGap
    {P : Set E} {f : E → ℝ} {representation : SaddlePointRepresentation ↥P U} {w : P → U}
    (hobjective_eq : ∀ y : P, representation y = f y)
    (hf_concave : ConcaveOn ℝ P f)
    (hsaddle_convex : ∀ y : P, ConvexOn ℝ Set.univ (representation.saddleFunction y))
    (x : ℕ → P) (subgradient : ℕ → E) (lam : ℕ → ℝ) (k : ℕ)
    (hlam_nonneg : ∀ i ∈ Finset.range (k + 1), 0 ≤ lam i)
    (hlam_sum_pos : 0 < barrierSubgradientWeightSum lam k)
    (hsubgradient_model :
      ∀ i ∈ Finset.range (k + 1), ∀ y : P,
        representation.saddleFunction y (w (x i)) - representation (x i) ≤
          inner ℝ (subgradient i) ((y : E) - (x i : E))) :
    maximalValueOn (Set.univ : Set ↥P)
        (fun y ↦
          representation.saddleFunction y
            ((Finset.range (k + 1)).centerMass lam fun i ↦ w (x i))) -
        f ((Finset.range (k + 1)).centerMass lam fun i ↦ (x i : E)) ≤
      barrierSubgradientMaximalGap x subgradient lam k / barrierSubgradientWeightSum lam k

Proposition 7.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.12 (2): the support function of the symmetric hull conv {±aᵢ} is exactly the finite maximum of the absolute pairings maxᵢ |⟪aᵢ, x⟫|.

open Matrix open scoped EllipsoidNotation PositiveDefMatrixNorm SupportFunction universe u v variable {ι : Type u} variable {E : Type v} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable [Fintype ι] [Nonempty ι] theorem supportFunction_convexHull_range_union_neg_toReal_eq_maxTypeObjective_absInner (a : ι → E) (x : E) : (ξ[convexHull ℝ (Set.range a ∪ Set.range fun i : ι ↦ -a i)] x).toReal = maxTypeObjective (fun i y ↦ |inner ℝ (a i) y|) x

Theorem 7.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.12 (1): if every generated point \hat x_t is feasible, feasible points have objective value at least f*, and the initial value satisfies f(\hat x_0) ≤ 2 √n f*, then the stopping time satisfies T ≤ 1 + log (2 √n).

open scoped MatrixGameRelativeScaleNotation StandardSimplex variable {m n : ℕ+} local notation "Δₙ" => Δ[(n : ℕ)] local notation "PosMat" => { G : Matrix (Fin (n : ℕ)) (Fin (n : ℕ)) ℝ // Matrix.PosDef G } local notation "DiagPosMat" => { G : Matrix (Fin (n : ℕ)) (Fin (n : ℕ)) ℝ // Matrix.IsDiag G ∧ Matrix.PosDef G } local notation "Solver" => (Δₙ → ℝ) → ℝ → Set Δₙ → PosMat → Δₙ → ℕ → Δₙ variable {S : Solver} {f : Δₙ → ℝ} {fμ : ℝ → Δₙ → ℝ} {D : DiagPosMat} {δ fStar : ℝ} {feasibleSet : Set Δₙ} local notation "x̂" => x̂[m; S; f; fμ; D | δ] theorem matrixGameRelativeScale_stoppingTime_le (hTerminate : matrixGameRelativeScaleTerminates m S f fμ D δ) (hGenerated_feasible : ∀ t : ℕ, x̂ t ∈ feasibleSet) (hOptimal_value_le_of_feasible : ∀ (x : Δₙ) (_hx : x ∈ feasibleSet), fStar ≤ f x) (hfStar_pos : 0 < fStar) (hInitial_value_le : f (x̂ 0) ≤ 2 * Real.sqrt (n : ℝ) * fStar) : (matrixGameRelativeScaleStoppingTime hTerminate : ℝ) ≤ 1 + Real.log (2 * Real.sqrt (n : ℝ))

Algorithm 7.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.13: a primal update scheme on P₀ with prescribed subgradients subgradient i = ∇f(x_i), prox-function prox, positive parameters M and v, and initial point x₀ = x0 is a sequence x_k in P₀ with x₀ = x0 such that, for every k ≥ 0, x_{k+1} maximizes the canonical prox-linear stage payoff, equivalently the textbook objective.

open scoped BigOperators universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] structure PrimalUpdateScheme (P0 : Set E) (subgradient : ℕ → E) (prox : E → ℝ) (M v : NNRealˣ) (x0 : E) where /-- The feasible iterate sequence generated by the primal-update rule. -/ x : ℕ → P0 /-- The zeroth iterate is the prescribed initial point `x₀`. -/ x_zero : (x 0 : E) = x0 /-- Each successor iterate maximizes the canonical stage-`k` prox-linear payoff over `P₀`. -/ step_isMax : ∀ k : ℕ, IsMaxOn (primalUpdatePayoff subgradient prox M v k) P0 (x (k + 1) : E)

Definition 7.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.13: for ρ ≥ 0, the bounded feasible set Q₁(ρ) is the subset of the feasible set Q₁ consisting of the points whose distance from x₀ is at most ρ.

universe u variable {E : Type u} [PseudoMetricSpace E] def boundedFeasibleSet (Q1 : Set E) (x0 : E) (ρ : ℝ) : Set E := Q1 ∩ Metric.closedBall x0 ρ

Lemma 7.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.13: if F is a ν-self-concordant barrier on interior Q and ψ is a positive concave function there, then at every interior point x where ψ has gradient ∇ ψ x, the dual local norm of that gradient with respect to the barrier Hessian of F is bounded by the value ψ x.

open InnerProductSpace
open scoped Gradient HessianDualLocalNorm DikinEllipsoidNotation
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
theorem dualLocalNorm_gradient_le_value_of_concaveOn_pos
    {Q : Set E} {ν : NNReal} {F ψ : E → ℝ} {x : E}
    (hF : IsSelfConcordantBarrierOnWith (interior Q) ν F)
    (hx : x ∈ interior Q)
    (hgrad : HasGradientAt ψ (∇ ψ x) x)
    (hψ_concave : ConcaveOn ℝ (interior Q) ψ)
    (hψ_pos : ∀ ⦃y : E⦄, y ∈ interior Q → 0 < ψ y)
    (hH : (hessian F x).det ≠ 0) :
    let hPos := hF.toIsStandardSelfConcordantOn.hessian_isPositive hx
    HessianDualLocalNorm.ofDetNeZero F x hPos hH ((toDual ℝ E) (∇ ψ x)) ≤ ψ x

Proposition 7.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.13: for a finite family aᵢ in a real inner product space and a positive smoothing parameter μ, the symmetric smoothing of x ↦ max_i |⟪a_i, x⟫| lies between that max and the same max plus μ log (2 * Fintype.card ι) at every point x.

universe u
variable {ι : Type u} [Fintype ι] [Nonempty ι]
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem maxTypeObjective_absInner_smoothing_bounds
    (a : ι → E) (μ : {μ : ℝ // 0 < μ}) (x : E) :
    maxTypeObjective (fun i y ↦ |inner ℝ (a i) y|) x ≤ absLinearLogSumExp μ a x ∧
      absLinearLogSumExp μ a x ≤
        maxTypeObjective (fun i y ↦ |inner ℝ (a i) y|) x +
          (μ : ℝ) * Real.log (2 * Fintype.card ι)

Theorem 7.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.13: if x₀ is a constrained analytic center of the strict feasible region hatP ∩ interior Q, if xStar maximizes ℓ on hatP ∩ Q, if xBeta maximizes the barrier-regularized payoff on hatP ∩ interior Q, and if every open segment from x₀ to a feasible point of hatP ∩ Q stays in the strict feasible region and satisfies the displayed barrier estimate, then the actual optimal value ℓ⋆ is bounded above by the smoothed value ℓ⋆(β) plus the explicit logarithmic error term.

universe u
open scoped ConstrainedArgmin
variable {E : Type u} [TopologicalSpace E] [AddCommGroup E] [Module ℝ E]
variable {hatP Q : Set E} {F : E → ℝ} {x0 xStar xBeta : E}
variable {ℓ : AffineMap ℝ E ℝ} {β v : ℝ}
local notation:max "ℓ⋆" =>
  maximalValueOn (hatP ∩ Q) ℓ
local notation "P₀" => hatP ∩ interior Q
local notation "Φβ" => affineBarrierRegularizedPayoff x0 β ℓ F
local notation:max "ℓ⋆β" =>
  maximalValueOn P₀ Φβ
theorem optimal_value_le_smoothed_value_log_barrier_bound
    (hβ : 0 < β) (hv : 0 < v)
    (hx0 : x0 ∈ argmin[P₀] F)
    (hxStar_mem : xStar ∈ hatP ∩ Q)
    (hxStar_max : IsMaxOn ℓ (hatP ∩ Q) xStar)
    (hxBeta_mem : xBeta ∈ P₀)
    (hxBeta_max : IsMaxOn Φβ P₀ xBeta)
    (hsegment_mem :
      ∀ ⦃x : E⦄, x ∈ hatP ∩ Q → ∀ ⦃α : ℝ⦄, α ∈ Set.Ico (0 : ℝ) 1 →
        x0 + α • (x - x0) ∈ P₀)
    (hF_segment :
      ∀ ⦃x : E⦄, x ∈ hatP ∩ Q → ∀ ⦃α : ℝ⦄, α ∈ Set.Ico (0 : ℝ) 1 →
        F (x0 + α • (x - x0)) ≤ F x0 - v * Real.log (1 - α)) :
    ℓ⋆ ≤
      ℓ⋆β +
        β * v *
          (1 + 2 * Real.log
            (1 + Real.sqrt (((ℓ⋆β).toReal - ℓ x0) / (β * v))))

Algorithm 7.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.14: a barrier subgradient method for maximizing a positive differentiable function ψ over a feasible set P₀ relative to a reference function F and positive parameter v consists of an initial point x₀ ∈ P₀ and a feasible iterate sequence x_k such that each successor x_{k+1} maximizes the displayed relative-scale model over P₀.

open scoped BigOperators Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] [FiniteDimensional ℝ E] structure BarrierSubgradientMethod (P0 : Set E) (F ψ : E → ℝ) (v : NNRealˣ) (x0 : P0) where /-- The barrier function `ψ` is differentiable on `P₀`. -/ ψ_differentiableOn : DifferentiableOn ℝ ψ P0 /-- The barrier function `ψ` is strictly positive on `P₀`. -/ ψ_pos : ∀ ⦃x : E⦄, x ∈ P0 → 0 < ψ x /-- The feasible iterate sequence `x₀, x₁, x₂, ...`. -/ iterate : ℕ → P0 /-- The zeroth iterate is the prescribed initial point `x₀`. -/ iterate_zero : iterate 0 = x0 /-- Each successor iterate `x_{k+1}` maximizes the step objective over `P₀`. -/ step_isMax : ∀ k : ℕ, IsMaxOn (barrierSubgradientStepObjective F ψ v x0 iterate k) P0 (iterate (k + 1) : E)

Definition 7.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.14: for \hatρ = (1 / γ₀(F)) f(x₀), the lower-value function sends u to the canonical constrained optimal value of x ↦ ⟪A x, u⟫ on Q₁(\hatρ). Using `optimalValue : EReal` keeps the source minimum faithful even when the feasible slice is empty or the linear objective is unbounded below.

universe u v variable {X : Type u} [NormedAddCommGroup X] [NormedSpace ℝ X] variable {U : Type v} [NormedAddCommGroup U] [InnerProductSpace ℝ U] def relativeScaleLowerValueFunction (gamma0F : ℝ) (Q1 : Set X) (A : X →ₗ[ℝ] U) (f : X → ℝ) (x0 : X) : U → EReal := fun u ↦ (relativeScaleLowerValueProblem gamma0F Q1 A f x0 u).optimalValue

Lemma 7.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.14: if ψ is concave and strictly positive on interior Q, and its gradient has pointwise pointNorm-dual norm at most ψ x, then at every x ∈ interior Q the gradient of x ↦ ln (ψ x) yields, after the standard sign flip, a constrained subgradient of y ↦ - ln (ψ y) over interior Q, written on the chapter notation `-∇ (logarithmicTransform ψ) x ∈ ∂[interior Q] (-logarithmicTransform ψ) (x)`, and this same canonical witness has pointNorm-dual norm at most 1; equivalently the negated logarithmic transform belongs to the barrier subgradient class with bound 1; moreover x ↦ ln (ψ x) is concave on interior Q.

open scoped Gradient WithTopConvexAnalysis universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] [FiniteDimensional ℝ E] theorem logarithmicTransform_has_constrained_subgradient_norm_le_one_and_concaveOn {Q : Set E} {ψ : E → ℝ} {pointNorm : interior Q → Seminorm ℝ E} (hpointNorm : ∀ x : interior Q, Seminorm.IsNorm (pointNorm x)) (hψ_grad : ∀ x : interior Q, HasGradientAt ψ (∇ ψ x) x) (hψ_concave : ConcaveOn ℝ (interior Q) ψ) (hψ_pos : ∀ x : interior Q, 0 < ψ x) (hψ_dual_bound : ∀ x : interior Q, let _ : Seminorm.IsNorm (pointNorm x) := hpointNorm x (pointNorm x).dualNorm (∇ ψ x) ≤ ψ x) : (∀ x : interior Q, -∇ (logarithmicTransform ψ) x ∈ ∂[interior Q] (-logarithmicTransform ψ) (x) ∧ (let _ : Seminorm.IsNorm (pointNorm x) := hpointNorm x (pointNorm x).dualNorm (-∇ (logarithmicTransform ψ) x) ≤ 1)) ∧ (fun y ↦ -logarithmicTransform ψ y) ∈ barrierSubgradientClass (interior Q) (interior Q) pointNorm hpointNorm 1 ∧ ConcaveOn ℝ (interior Q) (logarithmicTransform ψ)

Proposition 7.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.14 (1): for μ > 0, the smoothing function f_μ(x) = μ log (∑ᵢ [exp (⟪aᵢ, x⟫ / μ) + exp (-⟪aᵢ, x⟫ / μ)]) is twice continuously differentiable on a real inner product space.

open scoped BigOperators Gradient
universe u v
variable {ι : Type u}
variable {E : Type v} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable [Fintype ι]
theorem absLinearLogSumExp_contDiff
    (μ : {μ : ℝ // 0 < μ}) (a : ι → E) :
    ContDiff ℝ 2 (absLinearLogSumExp μ a)

Theorem 7.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.14: if method.F is a genuine self-concordant barrier on P in the source sense, so in particular it has the boundary-growth property HasBarrierBoundaryGrowthOn P method.F and P has nonempty frontier, and the barrier-subgradient iterates x_k ∈ P have local ratios (λ_k / β_k) ‖g_k‖*_(x_k) < 1 and the smoothing parameters satisfy β_k ≤ β_{k+1}, then for every k ≥ 0 the maximal-gap owner method.maximalGap k is bounded by A_k + β_{k+1} ν [1 + 2 log (1 + sqrt (A_k / (β_{k+1} ν)) + 3 (S_k / β_{k+1}) ‖g₀‖*_(x₀))], where x₀ = method 0, g₀ is the chosen subgradient at x₀, S_k = ∑_{i=0}^k λ_i, and A_k = ∑_{i=0}^k β_i ω_* ((λ_i / β_i) ‖g_i‖*_(x_i)).

open scoped BigOperators ConstrainedArgmin DikinEllipsoidNotation Gradient HessianDualLocalNorm
  HessianLocalNorm
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
namespace DualBarrierSubgradientMethod
variable {P : Set E} {f : E → ℝ}
variable (method : DualBarrierSubgradientMethod P f)
theorem maximalGap_upper_bound
    (ν : NNReal)
    [IsSelfConcordantBarrierOnWith P ν method.F]
    (hboundary : HasBarrierBoundaryGrowthOn P method.F)
    (hfront : (frontier P).Nonempty)
    (hH : ∀ i : ℕ, (hessian method.F (method i : E)).det ≠ 0)
    (hω :
      ∀ i : ℕ,
        (method.stepSize i : ℝ) *
            HessianDualLocalNorm.ofDetNeZero method.F (method i : E)
              (method.iterate_hessian_isPositive i) (hH i)
              (method.dualSubgradient (method i)) <
          method.beta i)
    (hβ_mono : ∀ i : ℕ, (method.beta i : ℝ) ≤ method.beta (i + 1))
    (k : ℕ) :
    let A := method.accumulatedOmegaStarError hH hω k
    let S := barrierSubgradientWeightSum (fun i ↦ (method.stepSize i : ℝ)) k
    let δ0 :=
      HessianDualLocalNorm.ofDetNeZero method.F (method 0 : E)
        (method.iterate_hessian_isPositive 0) (hH 0)
        (method.dualSubgradient (method 0))
    method.maximalGap k ≤
      A +
        (method.beta (k + 1) : ℝ) * (ν : ℝ) *
          (1 +
            2 * Real.log
              (1 +
                Real.sqrt (A / ((method.beta (k + 1) : ℝ) * (ν : ℝ))) +
                3 * ((S / (method.beta (k + 1) : ℝ)) * δ0)))

Algorithm 7.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.15: a symmetric matrix X can serve as the next iterate for the semidefinite-cone scheme at a strict-cone auxiliary matrix A if A admits an orthogonal tridiagonal reduction A = U T Uᵀ and X is a feasible maximizer of the canonical semidefinite subproblem attached to the induced factor matrix √T Uᵀ, which still factorizes A in the sense of Lemma 7.15.

open Matrix
open scoped MatrixOrder RealSymmetricMatrixSpace
variable {n : ℕ}
local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ
local notation "SymmMat" => 𝕊^n
open IsOrthogonalTridiagonalReduction
def IsSemidefiniteConeNextIterate
    (A : 𝕊^n₊₊) (X : SymmMat) : Prop :=
  ∃ (U : Matrix.orthogonalGroup (Fin n) ℝ) (T : SymmMat),
    IsOrthogonalTridiagonalReduction (A : SymmMat) U T ∧
      X ∈ factorizationSemidefiniteFeasibleSet ∧
        IsMaxOn
          (factorizationSemidefiniteObjective (factor U T))
          factorizationSemidefiniteFeasibleSet
          X

Definition 7.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.15 is the Chapter 6 regularized-supremum owner specialized to the matrix-to-dual map x ↦ (u ↦ ⟪Ax, u⟫), zero smooth terms, and the Euclidean prox term d₂(u) = (1 / 2) ‖u‖² = quadraticDistanceTo 0 u.

open Matrix variable {m n : ℕ} local notation "Eₘ" => EuclideanSpace ℝ (Fin m) local notation "Eₙ" => EuclideanSpace ℝ (Fin n) variable (Q2 : Set Eₘ) (A : Matrix (Fin m) (Fin n) ℝ) (μ : {μ : ℝ // 0 < μ}) (x : Eₙ) recall smoothedPrimalObjective

Lemma 7.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.15: if A = Lᵀ L, then the value ψ⋆ = inf {∑ᵢ uᵢ⁻¹ | diag(u) ≤ A⁻¹, uᵢ > 0} admits the semidefinite representation sup {([∑ᵢ √(qᵢᵀ X qᵢ)]^2) | X ⪰ 0, trace X = 1}, where qᵢ are the columns of L.

open Matrix
open scoped BigOperators MatrixOrder RealSymmetricMatrixSpace
variable {n : ℕ}
local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ
local notation "Eₙ" => Fin n → ℝ
local notation "SymmMat" => 𝕊^n
theorem factorizationDiagonalInverseRelaxationValue_eq_semidefiniteRelaxationValue
    (A : 𝕊^n₊₊) (L : Mₙ) (hA : ((A : SymmMat) : Mₙ) = Lᵀ * L) :
    factorizationDiagonalInverseRelaxationValue A =
      factorizationSemidefiniteRelaxationValue L

Proposition 7.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.15: if ‖aᵢ‖_G^* ≤ ν √n for every i, then the Hessian quadratic form of f_μ(x) = μ log ∑ᵢ (exp(⟪aᵢ, x⟫ / μ) + exp(-⟪aᵢ, x⟫ / μ)) is bounded above by (ν² n / μ) ‖h‖_G². The C² regularity is already the owner theorem absLinearLogSumExp_contDiff from Proposition_7_14.

open scoped Gradient PositiveDefMatrixNorm SmoothConvex
variable {m n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
variable (a : Fin m → E) (G : {G : Matrix (Fin n) (Fin n) ℝ // G.PosDef}) {ν : ℝ}
variable (μ : {μ : ℝ // 0 < μ})
variable (ha : ∀ i : Fin m, ‖a i‖[G,*] ≤ ν * Real.sqrt n)
include a G ν μ ha
-- Proof sketch: combine Proposition 7.14 with the chapter owner `positiveDefMatrixNorm`: the
-- smoothness is `absLinearLogSumExp_contDiff`, the Hessian quadratic form is
-- `absLinearLogSumExp_hessian_quadraticForm_eq`, and the weighted dual-norm bound on the `aᵢ`
-- controls the second-moment term by `ν² n / μ`.
theorem absLinearLogSumExp_hessian_quadraticForm_le (x h : E) :
    inner ℝ (hessian (absLinearLogSumExp μ a) x h) h ≤
      (((ν ^ (2 : ℕ)) * (n : ℝ)) / (μ : ℝ)) * ‖h‖[G] ^ (2 : ℕ)

Theorem 7.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.15: under the Chapter 7 parameter choice (7.3.19), if method.F is a genuine ν-self-concordant barrier on P in the Chapter 5 sense, then the normalized maximal gap of a DualBarrierSubgradientMethod is bounded by the explicit closed-form rate.

open Filter
open scoped Gradient HessianDualLocalNorm
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
namespace DualBarrierSubgradientMethod
variable {P : Set E} {f : E → ℝ}
theorem maximalGap_le_explicit_rate
    (method : DualBarrierSubgradientMethod P f)
    (M ν : NNReal) [IsSelfConcordantBarrierForWith P ν method.F]
    [HasPositiveDefiniteHessianOn P method.F]
    (hν : 0 < (ν : ℝ))
    (hdual :
      ∀ x : P,
        HessianDualLocalNorm.ofPosDefMem method.F x.2 (method.dualSubgradient x) ≤ (M : ℝ))
    (hstep : ∀ i : ℕ, (method.stepSize i : ℝ) = barrierSubgradientLambda i)
    (hbeta : ∀ i : ℕ, (method.beta i : ℝ) = barrierSubgradientBeta M ⟨(ν : ℝ), hν⟩ i)
    (k : ℕ) :
    method.maximalGap k /
      barrierSubgradientWeightSum (fun i ↦ (method.stepSize i : ℝ)) k ≤
      ((2 * (M : ℝ) *
          (Real.sqrt ((ν : ℝ) / ((k : ℝ) + 1)) + (ν : ℝ) / ((k : ℝ) + 1)) *
            (1 + Real.log (2 + (3 / 2 : ℝ) * Real.sqrt ((ν : ℝ) * ((k : ℝ) + 1)))) : ℝ))

Algorithm 7.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.16: given an initial point x₀ ∈ P, a finite-horizon payoff family ψ₀, …, ψ_{N-1}, and a horizon N, an uncertain-environment barrier subgradient method is a finite run x₀, …, x_N such that for each stage k = 0, …, N - 1, the next iterate x_{k+1} maximizes the displayed averaged relative-scale model with barrier penalty over P. The self-concordant-barrier hypothesis on F is part of later theorem layers, not primitive run data.

open scoped BigOperators Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] structure UncertainEnvironmentBarrierSubgradientMethod (P : Set E) (F : E → ℝ) (ν : NNRealˣ) (N : ℕ) (ψ : Fin N → E → ℝ) (x0 : P) where /-- Each payoff `ψ_i` from the finite horizon is differentiable on the feasible set `P`. -/ ψ_differentiableOn (i : Fin N) : DifferentiableOn ℝ (ψ i) P /-- Each payoff `ψ_i` from the finite horizon is strictly positive on the feasible set `P`. -/ ψ_pos (i : Fin N) {x : E} (hx : x ∈ P) : 0 < ψ i x /-- The finite feasible iterate trace `x₀, …, x_N`. -/ iterate : Fin (N + 1) → P /-- The zeroth iterate is the prescribed initial point `x₀`. -/ iterate_zero : iterate 0 = x0 /-- For each stage `k : Fin N`, the successor iterate `x_{k+1}` maximizes the averaged relative-scale objective with barrier penalty over `P`. Feasibility is carried by the subtype trace `iterate : Fin (N + 1) → P`. -/ step_isMax (k : Fin N) : IsMaxOn (uncertainEnvironmentBarrierStepObjective F ψ ν x0 iterate k) P (iterate k.succ : E)

Definition 7.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.16: the homogeneous linear-programming feasible set and optimal value are the existing Chapter 7 owners attached to (hatA, c).

open Matrix
variable {m n : ℕ}
local notation "Eₘ" => EuclideanSpace ℝ (Fin m)
variable (hatA : Matrix (Fin m) (Fin (n - 1)) ℝ) (c : Eₘ)
recall homogeneousLinearProgrammingFeasibleSet

Lemma 7.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.16, affine form: for an explicit whole-space subgradient h ∈ ∂[Set.univ] f(g x), the strict-positivity inequality for the affine pullback holds with the pulled-back vector g.linear.adjoint h.

open scoped WithTopConvexAnalysis universe u v variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable {F : Type v} [NormedAddCommGroup F] [InnerProductSpace ℝ F] [FiniteDimensional ℝ F] namespace StrictlyPositiveOn theorem inequality_comp_affineMap_image_adjoint {Qx : Set F} {f : F → ℝ} (hf : StrictlyPositiveOn Qx f) (g : E →ᵃ[ℝ] F) {x y : E} (hx : x ∈ g ⁻¹' Qx) (hy : y ∈ g ⁻¹' Qx) {h : F} (hh : h ∈ ∂[Set.univ] f((g x))) : 0 ≤ f (g y) + f (g x) + inner ℝ (g.linear.adjoint h) (y - x)

Proposition 7.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.16: if scheme is the accelerated projected-gradient run S(φ, L, Q, G, x₀, N) with positive horizon N ≥ 1, and the chosen gradient field is L-Lipschitz with respect to the weighted norm ‖·‖[G] and dual norm ‖·‖[G,*] on the feasible set, then the output point scheme.outputPoint = x_N satisfies φ(x_N) - φ(xStar) ≤ 2 L ‖x₀ - xStar‖[G]^2 / (N (N + 1)) for every minimizer xStar of φ on Q.

open scoped BigOperators ConstrainedArgmin PositiveDefMatrixNorm open scoped Gradient variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) namespace AcceleratedConvexMinimizationScheme theorem outputPoint_suboptimality_le {N : ℕ} (scheme : AcceleratedConvexMinimizationScheme n N) (hN : 1 ≤ N) (hgradient_lipschitz : ∀ ⦃x y : E⦄, x ∈ scheme.problem.feasibleSet → y ∈ scheme.problem.feasibleSet → ‖scheme.gradient x - scheme.gradient y‖[scheme.metricMatrix,*] ≤ (scheme.smoothness : ℝ) * ‖x - y‖[scheme.metricMatrix]) {xStar : E} (hxStar : xStar ∈ argmin[scheme.problem.feasibleSet] scheme.problem) : scheme.problem scheme.outputPoint - scheme.problem xStar ≤ (2 * (scheme.smoothness : ℝ) * ‖scheme.initialPoint - xStar‖[scheme.metricMatrix] ^ (2 : ℕ)) / ((N : ℝ) * ((N : ℝ) + 1))

Theorem 7.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.16: if the averaged logarithmic loss of the positive iterates relative to the positive optimum ψ⋆ is bounded by the explicit Chapter 7 rate δ_k, then the geometric mean of the first k + 1 iterate values is at least ψ⋆ exp (-δ_k) and therefore also at least ψ⋆ (1 - δ_k).

open scoped BigOperators universe u variable {X : Type u} theorem positiveIterateGeometricMean_relative_accuracy_of_log_rate (ψ : X → {r : ℝ // 0 < r}) (x : ℕ → X) (ψStar : {r : ℝ // 0 < r}) {ν : ℝ} (k : ℕ) (hlog_rate : Real.log (ψStar : ℝ) - (Finset.sum (Finset.range (k + 1)) fun i ↦ Real.log (ψ (x i) : ℝ)) / ((k : ℝ) + 1) ≤ barrierSubgradientRelativeAccuracyDelta ν k) : positiveIterateGeometricMean ψ x k ≥ (ψStar : ℝ) * Real.exp (-barrierSubgradientRelativeAccuracyDelta ν k) ∧ positiveIterateGeometricMean ψ x k ≥ (ψStar : ℝ) * (1 - barrierSubgradientRelativeAccuracyDelta ν k)

Algorithm 7.17

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 7.17: given a feasible set P of ambient Euclidean portfolio vectors whose points all lie in the simplex slice P̂ₙ, an ambient barrier term F, a positive parameter ν, an initial feasible portfolio x₀, and strictly positive price-relative vectors cₖ ∈ ℝⁿ_{++}, a barrier-based portfolio-weight update algorithm is a sequence x₀, x₁, x₂, ... such that for each k ≥ 0 the next iterate xₖ₊₁ maximizes the displayed averaged relative-growth objective with barrier penalty over P. Any self-concordant-barrier hypothesis on F belongs to later theorem layers, not to the primitive run data.

open EuclideanSpace (nonnegativeOrthant positiveOrthant) open scoped BigOperators StandardSimplex variable {n : ℕ} local notation "Eₙ" => EuclideanSpace ℝ (Fin n) local notation "Δₙ" => Δ[n] local notation "P̂ₙ" => (EuclideanSpace.equiv (Fin n) ℝ) ⁻¹' Δₙ structure BarrierPortfolioWeightUpdateAlgorithm (P : Set Eₙ) (F : Eₙ → ℝ) (ν : NNRealˣ) (x0 : P) (c : ℕ → positiveOrthant n) where /-- Every feasible point of `P` is a simplex-valued portfolio weight vector in the Euclidean carrier `Eₙ`. -/ subset_portfolioWeightSet : P ⊆ P̂ₙ /-- The feasible iterate sequence `x₀, x₁, x₂, ...`. -/ iterate : ℕ → P /-- The zeroth iterate is the prescribed feasible point `x₀`. -/ iterate_zero : iterate 0 = x0 /-- For every iteration `k`, the next portfolio weight vector `xₖ₊₁` maximizes the objective from Algorithm 7.17 over the feasible set `P`. -/ step_isMax : ∀ k : ℕ, IsMaxOn (portfolioBarrierStepObjective F ν x0 c iterate k) P (iterate (k + 1) : Eₙ)

Definition 7.17

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.17: for X ∈ 𝕊^n, the spectral radius is the real number ρ(X).

open RealSymmetricMatrixSpace open scoped RealSymmetricMatrixSpace variable {n : ℕ} local notation "Mat" => Matrix (Fin n) (Fin n) ℝ variable (n : ℕ) #check (fun X : 𝕊^n ↦ ρ(X))

Lemma 7.17

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.17: the real-valued support-function surface x ↦ (ξ[S] x).toReal of a nonempty bounded centrally symmetric set is strictly positive on the whole space in the sense of Definition 7.81. At this owner level, closedness is redundant because the support function depends only on the closed convex hull of S, while nonemptiness is essential to keep the .toReal bridge faithful.

open scoped SupportFunction open scoped WithTopConvexAnalysis universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] theorem supportFunction_strictlyPositiveOn_univ_of_nonempty_bounded_centrallySymmetric (S : Set E) (hS_nonempty : S.Nonempty) (hS_bounded : Bornology.IsBounded S) (hS_centrallySymmetric : ∀ ⦃s : E⦄, s ∈ S → -s ∈ S) : StrictlyPositiveOn Set.univ (fun x ↦ (ξ[S] x).toReal)

Proposition 7.17

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.17: under the standard side conditions used by the Chapter 7 method, one obtains a certified centrally symmetric rounding run for ∂f(0) = conv {± aᵢ}.

open Asymptotics Filter
open scoped EllipsoidNotation PositiveDefMatrixNorm WeightedGramMatrix
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
theorem exists_centralSymmetryRoundingAlgorithm_of_maxAbsLinearSubdifferential_stoppingIndex_le
    {m : ℕ+} {γ : ℝ} (a : Fin (m : ℕ) → E) (hn : 1 ≤ n) (hγ : 1 < γ)
    (hGram : (centralSymmetryGramMatrix a).PosDef) :
    ∃ certificate : MaxAbsLinearSubdifferentialRoundingCertificate a γ, True

Theorem 7.17

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.17: the explicit barrier-subgradient relative-accuracy term tends to 0 as the horizon tends to infinity. This is the source theorem's final “in particular” conclusion after the relative-efficiency inequality above.

open scoped BigOperators universe u variable {X : Type u} theorem barrierSubgradientRelativeAccuracyDelta_tendsto_zero (ν : NNReal) : Filter.Tendsto (fun N : ℕ ↦ barrierSubgradientRelativeAccuracyDelta (ν : ℝ) N) Filter.atTop (nhds 0)

Definition 7.18

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.18: from symmetric coefficient matrices A₁, …, Aₚ, the induced objective maps x ∈ ℝᵖ to the spectral radius of the linear matrix combination ∑ᵢ xᵢ Aᵢ.

open scoped RealSymmetricMatrixSpace variable {p n : ℕ} local notation "Eₚ" => EuclideanSpace ℝ (Fin p) local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ local notation "SymmMat" => 𝕊^n def spectralRadiusObjective (coeffMatrices : Fin p → SymmMat) : Eₚ → ℝ := fun x ↦ (spectralRadius ℝ ((linearMatrixCombination fun i ↦ (coeffMatrices i : Mₙ)) x)).toReal

Lemma 7.18

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.18: if the canonical WithTop ℝ lifts of f₁ and f₂ are closed convex and each is strictly positive on Q, then every nonnegative linear combination α₁ • f₁ + α₂ • f₂ is strictly positive on Q.

open scoped Pointwise WithTopConvexAnalysis
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem StrictlyPositiveOn.nonnegative_linear_combination
    {Q : Set E} {f₁ f₂ : E → ℝ}
    (hf₁ : StrictlyPositiveOn Q f₁) (hf₂ : StrictlyPositiveOn Q f₂)
    (hcc₁ : ClosedConvexFunction (fun x ↦ (f₁ x : WithTop ℝ)))
    (hcc₂ : ClosedConvexFunction (fun x ↦ (f₂ x : WithTop ℝ)))
    {α₁ α₂ : ℝ} (hα₁ : 0 ≤ α₁) (hα₂ : 0 ≤ α₂) :
    StrictlyPositiveOn Q (α₁ • f₁ + α₂ • f₂)

Proposition 7.18

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.18: viewed in the canonical owner EReal, the packing value ψ* is the reciprocal of the normalized gauge infimum on the slice ⟪c, y⟫ = 1, with the reciprocal taken in ℝ≥0∞ so a zero infimum yields ⊤.

open EuclideanSpace (nonnegativeOrthant)
open scoped StandardSimplex
variable {n : ℕ} {m : ℕ+}
local notation "E" => EuclideanSpace ℝ (Fin n)
local notation "Δₙ" => Δ[n]
namespace LinearPackingProblem

-- Proof sketch: use `problem.mem_feasibleSet_iff` to rewrite feasibility as the coordinatewise
-- inequalities `⟪a_i, y⟫ ≤ b_i`, then divide by the positive owner data `b_i > 0` and collect the
-- resulting family through `maxTypeObjective_le_iff`.
theorem optimalValue_eq_inv_normalizedMin
    (problem : LinearPackingProblem (m : ℕ) n) :
    problem.optimalValue =
      (((sInf ((fun y ↦ ENNReal.ofReal (problem.gauge y)) '' problem.normalizedSlice))⁻¹ :
          ENNReal) : EReal)

Theorem 7.18

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.18: if Δ is the least upper bound of the scenario-wise gap v ↦ f (x v) v - f xStatic v of a decision rule relative to a static strategy, then for every scenario u the gap at u is bounded above by Δ. This is the distribution-free worst-case guarantee relative to the static strategy.

universe u v variable {Scenario : Type u} {Decision : Type v} theorem pointwise_gap_le_of_isLUB_worst_case_gap_against_static_strategy (f : Decision → Scenario → ℝ) (x : Scenario → Decision) (xStatic : Decision) {Δ : ℝ} (hΔ : IsLUB (Set.range fun v : Scenario ↦ f (x v) v - f xStatic v) Δ) (u : Scenario) : f (x u) u - f xStatic u ≤ Δ

Definition 7.19

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.19: spectral_eigenvalue_l1_unit_ball n is the set Q₂ of real symmetric n × n matrices whose ordered eigenvalues satisfy ∑ i, |λ_i(X)| ≤ 1.

open RealSymmetricMatrixSpace open scoped BigOperators RealSymmetricMatrixSpace variable {n : ℕ} def spectral_eigenvalue_l1_unit_ball (n : ℕ) : Set (𝕊^n) := {X | ∑ i : Fin n, |eigenvalues X i| ≤ (1 : ℝ)} -- Proof sketch: unfold `spectral_eigenvalue_l1_unit_ball`; membership is exactly the displayed -- eigenvalue `ℓ₁`-bound from the definition of `Q₂`.

Lemma 7.19

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.19: if f₁ is strictly positive on Q, then the pointwise maximum of f₁ and f₂ is strictly positive on Q. In particular, this applies when both functions are strictly positive.

universe u variable {Q : Type u} -- Proof sketch: evaluate at an arbitrary `x : Q`; from `hf x` we get `0 < f₁ x`, and since -- `f₁ x ≤ max (f₁ x) (f₂ x)`, transitivity gives positivity of the function-space maximum. theorem StrictlyPositive.max {f₁ : Q → ℝ} (hf : StrictlyPositive f₁) (f₂ : Q → ℝ) : StrictlyPositive (max f₁ f₂)

Proposition 7.19

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.19: for a finite nonempty family aᵢ in a real inner product space, the log-sum-exp smoothing of the support function of Set.range a lies between (ξ[Set.range a] x).toReal and the same quantity plus μ log (Fintype.card ι) at every point x, for every positive smoothing parameter μ.

open scoped SupportFunction universe u v variable {ι : Type u} [Fintype ι] [Nonempty ι] variable {E : Type v} [NormedAddCommGroup E] [InnerProductSpace ℝ E] local notation "smoothMaxInnerApproximation" => smoothMaxInnerApproximationLocal theorem supportFunction_range_toReal_smoothing_bounds (a : ι → E) (μ : {μ : ℝ // 0 < μ}) (x : E) : (ξ[Set.range a] x).toReal ≤ smoothMaxInnerApproximation a μ x ∧ smoothMaxInnerApproximation a μ x ≤ (ξ[Set.range a] x).toReal + (μ : ℝ) * Real.log (Fintype.card ι)

Theorem 7.19

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.19 (Strict positivity of the augmented function): if φ : Q → ℝ is convex on the feasible set Q and every feasible constrained subgradient of φ has dual norm at most L, then the source augmented function x ↦ max (φ x) (L * p x) is strictly positive on Q in the sense of Definition 7.81.

open scoped WithTopConvexAnalysis
open scoped SeminormDualNorm
open scoped NormalCone
open scoped ConstrainedArgmin
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem strictlyPositiveOn_max_of_subgradientWithin_dualNorm_le
    (Q : Set E) [FiniteDimensional ℝ E]
    (p : Seminorm ℝ E) [Seminorm.IsNorm p]
    (φ : Q → ℝ) (L : ℝ)
    (hφ_convex : ConvexOn ℝ Q (zeroExtensionOn Q φ)) (hL_nonneg : 0 ≤ L)
    (hsubgradient_bound :
      ∀ ⦃x g : E⦄,
        x ∈ Q →
        g ∈ ∂[Q] (zeroExtensionOn Q φ)(x) →
        p.dualNorm g ≤ L) :
    StrictlyPositiveOnSubtype Q (augmentedFunctionOn p φ L)

Definition 7.20

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.20: on 𝕊^n, the Frobenius inner product is the Chapter 5 owner RealSymmetricMatrixSpace.frobeniusInner.

open Matrix
open scoped BigOperators RealSymmetricMatrixSpace
variable (n : ℕ)
#check (RealSymmetricMatrixSpace.frobeniusInner : 𝕊^n → 𝕊^n → ℝ)

Lemma 7.20

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.20: if f is strictly positive on Q, then for every x, y ∈ Q and every whole-space subgradient g ∈ ∂[Set.univ] f(x), the transformed objective satisfies the nonlinear lower-support inequality f̂ y ≥ f̂ x + ⟪ĝ[f; x] g, y - x⟫ + (1 / 2) * ⟪g, y - x⟫^2.

open scoped WithTopConvexAnalysis universe u variable {X : Type u} open scoped RelativeScaleTransformNotation variable {V : Type u} [NormedAddCommGroup V] [InnerProductSpace ℝ V] -- Proof sketch: rewrite `f̂` as `(1 / 2) * f^2` and -- `ĝ[f; x] g` as `f(x) • g`, then apply -- `StrictlyPositiveOn.inequality` to get `f y ≥ -(f x + ⟪g, y - x⟫)`. Squaring the resulting -- lower bound and expanding the square yields the displayed estimate. theorem relativeScaleTransformedObjective_nonlinear_lower_support {Q : Set V} {f : V → ℝ} (hstrict : StrictlyPositiveOn Q f) {x y g : V} (hx : x ∈ Q) (hy : y ∈ Q) (hg : g ∈ ∂[Set.univ] f(x)) : f̂ y ≥ f̂ x + inner ℝ (ĝ[f; x] g) (y - x) + (1 / 2 : ℝ) * (inner ℝ g (y - x)) ^ 2

Proposition 7.20

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.20: if a₁, …, aₘ ∈ ℝⁿ₊ and hat f(x) = maxᵢ ∑ⱼ aᵢⱼ |xⱼ|, then ∂ hat f(0) is the sign-symmetric convex hull Conv (⋃ i, B(aᵢ)).

open EuclideanSpace (nonnegativeOrthant)
open scoped BigOperators SupportFunction SymmetricBox WithTopConvexAnalysis
variable {n : ℕ} {m : ℕ+}
local notation "E" => EuclideanSpace ℝ (Fin n)
local notation "SignPattern" => Fin n → Bool
theorem subdifferential_zero_maxWeightedAbsoluteCoordinateSum_eq_signSymmetricConvexHull
    {a : Fin (m : ℕ) → E} (ha : ∀ i : Fin (m : ℕ), a i ∈ nonnegativeOrthant n) :
    ∂ (fun x : E ↦
        (maxWeightedAbsoluteCoordinateSumOfOrthant a ha x : WithTop ℝ))(0) =
      signSymmetricConvexHull a

Theorem 7.20

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.20: if φ satisfies the uniform Lipschitz bound |φ x - φ y| ≤ L ‖x - y‖ on Q, with x₀ ∈ Q and L, R > 0, then the local objective x ↦ max {φ(x) - φ(x₀) + 2LR, L ‖x - x₀‖} is strictly positive at every feasible point of Q.

universe u open scoped ConstrainedArgmin variable {E : Type u} [SeminormedAddCommGroup E] variable {Q : Set E} {φ : E → ℝ} {x₀ : E} {L R : ℝ} theorem localStrictlyPositiveObjective_strictlyPositive (hx₀ : x₀ ∈ Q) (hL : 0 < L) (hR : 0 < R) (hφ_lipschitz : LipschitzOnWith (Real.toNNReal L) φ Q) {x : E} (hx : x ∈ Q) : 0 < localStrictlyPositiveObjective φ x₀ L R x

Definition 7.21

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.21: the quadratic form of linearMatrixGramOperator is the Frobenius norm square of the associated matrix combination.

open Matrix open scoped BigOperators variable {p n : ℕ} local notation "Eₚ" => EuclideanSpace ℝ (Fin p) local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ theorem linearMatrixGramOperator_quadratic_form (coeffMatrices : Fin p → Mₙ) (x : Eₚ) : inner ℝ (linearMatrixGramOperator coeffMatrices x) x = ∑ i : Fin n, ∑ j : Fin n, ((linearMatrixCombination coeffMatrices x) i j) * ((linearMatrixCombination coeffMatrices x) i j)

Lemma 7.21

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.21: if the estimating functions satisfy the one-step upper recursion ψ_{k+1}(x) ≤ ψ_k(x) + a_k \hat f(x) on Q, with A₀ = 0 and A_{k+1} = A_k + a_k, then ψ_k(x) ≤ A_k \hat f(x) + ψ_0(x) for every x ∈ Q. This is the global estimating property obtained from the nonlinear lower-support inequality used in the quasi-Newton method.

universe u variable {X : Type u} {α : Type*} [Semiring α] [PartialOrder α] [IsOrderedRing α] -- Proof sketch: argue by induction on `k`. The base case uses `A 0 = 0`. For the inductive step, -- combine the one-step estimate `ψ (k + 1) x ≤ ψ k x + a k * hatF x` with the inductive -- hypothesis and then rewrite the coefficient of `hatF x` using `A (k + 1) = A k + a k`. theorem estimating_function_le_weighted_transformed_objective_add_initial {Q : Set X} {hatF : X → α} {ψ : ℕ → X → α} {A a : ℕ → α} (hA0 : A 0 = 0) (hA_succ : ∀ k : ℕ, A (k + 1) = A k + a k) (hpsi_succ : ∀ k : ℕ, ∀ ⦃x : X⦄, x ∈ Q → ψ (k + 1) x ≤ ψ k x + a k * hatF x) (k : ℕ) (x : X) (hx : x ∈ Q) : ψ k x ≤ A k * hatF x + ψ 0 x

Proposition 7.21

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.21: if the sign-symmetric box-hull support function of a nonnegative family (a i)_{i ∈ ι} is bounded on the nonnegative orthant by 2 √n ‖·‖_D for a diagonal positive-definite matrix D, then the Hessian quadratic form of the log-sum-exp smoothing smoothMaxInnerApproximation a μ is bounded by (4 n / μ) ‖h‖_D².

open EuclideanSpace (nonnegativeOrthant)
open scoped BigOperators Gradient PositiveDefMatrixNorm SmoothConvex SupportFunction
variable {n : ℕ} {ι : Type*} [Fintype ι] [Nonempty ι]
local notation "E" => EuclideanSpace ℝ (Fin n)
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
variable (a : ι → E)
variable (D : {D : Mat // D.PosDef}) (μ : {μ : ℝ // 0 < μ})
theorem smoothMaxInnerApproximation_hessian_quadratic_form_le
    (ha_nonneg : ∀ i, a i ∈ nonnegativeOrthant n)
    (hDdiag : D.1.IsDiag)
    (hBoxSupport :
      ∀ v : E, v ∈ nonnegativeOrthant n →
        (ξ[signSymmetricConvexHull a] v).toReal ≤ 2 * Real.sqrt n * ‖v‖[D])
    (x h : E) :
    inner ℝ (hessian (smoothMaxInnerApproximation a μ) x h) h ≤
      (4 : ℝ) * n / μ.1 * ‖h‖[D] ^ 2

Theorem 7.21

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 7.21: for the high-order method in relative scale, if \hat f(x) = (1 / 2) f(x)^2, the quasi-Newton estimating-sequence analysis provides the standard one-step bound for the best points x_k^* together with the exponential lower bound on A_{k+1}, then `(1 - δ) \hat f(x_k^*) ≤ \hat f(x^*) + L^2 ‖x₀ - x^*‖_{G₀}^2 / (2 n (e^{δ (k + 1) / n} - 1))for everyδ > 0`.

open scoped PositiveDefMatrixNorm RelativeScaleTransformNotation variable {n : ℕ+} local notation "E" => EuclideanSpace ℝ (Fin (n : ℕ)) variable {f : E → ℝ} variable {G0 : {G : Matrix (Fin (n : ℕ)) (Fin (n : ℕ)) ℝ // G.PosDef}} variable {x0 xStar : E} {δ : ℝ} {L : NNRealˣ} variable {A : ℕ → ℝ} theorem relativeScaleHighOrderMethod_best_point_bound {x0 : E} {xBest : ℕ → E} (hδ : 0 < δ) (hbest : ∀ k : ℕ, (1 - δ) * f̂ (xBest k) ≤ f̂ xStar + (‖x0 - xStar‖[G0] ^ (2 : ℕ)) / (2 * A (k + 1))) (hA_lower : ∀ k : ℕ, ((n : ℝ) / ((L : ℝ) ^ (2 : ℕ))) * (Real.exp (δ * ((k + 1 : ℕ) : ℝ) / (n : ℝ)) - 1) ≤ A (k + 1)) (k : ℕ) : (1 - δ) * f̂ (xBest k) ≤ f̂ xStar + (((L : ℝ) ^ (2 : ℕ)) * ‖x0 - xStar‖[G0] ^ (2 : ℕ)) / (2 * (n : ℝ) * (Real.exp (δ * ((k + 1 : ℕ) : ℝ) / (n : ℝ)) - 1))

Definition 7.22

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.22: a truss topology design problem consists of node positions in ℝ², arcs joining a free node to a later node, and external forces on the free nodes. The free nodes are indexed by Fin n, the fixed nodes occupy the remaining indices in Fin (n + p), and the strictly positive simplex weights used for the design objective are introduced below. The endpoint positions of each arc are required to be distinct, so the normalized bar directions are well-defined.

open Matrix
open scoped BigOperators
structure TrussTopologyDesignProblem (n p m : ℕ) where
  /-- The positions of all free and fixed nodes in `ℝ²`. -/
  nodePosition : Fin (n + p) → EuclideanSpace ℝ (Fin 2)
  /-- The tail of each arc, required to be a free node. -/
  tail : Fin m → Fin n
  /-- The head of each arc, allowed to be either free or fixed. -/
  head : Fin m → Fin (n + p)
  /-- Each arc joins its free tail to a later node, matching the condition `j_k > i_k`. -/
  tail_lt_head : ∀ k, ((tail k : Fin n) : ℕ) < (head k : ℕ)
  /-- Each arc has nonzero geometric length, so its endpoint positions are distinct. -/
  endpointPosition_ne :
    ∀ k,
      nodePosition (Fin.castLE (Nat.le_add_right n p) (tail k)) ≠ nodePosition (head k)
  /-- The external forces applied at the free nodes. -/
  externalForce : Fin n → EuclideanSpace ℝ (Fin 2)

Lemma 7.22

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.22: if the transformed subgradient norm at the updated metric G_{k+1} scales by f(x_k)^2, the rank-one metric update sends the squared dual norm of g_k from G_k to (1 - δ) times its old value, the accuracy parameter satisfies δ ≠ 1, and the step size a_k satisfies the displayed reciprocal norm identity, then the algorithmic progress identity (1 / 2) a_k^2 ‖ĝ[f; x_k] g_k‖_{G_{k+1}}^{*2} = δ a_k f̂ x_k holds.

open scoped RelativeScaleTransformNotation universe u v theorem algorithmic_progress_identity {X : Type u} [SMul ℝ X] {Metric : Type v} (dualNormSq : Metric → X → ℝ) {Gk GkNext : Metric} {f : X → ℝ} {xk gk : X} {a δ : ℝ} (hδ : δ ≠ 1) (htransformed_norm : dualNormSq GkNext (ĝ[f; xk] gk) = (f xk) ^ (2 : ℕ) * dualNormSq GkNext gk) (hmetric_update : dualNormSq GkNext gk = (1 - δ) * dualNormSq Gk gk) (hstep : dualNormSq Gk gk = δ / ((1 - δ) * a)) : (1 / 2 : ℝ) * a ^ (2 : ℕ) * dualNormSq GkNext (ĝ[f; xk] gk) = δ * a * f̂ xk

Proposition 7.22

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.22: if F_p satisfies the pointwise bounds (1 / 2) ρ(X)^2 ≤ F_p(X) ≤ (1 / 2) ρ(X)^2 (rank X)^(1 / p) on real symmetric matrices, then the induced infimum f_p* = inf_y F_p(A y), read as the real part of the canonical owner optimal value on a nonempty feasible type Q, satisfies (1 / 2) φ*^2 ≤ f_p* ≤ (1 / 2) φ*^2 r^(1 / p), where φ* = inf_y ρ(A y) is read in the same way and r = sup_y rank(A y).

open Matrix open scoped RealSymmetricMatrixSpace open scoped Pointwise universe u variable {n : ℕ} local notation "SymmMat" => 𝕊^n theorem inducedObjectiveInf_bounds {Q : Type u} [Nonempty Q] (p : ℕ+) (F_p : SymmMat → ℝ) (A : Q → SymmMat) (h_lower : ∀ X, (1 / 2 : ℝ) * ρ(X) ^ (2 : ℕ) ≤ F_p X) (h_upper : ∀ X, F_p X ≤ (1 / 2 : ℝ) * ρ(X) ^ (2 : ℕ) * ((Matrix.rank (X : Matrix (Fin n) (Fin n) ℝ) : ℝ) ^ (1 / (p : ℝ)))) : (1 / 2 : ℝ) * (inducedRadiusInf A).toReal ^ (2 : ℕ) ≤ (inducedObjectiveInf F_p A).toReal ∧ (inducedObjectiveInf F_p A).toReal ≤ (1 / 2 : ℝ) * (inducedRadiusInf A).toReal ^ (2 : ℕ) * ((inducedRankSup A : ℝ) ^ (1 / (p : ℝ)))

Definition 7.23

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.23 in owner form: a positive-definite matrix G induces the canonical seminorm x ↦ √⟪Gx, x⟫ on ℝⁿ.

open Matrix variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) def positiveDefMatrixNorm (G : Matrix (Fin n) (Fin n) ℝ) (hG : G.PosDef) : Seminorm ℝ E := LinearMap.BilinForm.primalSeminorm (matrixBilin G) (matrixToBilinForm_posDef_of_posDef G hG)

Lemma 7.23

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 7.23: if the optimal values ψStar k = ψ_k^* of the quasi-Newton estimating functions satisfy the one-step lower recursion induced by the update (7.4.12) and the progress identity (7.4.15), then ψ_k^* ≥ (1 - δ) * ∑_{i=0}^{k-1} a_i \hat f(x_i). Here hatF k abbreviates \hat f(x_k) and dualGradNormSq k abbreviates (\| \hat g(x_k) \|_{G_{k+1}}^*)^2.

open scoped BigOperators variable {α : Type*} [Field α] [LinearOrder α] [IsStrictOrderedRing α] theorem quasiNewtonEstimatingOptimalValue_lower_bound (ψStar a hatF dualGradNormSq : ℕ → α) (δ : α) (hzero : 0 ≤ ψStar 0) (hupdate : ∀ k : ℕ, ψStar (k + 1) ≥ ψStar k + a k * hatF k - (1 / 2 : α) * (a k) ^ (2 : ℕ) * dualGradNormSq k) (hprogress : ∀ k : ℕ, (1 / 2 : α) * (a k) ^ (2 : ℕ) * dualGradNormSq k = δ * a k * hatF k) (k : ℕ) : ψStar k ≥ (1 - δ) * (∑ i ∈ Finset.range k, a i * hatF i)

Proposition 7.23

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.23: if p is a positive smoothing order, f_p lies between (1 / 2) φ^2 and (1 / 2) r^(1 / p) φ^2 on the feasible set Q, and yBar ∈ Q is (1 + δ)-optimal for f_p, then yBar is also (1 + δ)-optimal for φ, with both optimal values read from the canonical Chapter 1 constrained optimization owner and projected back to ℝ via .toReal.

universe u variable {X : Type u} open scoped Pointwise theorem relative_accuracy_transfer_from_fp_to_phi (Q : Set X) (φ f_p : X → ℝ) (δ r : ℝ) (p : ℕ+) (yBar : X) (hyBar_mem : yBar ∈ Q) (hδ : 0 < δ) (hφ_nonneg : ∀ y ∈ Q, 0 ≤ φ y) (h_lower : ∀ y ∈ Q, (1 / 2 : ℝ) * φ y ^ (2 : ℕ) ≤ f_p y) (h_upper : ∀ y ∈ Q, f_p y ≤ (1 / 2 : ℝ) * Real.rpow r (1 / (p : ℝ)) * φ y ^ (2 : ℕ)) (hp : ((1 + δ) / δ) * Real.log r ≤ (p : ℝ)) (hyBar : f_p yBar ≤ (1 + δ) * ((.mk Q f_p : SetConstrainedMinimizationProblem X).optimalValue).toReal) : φ yBar ≤ (1 + δ) * ((.mk Q φ : SetConstrainedMinimizationProblem X).optimalValue).toReal

Definition 7.24

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.24 reuses the existing convex-body owner supportFunctionReal.

open scoped SupportFunction universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] recall ConvexBody.supportFunctionReal {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] (C : ConvexBody E) : E → ℝ

Proposition 7.24

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.24 in source-facing owner form: if the Hessian quadratic form of f is nonnegative and bounded above by (2p - 1) times the squared pullback seminorm induced by A : ι → M, then the gradient is bounded by the induced dual seminorm of that Gram seminorm. The surface statement depends only on the explicit coefficient (2 * p - 1), so no separate assumption 1 ≤ p is part of the owner API.

open scoped BigOperators Gradient SupportFunction universe u v variable {ι : Type v} [Fintype ι] variable {M : Type u} [NormedAddCommGroup M] [InnerProductSpace ℝ M] local notation "Eι" => EuclideanSpace ℝ ι theorem gradient_familyInducedEuclideanDualSeminorm_le_of_hessian_quadratic_form_bounded {f : Eι → ℝ} {p : ℝ} {A : ι → M} (hf_C2 : ContDiff ℝ 2 f) (hessian_quadratic_form_bounded : ∀ y h : Eι, 0 ≤ inner ℝ (hessian f y h) h ∧ inner ℝ (hessian f y h) h ≤ (2 * p - 1) * familyInducedEuclideanSeminorm A h ^ (2 : ℕ)) : ∀ y z : Eι, familyInducedEuclideanDualSeminorm A (∇ f y - ∇ f z) ≤ ((2 * p - 1) * familyInducedEuclideanSeminorm A (y - z) : EReal)

Definition 7.25

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.25 uses the chapter-level notation Δ[n] for the canonical simplex owner.

open scoped StandardSimplex variable (n : ℕ) #check (Δ[n] : Set (Fin n → ℝ))

Proposition 7.25

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.25 [Quadratic lower bound and distance bound]. The payload authority for this repo snapshot quotes all three displayed consequences (7.u556), (7.u557), and (7.u558). The third clause (7.u558) is false without an additional geometric side condition, and there is no local source/ file authorizing which missing hypothesis should be added here. The source-facing owner therefore stays as a blocked check-only surface for the full quoted proposition, while the valid clauses and the convex repair remain auxiliary API below.

open scoped ConstrainedArgmin
open scoped RealSymmetricMatrixSpace
open scoped PositiveDefMatrixNorm
variable {m n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin m)
variable (r p : ℕ+)
variable (G : {G : Matrix (Fin m) (Fin m) ℝ // G.PosDef})
variable (X : E → 𝕊^n) (f : E → ℝ)
variable
  (h_rank_norm_comparison : ∀ M : 𝕊^n,
      Matrix.rank (M : Matrix (Fin n) (Fin n) ℝ) ≤ (r : ℕ) →
        (1 / (r : ℝ)) * ⟪M, M⟫_F ≤ ρ(M) ^ (2 : ℕ) ∧
          ρ(M) ^ (2 : ℕ) ≤ 2 * squaredLpMatrixNormSmoothing p M)
  (hXrank : ∀ y : E, Matrix.rank (X y : Matrix (Fin n) (Fin n) ℝ) ≤ (r : ℕ))
  (hf : ∀ y : E, f y = squaredLpMatrixNormSmoothing p (X y))
  (hGnorm : ∀ y : E, ‖y‖[G] = ρ(X y))
include p X h_rank_norm_comparison hXrank hf hGnorm
#check
  (∀ y : E, (1 / (2 * (r : ℝ))) * ‖y‖[G] ^ (2 : ℕ) ≤ f y) ∧
    (∀ {Q : Set E} {yStar : E},
      yStar ∈ argmin[Q] f →
        (1 / (2 * (r : ℝ))) * ‖yStar‖[G] ^ (2 : ℕ) ≤
          ((.mk Q f : SetConstrainedMinimizationProblem E).optimalValue).toReal) ∧
    (∀ {Q : Set E} {yStar x0 : E},
      yStar ∈ argmin[Q] f →
        x0 ∈ argmin[Q] (fun y : E ↦ ‖y‖[G]) →
          (1 / 2 : ℝ) * ‖yStar - x0‖[G] ^ (2 : ℕ) ≤
            (r : ℝ) * ((.mk Q f : SetConstrainedMinimizationProblem E).optimalValue).toReal)

Definition 7.26

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.26: the ellipsoid W_r(v, G) is the set of points s in ℝⁿ whose G-dual distance from the center v is at most r, namely ⟪G⁻¹ (s - v), s - v⟫ ^ (1 / 2) ≤ r.

open Matrix open scoped EllipsoidNotation PositiveDefMatrixNorm variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ def matrixEllipsoid (G : Mat) (v : E) (r : ℝ) : Set E := {s | Real.sqrt (inner ℝ ((toEuclideanLin G⁻¹) (s - v)) (s - v)) ≤ r}

Proposition 7.26

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.26: if the iterates x_k satisfy the displayed gap estimate f_p(x_k) - f_p^* ≤ 16 (1 + δ) r log r / (δ k (k + 1)) * f_p^*, f_p^* is nonnegative, and every iterate with k ≥ (4 / δ) * sqrt ((1 + δ) r log r) satisfies the relative-accuracy bound f_p(x_k) ≤ (1 + δ) f_p^*.

universe u variable {Q : Type u} theorem fp_relative_accuracy_of_iteration_gap_bound (f_p : Q → ℝ) (δ r fStar : ℝ) (x : ℕ → Q) {k : ℕ} (hδ : 0 < δ) (hr : 1 < r) (hfStar_nonneg : 0 ≤ fStar) (hgap : ∀ n : ℕ, 1 ≤ n → f_p (x n) - fStar ≤ ((16 : ℝ) * (1 + δ) * r * Real.log r) / (δ * (n : ℝ) * (n + 1)) * fStar) (hk : (4 / δ) * Real.sqrt ((1 + δ) * r * Real.log r) ≤ (k : ℝ)) : f_p (x k) ≤ (1 + δ) * fStar

Definition 7.27

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.27: the ellipsoid W₁(v,G) is a β-rounding of C when the unit ellipsoid W₁(v,G) is contained in C and C is contained in the dilated ellipsoid W_β(v,G).

open scoped EllipsoidNotation variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ structure IsBetaRounding (C : Set E) (β : ℝ) (G : Mat) (v : E) : Prop where /-- The unit ellipsoid `W₁(v,G) = E(G, v)` lies inside `C`. -/ unit_ellipsoid_subset : E(G, v) ⊆ C /-- The set `C` lies inside the outer ellipsoid `W_β(v,G)`. -/ subset_beta_ellipsoid : C ⊆ W[β](v, G)

Proposition 7.27

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.27: if Trace(X_k) ≠ 0, then the power-of-two specialization of squaredLpMatrixNormSmoothing has gradient ∇ f_{2^k}(y)^(i) = (2 f_{2^k}(y) / Trace(X_k)) * Trace(Y_k Aᵢ).

open scoped BigOperators Gradient
open Matrix
open RealSymmetricMatrixSpace
open scoped RealSymmetricMatrixSpace
open scoped Matrix.Norms.Frobenius
open scoped RightActions
variable {m n : ℕ}
local notation "Eₘ" => EuclideanSpace ℝ (Fin m)
local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ
local notation "SymmMat" => 𝕊^n
theorem squaredLpMatrixNormSmoothing_powerOfTwo_hasGradientAt
    (k : ℕ+) (A : Fin m → SymmMat) (y : Eₘ)
    (htrace :
      Matrix.trace (repeatedSquaringX (symmetricLinearMatrixCombination A y : Mₙ) (k : ℕ)) ≠ 0) :
    HasGradientAt
      (fun y' ↦
        squaredLpMatrixNormSmoothing (powerOfTwoSmoothingOrder k)
          (symmetricLinearMatrixCombination A y'))
      ((EuclideanSpace.equiv (Fin m) ℝ).symm <| fun i : Fin m ↦
        ((2 : ℝ) *
            squaredLpMatrixNormSmoothing (powerOfTwoSmoothingOrder k)
              (symmetricLinearMatrixCombination A y) /
            Matrix.trace
              (repeatedSquaringX (symmetricLinearMatrixCombination A y : Mₙ) (k : ℕ))) *
          Matrix.trace
              (repeatedSquaringY (symmetricLinearMatrixCombination A y : Mₙ) (k : ℕ) *
              (A i : Mₙ)))
      y

Definition 7.28

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.28 recalls the primal weighted norm owner positiveDefMatrixNorm.

open Matrix open scoped EllipsoidNotation PositiveDefMatrixNorm variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ #check positiveDefMatrixNorm

Proposition 7.28

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.28 [Gradient of U_β]: assume x₀ ∈ hatP and every dual point s admits a unique canonical maximizer u^*_β(s) in `Argmaxβ hatP F β s. Then the source-facing owner Uβ hatP F x0 β : StrongDual ℝ E → ℝ` is differentiable, and its derivative at s is evaluation at u^*_β(s) - x₀.

open Filter
open scoped Topology Gradient WithTopConvexAnalysis
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
variable (hatP : Set E) (F : E → ℝ) (x0 : E) (β : {β : ℝ // 0 < β})
theorem supportFunctionApproximation_differentiable_and_hasFDerivAt_of_unique_argmax
    (hx0 : x0 ∈ hatP)
    (uStar : StrongDual ℝ E → E)
    (huStar : ∀ s : StrongDual ℝ E, uStar s ∈ Argmaxβ hatP F β s)
    (huStar_unique :
      ∀ s : StrongDual ℝ E, ∀ u : E, u ∈ Argmaxβ hatP F β s → u = uStar s) :
    Differentiable ℝ (Uβ hatP F x0 β) ∧
      ∀ s : StrongDual ℝ E,
        HasFDerivAt (Uβ hatP F x0 β)
          (ContinuousLinearMap.apply ℝ ℝ (uStar s - x0)) s

Definition 7.29

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.29: for a convex centrally symmetric body C ⊆ ℝⁿ, an ellipsoidal rounding of radius γ √n is a positive-definite matrix G such that the unit centered ellipsoid W₁(G) is contained in C and C is contained in W_(γ √n)(G).

open Matrix open scoped EllipsoidNotation variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ abbrev IsEllipsoidalRounding (C : Set E) (gamma : ℝ) (G : Mat) : Prop := G.PosDef ∧ IsBetaRounding C (gamma * Real.sqrt (n : ℝ)) G (0 : E)

Proposition 7.29

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.29: for a concave objective on the feasible set of the barrier subgradient method, the weighted average of the values f(x_i) over the first k + 1 iterates, written canonically as a Finset.centerMass, is within ℓ_k⋆ / S_k of the maximal value f_* = maximalValueOn P f, where ℓ_k⋆ is barrierSubgradientMaximalGap ... k and S_k = barrierSubgradientWeightSum ... k.

open scoped BigOperators
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
theorem barrierSubgradientMethod_primal_efficiency_estimate
    {P : Set E} {f : E → ℝ}
    (method : DualBarrierSubgradientMethod P f) (k : ℕ) :
    maximalValueOn P f -
        (((Finset.range (k + 1)).centerMass
            (fun i ↦ (method.stepSize i : ℝ))
            (fun i ↦ f (method i)) : ℝ) : EReal) ≤
      method.maximalGap k /
        barrierSubgradientWeightSum (fun i ↦ (method.stepSize i : ℝ)) k

Definition 7.30

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.30: for a positive-definite matrix G on ℝⁿ and a vector g ∈ ℝⁿ, the set C_g(G) is the convex hull of the weighted unit ball W₁(G) = E(G⁻¹, 0) together with the point g.

open Matrix open scoped EllipsoidNotation PositiveDefMatrixNorm SupportFunction variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ def convexHullOfWeightedUnitBallAndPoint (G : {G : Mat // G.PosDef}) (g : E) : Set E := convexHull ℝ (E(G.1⁻¹, 0) ∪ ({g} : Set E))

Proposition 7.30

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.30: if the logarithmic primal-dual gap at the canonical weighted aggregates barx and barU is bounded by \ell_k^\star / S_k, then ψ(barx) ≥ ψ^\star(barU) \exp(-\ell_k^\star / S_k). Here barx is the arithmetic mean of the iterates and barU is their inverse-ψ weighted dual center of mass.

universe u v variable {E : Type u} {E₁ : Type v} variable [AddCommGroup E] [Module ℝ E] variable [AddCommGroup E₁] [Module ℝ E₁] variable {P : Set E} {Ω : Set E₁} variable (ψ : P → { r : ℝ // 0 < r }) (u : P → E₁) (ψStar : Ω → { r : ℝ // 0 < r }) variable {k : ℕ} (x : Fin (k + 1) → P) local notation "barx" => Finset.univ.centroid ℝ (fun i ↦ (x i : E)) local notation "barU" => Finset.univ.centerMass (fun i ↦ ((ψ (x i) : ℝ)⁻¹)) (fun i ↦ u (x i)) -- Proof sketch: the logarithmic hypothesis is `log (ψ⋆(barU) / ψ(barx)) ≤ ellStar / Sk`. -- Apply `Real.log_le_iff_le_exp` to bound the ratio by `exp (ellStar / Sk)`, then divide by the -- positive factor `exp (ellStar / Sk)` and rewrite with `Real.exp_neg`. theorem primalDualEfficiencyEstimate_of_weightedLogarithmicGap (hbarx_mem : barx ∈ P) (hbarU_mem : barU ∈ Ω) {Sk ellStar : ℝ} (hloggap : ellStar / Sk ≥ Real.log ((ψStar ⟨barU, hbarU_mem⟩ : ℝ) / (ψ ⟨barx, hbarx_mem⟩ : ℝ))) : (ψ ⟨barx, hbarx_mem⟩ : ℝ) ≥ (ψStar ⟨barU, hbarU_mem⟩ : ℝ) * Real.exp (-ellStar / Sk)

Definition 7.31

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.31: for a positive-definite matrix G on ℝⁿ, a vector g ∈ ℝⁿ, and a scalar parameter α, the one-sided updated matrix is (1 - α) G + (α / r + ((r - 1) / 2)^2 (α / r)^2) ggᵀ, where r = ‖g‖*_G. The textbook restriction α ∈ [0, 1] and any later nonvanishing hypotheses are imposed only on the theorem layer.

open Matrix open scoped PositiveDefMatrixNorm variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ def oneSidedRoundingUpdatedMatrix (G : {G : Mat // G.PosDef}) (g : E) (α : ℝ) : Mat := let r := ‖g‖[G,*] (1 - α) • G.1 + ((α / r) + (((r - 1) / 2) ^ (2 : ℕ)) * (α / r) ^ (2 : ℕ)) • vecMulVec g g

Proposition 7.31

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.31: [Equivalent formulations of φ⋆ via ψ] For b ∈ ℝ^m and a positively homogeneous ψ that is strictly positive on the nonzero nonnegative orthant, the value φ⋆ = inf_{y ≥ 0, y ≠ 0} ⟪b, y⟫ / ψ(y) is the reciprocal of the supremum of the reciprocal ratio ψ(y) / ⟪b, y⟫, provided ⟪b, y⟫ > 0 on the nonzero nonnegative orthant. The ambient nonzero-domain assumption is carried by [Nonempty (Fin m)], matching the source's implicit use of min/max over ℝ^m_+ \ {0}.

open EuclideanSpace (nonnegativeOrthant) open SetConstrainedMinimizationProblem variable {m : ℕ} local notation "E" => EuclideanSpace ℝ (Fin m) theorem fractionalCoveringPhiStar_eq_inv_reciprocalPsiSup [Nonempty (Fin m)] (b : E) (ψ : E → ℝ) (hinner_pos : ∀ y : E, y ∈ nonnegativeOrthant m → y ≠ 0 → 0 < inner ℝ b y) (hψ_pos : ∀ y : E, y ∈ nonnegativeOrthant m → y ≠ 0 → 0 < ψ y) : fractionalCoveringPhiStar b ψ = (fractionalCoveringReciprocalPsiSup b ψ)⁻¹

Definition 7.32

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.32: a γ n-rounding of a convex set C ⊆ ℝⁿ with nonempty interior is a center v and a positive-definite matrix G such that γ > 1, the unit ellipsoid W₁(v,G) is contained in C, and C is contained in the outer ellipsoid W_(γ n)(v,G).

open scoped EllipsoidNotation variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mat" => Matrix (Fin n) (Fin n) ℝ structure IsGammaNRounding (C : Set E) (γ : ℝ) (G : Mat) (v : E) : Prop extends IsBetaRounding C (γ * n) G v where /-- The ambient set `C` is convex. -/ convex : Convex ℝ C /-- The rounding parameter satisfies `γ > 1`. -/ one_lt_gamma : 1 < γ /-- The rounding matrix is positive definite. -/ posDef : G.PosDef

Proposition 7.32

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.32: for the maximal concurrent flow problem with capacity vector barf, demands d_{i,j}, and shortest-path costs SP_{i,j}(t), specializing Proposition 7.31 to the dual objective ψ(t) = ∑_{(i,j) ∈ 𝒪𝒟} d_{i,j} SP_{i,j}(t) identifies the dual value λ⋆ with the reciprocal of the supremum of ψ on the normalized nonnegative slice ⟪barf, t⟫ = 1, which is the textbook formula ψ⋆ = λ⋆⁻¹.

open scoped BigOperators
open EuclideanSpace (nonnegativeOrthant)
universe u
variable {m : ℕ} {OD : Type u} [Fintype OD]
local notation "E" => EuclideanSpace ℝ (Fin m)
theorem maximalConcurrentFlow_dualValue_eq_inv_normalizedDualObjectiveSup
    (barf : E) (d : OD → ℝ) (shortestPath : OD → E → ℝ)
    (hbarf_pos_on_orthant :
      ∀ t : E, t ∈ nonnegativeOrthant m → t ≠ 0 → 0 < inner ℝ barf t)
    (hobjective_pos :
      ∀ t : E, t ∈ nonnegativeOrthant m → t ≠ 0 →
        0 < ∑ od, d od * shortestPath od t)
    (hobjective_hom :
      IsPositivelyHomogeneousOn 1 (nonnegativeOrthant m)
        (fun t ↦ ∑ od, d od * shortestPath od t)) :
    fractionalCoveringPhiStar barf (fun t ↦ ∑ od, d od * shortestPath od t) =
      (fractionalCoveringNormalizedPsiSup
        barf (fun t ↦ ∑ od, d od * shortestPath od t))⁻¹

Definition 7.33

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.33: if C is convex, sign-invariance is equivalent to containing the full symmetric box B(fun i ↦ |g i|) for every point g of C.

open scoped Pointwise variable {ι : Type*} local notation "E" => EuclideanSpace ℝ ι open scoped SymmetricBox theorem isSignInvariant_iff_symmetricBox_subset_of_convex [Finite ι] {C : Set E} (hC_convex : Convex ℝ C) : IsSignInvariant C ↔ ∀ g ∈ C, B(fun i ↦ |g i|) ⊆ C

Proposition 7.33

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.33: for a positive-semidefinite symmetric matrix A, the Boolean quadratic optimum f⋆ from Definition 7.70 and the chapter semidefinite-relaxation value ψ⋆ from Definition 7.71 satisfy (2 / π) ψ⋆ ≤ f⋆ ≤ ψ⋆.

open Matrix
open ProbabilityTheory
open scoped Pointwise MatrixOrder RealSymmetricMatrixSpace
variable {n : ℕ}
local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ
local notation "Eₙ" => EuclideanSpace ℝ (Fin n)
theorem booleanQuadraticOptimalValue_two_div_pi_mul_diagonalSemidefiniteRelaxation_le_and_le
    (A : 𝕊^n₊) :
    (2 / Real.pi) * diagonalSemidefiniteRelaxationOptimalValue (A : 𝕊^n) ≤
        booleanQuadraticOptimalValue (A : Mₙ) ∧
      booleanQuadraticOptimalValue (A : Mₙ) ≤
        diagonalSemidefiniteRelaxationOptimalValue (A : 𝕊^n)

Definition 7.34

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.34: the logarithmic potential ellipsoidBoxLogVolumePotential d g α is the coordinate formula -∑ i, log (1 + α (τ_i - 1)).

open Matrix
open scoped BigOperators EllipsoidNotation RealSymmetricMatrixSpace SymmetricBox
variable {n : ℕ}
local notation "Eₙ" => EuclideanSpace ℝ (Fin n)
local notation "Matₙ" => Matrix (Fin n) (Fin n) ℝ
local notation "SymmMatₙ" => 𝕊^n
theorem ellipsoidBoxLogVolumePotential_eq
    (D : Matₙ) (hDpos : D.PosDef) (g : Eₙ) (α : ℝ)
    (hα : α ∈ Set.Ico (0 : ℝ) 1) :
    ellipsoidBoxLogVolumePotential D g α =
      -(∑ i : Fin n, Real.log (1 + α * (ellipsoidBoxCoordinateRatio D g i - 1)))

Proposition 7.34

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.34: for the barrier-subgradient approximation scheme (7.3.33) applied to a concave maximization problem of the form (7.3.29), there exists an iteration schedule N(δ) such that the geometric-mean output after N(δ) steps is a relative-δ approximation of ψ(x⋆), where the method parameter is the same barrier parameter ν that indexes the explicit rate, and N(δ) has soft complexity \tilde O(ν / δ²) as δ ↓ 0.

open Asymptotics
open Filter
open scoped BigOperators Gradient HessianDualLocalNorm
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
  [FiniteDimensional ℝ E]
namespace BarrierSubgradientMethod
variable {P0 : Set E} {F ψ : E → ℝ} {ν : NNRealˣ} {x0 : P0}
variable (method : BarrierSubgradientMethod P0 F ψ ν x0)
theorem exists_relativeScaleDeltaApproximation_schedule
    (xStar : P0) (hoptimal : IsMaxOn ψ P0 xStar)
    [IsSelfConcordantBarrierOnWith P0 (ν : NNReal) F]
    [HasPositiveDefiniteHessianOn P0 F]
    (hψ_concave : ConcaveOn ℝ P0 ψ)
    (hψ_dual_bound :
      ∀ x : P0,
        HessianDualLocalNorm.ofPosDefMem F x.2
            (InnerProductSpace.toDualMap ℝ E (∇ ψ x)) ≤
          ψ x) :
    ∃ N : ℝ → ℕ,
      (∀ ⦃δ : ℝ⦄, 0 < δ →
        IsRelativeScaleDeltaApproximation (ψ xStar) δ
          (method.iterateGeometricMean (N δ))) ∧
        (fun δ ↦ (N δ : ℝ)) =Õ[fun δ ↦ ⌈(ν : ℝ) / δ ^ (2 : ℕ)⌉₊;
          nhdsWithin (0 : ℝ) (Set.Ioi 0)]
          (fun δ ↦ (ν : ℝ) / δ ^ (2 : ℕ))

Definition 7.35

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.35: the sign-symmetric convex set generated by a family of boxes B(aᵢ) is their convex hull Conv {B(aᵢ)}.

open EuclideanSpace (positiveOrthant) open scoped BigOperators SymmetricBox open Matrix Set variable {n : ℕ} variable {ι : Type*} {κ : Type*} local notation "E" => EuclideanSpace ℝ ι def signSymmetricConvexHull (a : κ → E) : Set E := convexHull ℝ (⋃ i : κ, B((a i))) -- Proof sketch: unfold `signSymmetricConvexHull`; the right-hand side is definitionally the convex -- hull of the union of the boxes `B(a_i)`.

Proposition 7.35

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.35 (1): the aggregate objective f₁(x) = ∑ᵢ p (Aᵢ x - bᵢ) is strictly positive on the whole space in the sense of Definition 7.81.

open scoped BigOperators universe u v w variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable {F : Type v} [NormedAddCommGroup F] [InnerProductSpace ℝ F] [FiniteDimensional ℝ F] variable {ι : Type w} [Fintype ι] theorem affineResidualSeminormSum_strictlyPositiveOn (p : Seminorm ℝ F) [p.IsNorm] (A : ι → E →ₗ[ℝ] F) (b : ι → F) : StrictlyPositiveOn Set.univ (fun x ↦ ∑ i : ι, p (A i x - b i))

Definition 7.36

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.36: given vectors a i ∈ ℝ^(n - 1) and scalars c i ∈ ℝ for i = 1, …, m, the linear-programming min-max absolute deviation problem is the unconstrained minimization problem on ℝ^(n - 1) with objective y ↦ maxᵢ |⟪aᵢ, y⟫ - cᵢ|.

open scoped RealInnerProductSpace variable {m n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin (n - 1)) def linearProgrammingMinMaxAbsoluteDeviationProblem (hm : 0 < m) (a : Fin m → E) (c : Fin m → ℝ) : SetConstrainedMinimizationProblem E := .mk Set.univ (minMaxAbsoluteDeviationObjective hm a c)

Proposition 7.36

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.36: if f is nonnegative on Q, then the minimizers of f on Q coincide with the minimizers of the transformed objective f̂, so the two optimization problems are equivalent.

open scoped ConstrainedArgmin RelativeScaleTransformNotation universe u variable {X : Type u} theorem argmin_eq_argmin_relativeScaleTransformedObjective {Q : Set X} {f : X → ℝ} (hf_nonneg : ∀ x ∈ Q, 0 ≤ f x) : argmin[Q] f = argmin[Q] f̂

Definition 7.37

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.37: the conic reformulation min {max_i |⟪a_i, x⟫| | ⟪d, x⟫ = 1} is the canonical constrained minimization problem supportAbsMinProblem a d.

open scoped RealInnerProductSpace
universe u
variable {ι : Type} [Fintype ι] [Nonempty ι]
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable (a : ι → E) (d x : E)
recall supportAbsMinProblem

Proposition 7.37

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.37: if ψ_k is a quadratic estimating function with positive-definite Hessian G_k, then the next Hessian is obtained by the rank-one update G_{k+1} = G_k + (δ / (1 - δ)) * g_k g_kᵀ / ‖g_k‖_{G_k}^{*2}, and its inverse satisfies the Sherman-Morrison identity G_{k+1}^{-1} = G_k^{-1} - δ * G_k^{-1} g_k g_kᵀ G_k^{-1} / ‖g_k‖_{G_k}^{*2}.

open Matrix open scoped PositiveDefMatrixNorm variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) theorem quasiNewtonRankOneHessianUpdate_and_inverse {δ : ℝ} (hδ : δ ∈ Set.Ioo (0 : ℝ) 1) (Gk : {G : Matrix (Fin n) (Fin n) ℝ // G.PosDef}) (gk : E) : quasiNewtonUpdatedHessian δ Gk gk = Gk.1 + ((δ / (1 - δ)) / (‖gk‖[Gk,*] ^ (2 : ℕ))) • Matrix.vecMulVec gk gk ∧ (quasiNewtonUpdatedHessian δ Gk gk)⁻¹ = Gk.1⁻¹ - (δ / (‖gk‖[Gk,*] ^ (2 : ℕ))) • (Gk.1⁻¹ * Matrix.vecMulVec gk gk * Gk.1⁻¹)

Definition 7.38

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.38: for a finite family a : Fin (m : ℕ) → E and a positive parameter μ : {μ : ℝ // 0 < μ}, the textbook log-sum-exp smoothing x ↦ μ log (∑ i, [exp (⟪aᵢ, x⟫ / μ) + exp (-⟪aᵢ, x⟫ / μ)]) is the Chapter 7 owner absLinearLogSumExp μ a.

open scoped BigOperators RealInnerProductSpace
variable {n : ℕ} {m : ℕ+}
local notation "E" => EuclideanSpace ℝ (Fin n)
variable (a : Fin (m : ℕ) → E) (μ : {μ : ℝ // 0 < μ})
#check (absLinearLogSumExp μ a : E → ℝ)

Proposition 7.38

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.38: for ε > 0 and δ > 0, the mixed-accuracy iteration bound N_n(ε, δ) from (7.4.20) is strictly less than the dimension-free bound N_∞(ε, δ) = L² R² / (2 ε δ) whenever L R ≠ 0.

theorem mixedAccuracyIterationCountBound_lt_uniformUpperBound (n : ℕ+) (L R ε δ : ℝ) (hε : 0 < ε) (hδ : 0 < δ) (hLR : L * R ≠ 0) : mixedAccuracyIterationCountBound n L R ε δ < mixedAccuracyUniformIterationCountBound L R ε δ

Definition 7.39

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.39: a composite smooth convex minimization problem consists of a nonempty closed convex feasible set Q ⊆ ℝⁿ, a convex differentiable objective φ : ℝⁿ → ℝ, a positive-definite matrix G defining the weighted norm ‖·‖_G, and a positive constant L such that ‖∇φ(x) - ∇φ(y)‖*_G ≤ L ‖x - y‖_G for all x, y ∈ ℝⁿ. The feasible-set and objective pair is owned canonically by SetConstrainedMinimizationProblem, and the objective-side smoothness data is owned by ConvexC1SeminormSmooth for the weighted seminorm from Definition 7.23.

open scoped Gradient PositiveDefMatrixNorm SmoothConvex variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) structure CompositeSmoothConvexMinimizationProblem (n : ℕ) extends SetConstrainedMinimizationProblem (EuclideanSpace ℝ (Fin n)) where /-- The positive-definite matrix defining the weighted norm `‖·‖_G`. -/ metricMatrix : {G : Matrix (Fin n) (Fin n) ℝ // G.PosDef} /-- The Lipschitz constant `L > 0`, encoded canonically as a positive nonnegative real. -/ lipschitzConstant : NNRealˣ /-- The feasible set `Q` is nonempty. -/ feasibleSet_nonempty : feasibleSet.Nonempty /-- The feasible set `Q` is closed. -/ feasibleSet_closed : IsClosed feasibleSet /-- The feasible set `Q` is convex. -/ feasibleSet_convex : Convex ℝ feasibleSet /-- The objective belongs to the weighted smooth-convex class `𝓕[(L : NNReal), positiveDefMatrixNorm G]¹¹`. -/ objective_smooth : ConvexC1SeminormSmooth (positiveDefMatrixNorm metricMatrix.1 metricMatrix.2) (lipschitzConstant : NNReal) objective

Proposition 7.39

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.39: if δ ∈ (0, 1 / 2), the quasi-Newton best point x_k^* satisfies the estimate (1 - δ) (f(x_k^*) - f^*) f^* ≤ δ \hat f(x^*) + L² R² / (2 n (e^{δ (k + 1) / n} - 1)) with \hat f(x^*) = (1 / 2) (f^*)², and the iteration index k is at least R_n(δ) = (n / δ) log (1 + L² R² / (n δ (1 - 2δ) (f^*)²)), then f(x_k^*) ≤ (1 + δ) f^*.

universe u variable {X : Type u} theorem quasiNewton_bestPoint_relative_accuracy_of_iterationBound (f : X → ℝ) (xkStar : X) (n : ℕ+) (δ L R fStar : ℝ) (k : ℕ) (hδ : δ ∈ Set.Ioo (0 : ℝ) (1 / 2)) (hfStar : 0 < fStar) (hEstimate : (1 - δ) * (f xkStar - fStar) * fStar ≤ δ * ((1 / 2 : ℝ) * fStar ^ (2 : ℕ)) + (L ^ (2 : ℕ) * R ^ (2 : ℕ)) / (2 * (n : ℝ) * (Real.exp (δ * ((k + 1 : ℕ) : ℝ) / (n : ℝ)) - 1))) (hk : relativeScaleIterationBound n δ L R fStar ≤ (k : ℝ)) : f xkStar ≤ (1 + δ) * fStar

Definition 7.40

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.40: for the matrix A in the textbook nonnegative-matrix-game setup, the associated simplex payoff is the Chapter 6 primal objective of the zero-linear-term simplex saddle-point problem with matrix Aᵀ, restricted to Δ[n].

open scoped StandardSimplex variable {n m : ℕ+} local notation "Δₙ" => Δ[n] def nonnegative_matrix_game_payoff (A : Matrix (Fin (n : ℕ)) (Fin (m : ℕ)) ℝ) : Δₙ → ℝ := (nonnegative_matrix_game_saddle_problem A).primalObjective

Proposition 7.40

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.40: if δ ∈ (0, 1 / 2) and the relative-scale constants L, R, and f^* are positive, then the iteration bound R_n(δ) from (7.4.24) is strictly less than the dimension-free quantity R_∞(δ) = L² R² / (δ² (1 - 2δ) (f^*)²).

theorem relativeScaleIterationBound_lt_uniformBound (n : ℕ+) (δ L R fStar : ℝ) (hδ : δ ∈ Set.Ioo (0 : ℝ) (1 / 2)) (hL : 0 < L) (hR : 0 < R) (hfStar : 0 < fStar) : relativeScaleIterationBound n δ L R fStar < relativeScaleUniformIterationBound δ L R fStar

Definition 7.41

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.41 (1): a linear packing problem consists of nonnegative constraint vectors a₁, …, aₘ ∈ ℝⁿ_+, a positive right-hand side b ∈ ℝᵐ, and positive objective coefficients c ∈ ℝⁿ.

open EuclideanSpace (nonnegativeOrthant positiveOrthant)
open scoped StandardSimplex
variable {m n : ℕ}
structure LinearPackingProblem (m n : ℕ) where
  /-- The constraint vectors `a_i ∈ ℝⁿ_+`. -/
  a : Fin m → EuclideanSpace ℝ (Fin n)
  /-- The right-hand-side vector `b ∈ ℝᵐ`. -/
  b : EuclideanSpace ℝ (Fin m)
  /-- The objective coefficient vector `c ∈ ℝⁿ`. -/
  c : EuclideanSpace ℝ (Fin n)
  /-- Each constraint vector `a_i` lies in the nonnegative orthant `ℝⁿ_+`. -/
  a_nonneg (i : Fin m) : a i ∈ nonnegativeOrthant n
  /-- The right-hand side lies in the positive orthant `ℝ₊₊ᵐ`. -/
  b_pos : b ∈ positiveOrthant m
  /-- The objective coefficient vector lies in the positive orthant `ℝ₊₊ⁿ`. -/
  c_pos : c ∈ positiveOrthant n

Proposition 7.41

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.41: if the k-th iterate satisfies the mixed-accuracy gap estimate with δ = ε / (ε + 2LR) and k is at least the threshold T_n(ε), then its objective value is within absolute accuracy ε of φ*.

universe u theorem quasi_newton_absolute_accuracy_of_iteration_bound {X : Type u} (φ : X → ℝ) (xkStar : X) (φStar : ℝ) (n : ℕ+) (k : ℕ) (L R ε : ℝ) (hL : 0 < L) (hR : 0 < R) (hε : 0 < ε) (hgap : φ xkStar - φStar ≤ let δ := quasi_newton_absolute_accuracy_delta ε L R L * R * (δ / (1 - δ) + 1 / (2 * (n : ℝ) * (Real.exp (δ * ((k + 1 : ℕ) : ℝ) / (n : ℝ)) - 1) * (1 - δ)))) (hk : quasi_newton_absolute_accuracy_iteration_bound n ε L R ≤ (k : ℝ)) : φ xkStar ≤ φStar + ε

Definition 7.42

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.42: for vectors aᵢ ∈ E in a real inner-product space E and a positive parameter μ, the smooth approximation of x ↦ max_i ⟪aᵢ, x⟫ is the Chapter 6 log-sum-exp owner η applied to the score vector i ↦ ⟪aᵢ, x⟫, i.e. x ↦ μ log (∑ i, exp (⟪aᵢ, x⟫ / μ)), for a nonempty finite family indexed by ι.

open scoped BigOperators RealInnerProductSpace universe u v variable {ι : Type v} [Fintype ι] [Nonempty ι] variable {E : Type u} [SeminormedAddCommGroup E] [InnerProductSpace ℝ E] def smoothMaxInnerApproximation (a : ι → E) (μ : {μ : ℝ // 0 < μ}) : E → ℝ := fun x ↦ η μ (WithLp.toLp 2 fun i ↦ ⟪a i, x⟫) -- Proof sketch: unfold `smoothMaxInnerApproximation`; this is the defining specialization of the -- Chapter 6 owner `η` to the score family `i ↦ ⟪a i, x⟫`.

Proposition 7.42

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 7.42: if ε > 0 and the logarithmic parameter 1 + 2 L R / ε is positive, equivalently ε + 2 L R > 0, then the finite-dimensional absolute-accuracy iteration threshold T_n(ε) is strictly smaller than the dimension-free comparison bound T_∞(ε) = (1 / 2) (1 + 2 L R / ε)^2.

theorem quasi_newton_absolute_accuracy_iteration_bound_lt_uniform_bound (n : ℕ+) (L R ε : ℝ) (hε : 0 < ε) (hsum : 0 < ε + 2 * L * R) : quasi_newton_absolute_accuracy_iteration_bound n ε L R < quasi_newton_absolute_accuracy_uniform_iteration_bound L R ε

Definition 7.43

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.43: for a nonempty finite family of nonnegative coefficient vectors aᵢ ∈ ℝⁿ_+, the homogeneous function \hat f : ℝⁿ → ℝ is the finite maximum of the weighted absolute-coordinate sums ∑ⱼ aᵢ⁽ʲ⁾ |x⁽ʲ⁾|.

open EuclideanSpace (nonnegativeOrthant) open scoped BigOperators variable {ι : Type*} [Fintype ι] [Nonempty ι] {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) def maxWeightedAbsoluteCoordinateSum (a : ι → Fin n → NNReal) : E → ℝ := maxTypeObjective fun i x ↦ ∑ j : Fin n, (a i j : ℝ) * |x j|

Definition 7.44

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.44: for a real symmetric matrix, the spectral radius is the least nonnegative real scalar τ such that both symmetric matrices τ I_n - X and τ I_n + X lie in the positive-semidefinite cone 𝕊^n₊.

open scoped MatrixOrder RealSymmetricMatrixSpace variable {n : ℕ} local notation "Mat" => Matrix (Fin n) (Fin n) ℝ theorem realSymmetricMatrix_toReal_spectralRadius_isLeast_semidefiniteBound (X : 𝕊^n) : IsLeast (realSymmetricMatrix_spectralRadiusSemidefiniteBounds X) ρ(X)

Definition 7.45

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.45: the maximal rank is bounded by min {n, ∑ᵢ rank Aᵢ}.

open Matrix
open RealSymmetricMatrixSpace
open scoped RealSymmetricMatrixSpace
open scoped BigOperators
variable {m n : ℕ}
local notation "Eₘ" => EuclideanSpace ℝ (Fin m)
local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ
namespace SpectralRadiusMinimizationProblem
theorem maxRank_le_min_matrixSize_sum_coeffRanks
    (problem : SpectralRadiusMinimizationProblem m n) :
    problem.maxRank ≤
      min n (∑ i : Fin m, Matrix.rank (problem.coeffMatrices i : Mₙ))

Definition 7.46

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.46 recalls the weighted quadratic prox owner (positiveDefMatrixNorm G.1 G.2).quadraticDistanceTo x₀.

open scoped PositiveDefMatrixNorm variable {m : ℕ} local notation "Eₘ" => EuclideanSpace ℝ (Fin m) variable (G : {G : Matrix (Fin m) (Fin m) ℝ // G.PosDef}) (x0 : Eₘ) #check (positiveDefMatrixNorm G.1 G.2).quadraticDistanceTo x0

Definition 7.47

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.47 (1): a linear maximization oracle over Q is a feasible selection c ↦ x*(c) whose sign-flipped outputs form a Chapter 6 linear optimization oracle for the zero regularizer on the feasible subtype Q. Equivalently, oracle c attains the maximum of x ↦ c x on Q.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] def IsLinearMaximizationOracle (Q : Set E) (oracle : StrongDual ℝ E → Q) : Prop := IsLinearOptimizationOracle (fun _ : Q ↦ (0 : ℝ)) fun c ↦ oracle (-c)

Definition 7.48

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.48: under the stronger hypotheses needed by Chapter 6, a bilinear saddle-point problem becomes a structured objective model with linear smooth and dual-penalty parts.

universe u v variable {E : Type u} {F : Type v} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [NormedAddCommGroup F] [InnerProductSpace ℝ F] namespace BilinearSaddlePointProblem variable [FiniteDimensional ℝ E] def toStructuredObjectiveModel (problem : BilinearSaddlePointProblem E F) (hprimal_bounded : Bornology.IsBounded problem.primalSet) (hdual_bounded : Bornology.IsBounded problem.dualSet) : StructuredObjectiveModel E F

Definition 7.49

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.49: for a linear operator A : E → H*, the adjoint operator is exactly the canonical transpose A.flip : H → E*.

open Module universe u v variable {E : Type u} {H : Type v} variable [AddCommMonoid E] [Module ℝ E] variable [AddCommMonoid H] [Module ℝ H] #check (show (E →ₗ[ℝ] Dual ℝ H) → H →ₗ[ℝ] Dual ℝ E from LinearMap.flip)

Definition 7.50

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.50: a vector g is a subgradient of a concave real-valued function f at x when -g is a Chapter 3 subgradient of the convex function -f at x. Equivalently, g gives the global affine upper support inequality for f. Since f : E → ℝ, the textbook domain conditions x ∈ dom f and y ∈ dom f are automatic.

open scoped WithTopConvexAnalysis
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
def IsConcaveSubgradientAt (f : E → ℝ) (x g : E) : Prop :=
  IsSubgradientAt (fun y ↦ ((-f y : ℝ) : WithTop ℝ)) x (-g)

Definition 7.51

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.51: membership in the whole-space second-argument subdifferential is exactly the global affine lower-support inequality for the partial map x' ↦ Ψ u x'.

open scoped WithTopConvexAnalysis universe u v variable {U : Type u} {X : Type v} [NormedAddCommGroup X] [InnerProductSpace ℝ X] theorem mem_secondArgumentSubdifferential_iff (Ψ : U → X → ℝ) (u : U) (x g : X) : g ∈ secondArgumentSubdifferential Ψ u x ↔ ∀ y : X, Ψ u y ≥ Ψ u x + inner ℝ g (y - x)

Definition 7.52

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.52: a constrained analytic center of P = hatP ∩ Q with respect to F is exactly a point of the canonical constrained argmin set of F on the strict feasible region P₀ = hatP ∩ interior Q.

universe u open scoped ConstrainedArgmin variable {E : Type u} [TopologicalSpace E] variable (hatP Q : Set E) (F : E → ℝ) (x0 : E) local notation "P₀" => hatP ∩ interior Q #check x0 ∈ argmin[P₀] F

Definition 7.53

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.53's smoothed support-function approximation Uβ is the Chapter 6 regularized-max owner specialized to the identity dual map, the feasible set hatP, zero dual penalty, prox term F, and affine base term s ↦ -s x₀ + β F(x₀). Its maximizer layer Argmaxβ is the corresponding canonical argmax owner.

universe u open scoped ConstrainedArgmin variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable (hatP : Set E) (F : E → ℝ) (x0 : E) (β : {β : ℝ // 0 < β}) variable (s : StrongDual ℝ E) (u : E) recall smoothedPrimalObjective

Definition 7.54

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.54 recalls the canonical Hessian local norm owner.

recall hessianLocalNorm

Definition 7.55

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.55: the barrier-regularized maximal affine value ℓ⋆(β) is the Chapter 7 canonical maximal value of the payoff x ↦ ℓ x - β (F x - F x₀) over the strict feasible set hatP ∩ interior Q.

universe u variable {E : Type u} [TopologicalSpace E] [AddCommGroup E] [Module ℝ E] variable (hatP Q : Set E) (F : E → ℝ) (x0 : E) (ℓ : AffineMap ℝ E ℝ) (β : ℝ) abbrev affineBarrierRegularizedMaximalValue : EReal := maximalValueOn (hatP ∩ interior Q) (affineBarrierRegularizedPayoff x0 β ℓ F)

Definition 7.56

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.56: for a feasible set P ⊆ X and an objective f, the maximal value f_* of the associated problem is the negated Chapter 1 optimal value of the minimization problem with feasible set P and objective x ↦ -f x. This keeps maximization on the project's canonical EReal-valued optimization owner.

universe u variable {X : Type u} open SetConstrainedMinimizationProblem def maximalValueOn (P : Set X) (f : X → ℝ) : EReal := -((.mk P (fun x ↦ -f x) : SetConstrainedMinimizationProblem X).optimalValue)

Definition 7.57

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.57 (1): given iterates x_i ∈ P, chosen subgradients g_i, and weights λ_i, the gap function ℓ_k is the weighted affine sum ℓ_k(y) = ∑_{i=0}^k λ_i ⟪g_i, y - x_i⟫.

open scoped BigOperators
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
def barrierSubgradientGapFunction
    {P : Set E} (x : ℕ → P) (subgradient : ℕ → E) (lam : ℕ → ℝ) (k : ℕ) : P → ℝ :=
  fun y ↦
    ∑ i ∈ Finset.range (k + 1), lam i * inner ℝ (subgradient i) ((y : E) - (x i : E))

Definition 7.58

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.58: for a feasible set P ⊆ E, a distinguished subset P₀, and a norm ‖·‖ₓ on E for each x ∈ P₀, barrierSubgradientClass P P₀ pointNorm hpointNorm M is the set 𝓑_M(P) of real-valued functions on E whose constrained subdifferential over P is nonempty at every x ∈ P₀ with some subgradient having ‖·‖ₓ*-norm at most M.

open scoped WithTopConvexAnalysis universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] def barrierSubgradientClass (P P0 : Set E) (pointNorm : P0 → Seminorm ℝ E) (hpointNorm : ∀ x : P0, Seminorm.IsNorm (pointNorm x)) (M : NNReal) : Set (E → ℝ) := {f | ∀ x : P0, ∃ g : E, let _ : Seminorm.IsNorm (pointNorm x) := hpointNorm x g ∈ ∂[P] (fun y ↦ (f y : WithTop ℝ)) (x) ∧ (pointNorm x).dualNorm g ≤ (M : ℝ)} -- Proof sketch: unfold `barrierSubgradientClass`; membership is exactly the pointwise bounded -- constrained-subgradient condition over the distinguished subset `P₀`.

Definition 7.59

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.59: [Saddle-point representation] a concave maximization problem on a feasible set P admits a saddle-point representation if it is given by an objective f : P → ℝ together with a function Ψ : P → S → ℝ whose partial minimum over S recovers f(x) for every x ∈ P.

universe u v variable {P : Type u} {S : Type v} structure SaddlePointRepresentation (P : Type u) (S : Type v) where /-- The objective function `f : P → ℝ` of the maximization problem. -/ objective : P → ℝ /-- The saddle function `Ψ : P → S → ℝ` whose minimum over `S` recovers the objective. -/ saddleFunction : P → S → ℝ /-- For each feasible point `x ∈ P`, the objective value is a least element of the saddle slice `Ψ(x, ·)`. This is the faithful owner form of the textbook identity `f(x) = \min_{w ∈ S} Ψ(x, w)`. -/ objective_isLeast (x : P) : IsLeast (Set.range (saddleFunction x)) (objective x)

Definition 7.60

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.60: [Subgradient selection] if w(x) is a chosen minimizer of the saddle slice Ψ(x, ·) and ∇₁Ψ is a chosen subgradient with respect to the first argument, then the selected field x ↦ ∇₁Ψ(x, w(x)) is a subgradient selection of the represented objective.

open scoped ConstrainedArgmin ConvexAnalysis WithTopConvexAnalysis universe u v w variable {P : Type u} {S : Type v} namespace SaddlePointRepresentation variable [NormedAddCommGroup P] [InnerProductSpace ℝ P] variable [NormedAddCommGroup S] [InnerProductSpace ℝ S] theorem barrierSubgradientSelection_isBarrierSubgradientSelection {representation : SaddlePointRepresentation P S} {w : P → S} (hw : representation.IsBarrierSubproblemMinimizerSelection w) (saddleSubgradient : P → S → P × S) (hsub : ∀ x : P, WithLp.toLp 2 (saddleSubgradient x (w x)) ∈ subdifferential (fun z : WithLp 2 (P × S) ↦ ((representation.saddleFunction z.1.1 z.1.2 : ℝ) : WithTop ℝ)) (WithLp.toLp 2 (x, w x))) (hvar : ∀ x : P, ∀ y : S, inner ℝ (saddleSubgradient x (w x)).2 (y - w x) ≥ 0) : representation.IsBarrierSubgradientSelection (barrierSubgradientSelection (fun x s ↦ (saddleSubgradient x s).1) w)

Definition 7.61

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.61: a concave maximization problem over an intersection domain consists of sets hatP, Q ⊆ E and an objective ψ : E → ℝ that is concave on the feasible region hatP ∩ Q and strictly positive on the strict feasible region hatP ∩ interior Q.

universe u variable {E : Type u} [TopologicalSpace E] [AddCommGroup E] [Module ℝ E] structure ConcaveMaximizationOverIntersectionDomain (E : Type u) [TopologicalSpace E] [AddCommGroup E] [Module ℝ E] where /-- The outer set `hatP` appearing in the decomposition `P = hatP ∩ Q`. -/ hatP : Set E /-- The second constraint set `Q` in the decomposition `P = hatP ∩ Q`. -/ Q : Set E /-- The objective `ψ : E → ℝ`. -/ objective : E → ℝ /-- The objective is concave on the feasible region `hatP ∩ Q`. -/ objective_concaveOn : ConcaveOn ℝ (hatP ∩ Q) objective /-- The objective is strictly positive on the strict feasible region `hatP ∩ interior Q`. -/ objective_pos : ∀ ⦃x : E⦄, x ∈ hatP ∩ interior Q → 0 < objective x

Definition 7.62

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.62: for a strictly positive function ψ, its logarithmic transform is the function x ↦ ln (ψ x). Since Real.log is total in mathlib, the owner is the primitive pointwise map Real.log ∘ ψ; positivity remains a source-level hypothesis when needed.

universe u def logarithmicTransform {X : Type u} (ψ : X → ℝ) : X → ℝ := Real.log ∘ ψ

Definition 7.63

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.63 (1): for a saddle-function model Ψ₀ : Ω × P → ℝ, the associated primal objective is the lower value ψ(x) = inf_{u ∈ Ω} Ψ₀(u, x), formalized through the canonical infimal-projection owner on EReal so empty or unbounded-below slices are represented faithfully.

universe u v variable {E : Type u} {E₁ : Type v} variable {P : Set E} {Ω : Set E₁} def saddlePointObjective (Ψ₀ : Ω → P → ℝ) : P → EReal := partialInfProjection (Set.univ : Set (P × Ω)) (fun z : P × Ω ↦ (Ψ₀ z.2 z.1 : EReal)) -- Proof sketch: unfold `saddlePointObjective`; this is exactly the unconstrained -- `partialInfProjection` of the `EReal`-valued saddle map on `P × Ω`.

Definition 7.64

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.64: for a dual vector w = (τ, v) with τ > 0 and τ⁻¹ • v ∈ Ω, the dual objective via the perspective transform of ψ⋆ : Ω → ℝ is η(w) = -1 - log τ + τ ψ⋆(τ⁻¹ • v).

universe u variable {E : Type u} [SMul ℝ E] local notation "P" => ℝ × E def dualObjectiveViaPerspectiveTransform {Ω : Set E} (ψStar : Ω → ℝ) : {w : P // 0 < w.1 ∧ w.1⁻¹ • w.2 ∈ Ω} → ℝ

Definition 7.65

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.65: a value phiBar is a δ-approximation of the positive optimal value phiStar in relative scale when δ > 0 and phiStar ≥ phiBar ≥ phiStar * exp (-δ).

def IsRelativeScaleDeltaApproximation (phiStar δ phiBar : ℝ) : Prop := 0 < phiStar ∧ 0 < δ ∧ phiStar ≥ phiBar ∧ phiBar ≥ phiStar * Real.exp (-δ)

Definition 7.66

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.66: unfolding Asymptotics.IsSoftBigO l size f g gives an ordinary O-bound after restoring a power of the omitted logarithmic factor log (size + 2).

open Asymptotics universe u @[inherit_doc Asymptotics.IsSoftBigO] notation:100 f " =Õ[" size:100 "; " l:100 "] " g:100 => Asymptotics.IsSoftBigO l size f g namespace Asymptotics theorem isSoftBigO_iff {α : Type u} {l : Filter α} {size : α → ℕ} {f g : α → ℝ} : IsSoftBigO l size f g ↔ ∃ logPower : ℕ, f =O[l] fun x ↦ (Real.log ((size x : ℝ) + 2)) ^ logPower * g x

Definition 7.67

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.67: a fractional covering problem is specified by a nonnegative matrix A ∈ ℝ_+^{m × n}, a strictly positive right-hand side b ∈ ℝ_{++}^m, and a strictly positive cost vector c ∈ ℝ_{++}^n; the column dimension is part of the ambient parameter n : ℕ+, so the textbook ψ(y) = min_j (Aᵀ y)_j / c_j is a genuine finite minimum without extra witness fields. The associated feasible set, optimal value φ_*, and concave functional ψ are defined below.

open EuclideanSpace (nonnegativeOrthant positiveOrthant)
open Matrix
open scoped Matrix
variable {m : ℕ} {n : ℕ+}
structure FractionalCoveringProblem (m : ℕ) (n : ℕ+) where
  /-- The nonnegative covering matrix `A`. -/
  matrix : Matrix (Fin m) (Fin (n : ℕ)) ℝ
  /-- The strictly positive right-hand side vector `b`. -/
  rhs : EuclideanSpace ℝ (Fin m)
  /-- The strictly positive cost vector `c`. -/
  cost : EuclideanSpace ℝ (Fin (n : ℕ))
  /-- Every entry of `A` is nonnegative. -/
  matrix_nonneg (i : Fin m) (j : Fin (n : ℕ)) : 0 ≤ matrix i j
  /-- The right-hand side lies in the positive orthant. -/
  rhs_pos : rhs ∈ positiveOrthant m
  /-- The cost vector lies in the positive orthant. -/
  cost_pos : cost ∈ positiveOrthant n

Definition 7.68

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.68: the maximal concurrent flow value is the maximal value of the nonnegative concurrency coordinate on the feasible-state set, viewed through the chapter's faithful EReal maximization owner.

open scoped BigOperators universe u v variable {V : Type u} {A : Type v} [Fintype A] def maximalConcurrentFlowValue (B : Matrix V A ℝ) (OD : Finset (V × V)) (demand : {p // p ∈ OD} → NNReal) (capacity : A → NNReal) : EReal := maximalValueOn (concurrentFlowFeasibleSet B OD demand capacity) fun state ↦ state.1 -- Proof sketch: unfold `maximalConcurrentFlowValue` and apply the chapter owner expansion theorem -- `maximalValueOn_eq_sSup_image` to the real-valued concurrency coordinate `state ↦ (state.1 : ℝ)`.

Definition 7.69

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.69: a convex minimax problem consists of a nonempty closed convex feasible set S ⊆ E in a real topological module together with a nonempty finite family of nonnegative component functions fᵢ : E → ℝ≥0 whose restrictions to S are convex. Its objective is the pointwise maximum of the component family, minimized over S, and its dual side is obtained from simplex-weighted convex combinations of the same family.

open scoped BigOperators universe u v variable {E : Type u} [TopologicalSpace E] [AddCommMonoid E] [Module ℝ E] variable {ι : Type v} [Fintype ι] [Nonempty ι] structure ConvexMinimaxProblem (E : Type u) (ι : Type v) [TopologicalSpace E] [AddCommMonoid E] [Module ℝ E] [Fintype ι] [Nonempty ι] where /-- The feasible set `S`. -/ feasibleSet : Set E /-- The feasible set is nonempty. -/ feasibleSet_nonempty : feasibleSet.Nonempty /-- The feasible set is closed. -/ feasibleSet_isClosed : IsClosed feasibleSet /-- The feasible set is convex. -/ feasibleSet_convex : Convex ℝ feasibleSet /-- The nonnegative component family `fᵢ : E → ℝ≥0`. -/ componentFun : ι → E → NNReal /-- Each component function is convex on the feasible set `S`. -/ componentFun_convex (i : ι) : ConvexOn ℝ feasibleSet (fun x ↦ (componentFun i x : ℝ))

Definition 7.70

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.70: the Boolean quadratic optimum f⋆ is the supremum of the quadratic-map values A.toQuadraticMap' x over all sign vectors on the finite coordinate type ι. The textbook n-dimensional case is the specialization ι = Fin n, and the later approximation theorem specializes further to positive-definite matrices.

universe u variable {ι : Type u} [Fintype ι] [DecidableEq ι] def booleanQuadraticOptimalValue (A : Matrix ι ι ℝ) : ℝ := sSup (A.toQuadraticMap' '' signVectorSet ι) -- Proof sketch: unfold `booleanQuadraticOptimalValue`; the right-hand side is exactly the -- defining supremum of the quadratic values over the sign-vector feasible set.

Definition 7.71

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.71: for a symmetric matrix A ∈ ℝ^{n × n}, the value ψ⋆ is the infimum of ⟨\bar e_n, y⟩ = ∑ i, y i over all vectors y ∈ ℝⁿ whose diagonal matrix D(y) satisfies D(y) ⪰ A.

open Matrix open scoped BigOperators MatrixOrder RealSymmetricMatrixSpace variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) local notation "Mₙ" => Matrix (Fin n) (Fin n) ℝ def diagonalSemidefiniteRelaxationOptimalValue (A : 𝕊^n) : ℝ := sInf ((fun y : E ↦ ∑ i : Fin n, y i) '' diagonalSemidefiniteRelaxationFeasibleSet A) -- Proof sketch: unfold `diagonalSemidefiniteRelaxationOptimalValue`; the right-hand side is -- exactly the defining infimum of the linear objective over the feasible diagonal-majorant set.

Definition 7.72

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.72 is a bridge/view item in the chapter's semidefinite log-determinant-barrier domain. Mandatory domain-style sampling: - logDetBarrier and logDetBarrier_apply in Chap05/Definition_5_4_4_5, the Chapter 5 owner of the semidefinite log-determinant barrier on the strict cone 𝕊^n₊₊; - negativeLogDet_isSelfConcordantBarrierOnWith_positiveSemidefiniteCone in Chap05/Theorem_5_4_4_3, the Chapter 5 owner theorem recording that the same barrier has parameter ν = n; - Matrix.PosDef, the canonical matrix-level positive-definite owner behind the strict-cone bridge already used upstream. Best owner abstraction: - logDetBarrier Primitive data: - n : ℕ Derived API: - logDetBarrier n : 𝕊^n₊₊ → ℝ - logDetBarrier_apply - negativeLogDet_isSelfConcordantBarrierOnWith_positiveSemidefiniteCone Source/core/bridge triage: - source-facing: the semidefinite log-determinant barrier together with the parameter statement ν = n - core/canonical: logDetBarrier - bridge/view: logDetBarrier_apply and the Chapter 5 self-concordance theorem The barrier, its strict domain, and the parameter statement are already owned upstream in Chapter 5. This file therefore recalls that canonical API directly instead of keeping parallel Chapter 7 copies of the positive-definite subtype, the barrier itself, or the parameter alias.

recall logDetBarrier

Definition 7.73

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.73: an optimal static production strategy is a feasible point xStatic : P whose cumulative output is maximal among all feasible static strategies. On the feasible subtype P, this is exactly the canonical owner IsMaxOn (staticProductionTotalOutput ψ) Set.univ xStatic, and its average efficiency is the already-defined staticProductionAverageEfficiency ψ xStatic.

open scoped BigOperators universe u variable {X : Type u} variable (P : Set X) (N : ℕ) variable (ψ : Fin (N + 1) → P → {r : ℝ // 0 < r}) variable (xStatic : P) #check IsMaxOn (staticProductionTotalOutput ψ) Set.univ xStatic

Definition 7.74

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.74: the average rate of growth of a dynamic strategy over the periods 0, ..., N is the geometric mean of the outputs ψ_k(x_k) along the adaptive strategy trace.

open scoped BigOperators universe u variable {X : Type u} def dynamicStrategyAverageRateOfGrowth {P : Set X} {N : ℕ} (ψ : Fin (N + 1) → P → {r : ℝ // 0 < r}) (x : Fin (N + 1) → P) : ℝ

Definition 7.75

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.75: the set of optimal constant-share portfolios on P consists of the feasible portfolios that maximize the cumulative return x ↦ ∏_{k=0}^N ⟪c_k, x⟫. Any member of this set is an admissible textbook choice of x_N^⋆.

open scoped BigOperators open Matrix variable {n N : ℕ} def optimalConstantShareArgmax (P : Set (stdSimplex NNReal (Fin n))) (c : Fin (N + 1) → Fin n → NNReal) : Set (stdSimplex NNReal (Fin n)) := {x | x ∈ P ∧ IsMaxOn (constantShareObjective c) P x} -- Proof sketch: unfold `optimalConstantShareArgmax`.

Definition 7.76

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.76 recalls the strict positive orthant ℝⁿ₊₊.

open scoped BigOperators open scoped EuclideanOrthant recall EuclideanSpace.positiveOrthant (n : ℕ) : Set (EuclideanSpace ℝ (Fin n))

Definition 7.77

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.77: the average growth rate of an iterated portfolio over the periods 0, ..., N is the geometric mean of the period returns ⟪c_k, x_k⟫.

open scoped BigOperators open Matrix variable {n N : ℕ} def iteratedPortfolioAverageGrowthRate {P : Set (stdSimplex NNReal (Fin n))} (c : Fin (N + 1) → Fin n → NNReal) (x : Fin (N + 1) → P) : NNReal := iteratedPortfolioCumulativeReturn c x ^ ((1 : ℝ) / (N + 1))

Definition 7.78

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.78: an elastic production investment model with n production processes consists of period-dependent production costs a_k^(i) > 0 and unit prices b_k^(i) ≥ 0.

open scoped BigOperators EuclideanOrthant StandardSimplex structure ElasticProductionInvestmentModel (n : ℕ) where /-- The production cost `a_k^(i)` of process `i` in period `k`. -/ productionCost : ℕ → Fin n → ℝ /-- The unit price `b_k^(i)` of process `i` in period `k`. -/ unitPrice : ℕ → Fin n → ℝ /-- Every production cost is strictly positive. -/ productionCost_pos (k : ℕ) (i : Fin n) : 0 < productionCost k i /-- Every unit price is nonnegative. -/ unitPrice_nonneg (k : ℕ) (i : Fin n) : 0 ≤ unitPrice k i

Definition 7.79

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.79: a one-stage stochastic programming problem consists of a feasible set of static decisions, a probability law, a measurable random input ζ, and a jointly measurable payoff function whose expectation is well-defined for every feasible decision. The textbook ℝ^m random-vector presentation is the specialization to Ξ = EuclideanSpace ℝ (Fin m).

open MeasureTheory open scoped ProbabilityTheory universe u v w variable (X : Type u) [MeasurableSpace X] variable (Ω : Type v) [MeasurableSpace Ω] variable (Ξ : Type w) [MeasurableSpace Ξ] structure OneStageStochasticProgram where /-- The probability law governing the sample space. -/ law : ProbabilityMeasure Ω /-- The feasible set of static decisions. -/ feasibleSet : Set X /-- The random input entering the payoff. -/ randomVector : Ω → Ξ /-- The random input is a measurable random variable. -/ measurable_randomVector : Measurable randomVector /-- The stage payoff as a function of the decision and the realized random input. -/ payoff : X → Ξ → ℝ /-- The payoff is jointly measurable in the decision and random inputs. -/ measurable_payoff : Measurable fun p : X × Ξ ↦ payoff p.1 p.2 /-- The realized payoff is integrable for every feasible static decision. -/ integrable_payoff (x : feasibleSet) : Integrable (fun ω ↦ payoff x.1 (randomVector ω)) (law : Measure Ω)

Definition 7.80

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.80: f satisfies the everywhere nonempty subdifferential condition on Q when every point x ∈ Q has a nonempty subdifferential ∂ f(x).

open scoped WithTopConvexAnalysis universe u variable {V : Type u} [SeminormedAddCommGroup V] [InnerProductSpace ℝ V] def EverywhereNonemptySubdifferentialCondition (f : V → WithTop ℝ) (Q : Set V) : Prop := ∀ ⦃x : V⦄, x ∈ Q → (∂ f(x)).Nonempty -- Proof sketch: apply the defining predicate of -- `EverywhereNonemptySubdifferentialCondition` at the chosen point `x ∈ Q`.

Definition 7.81

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.81: a function that is strictly positive on Q satisfies the defining subgradient inequality at every pair of points of Q.

open scoped WithTopConvexAnalysis universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] theorem StrictlyPositiveOn.inequality {Q : Set E} {f : E → ℝ} (hf : StrictlyPositiveOn Q f) {x y g : E} (hx : x ∈ Q) (hy : y ∈ Q) (hg : g ∈ ∂[Set.univ] f(x)) : 0 ≤ f y + f x + inner ℝ g (y - x)

Definition 7.82

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.82: the associated set Q_y is the affine preimage of Q_x under y ↦ A y + b.

variable {n m : ℕ} local notation "En" => EuclideanSpace ℝ (Fin n) local notation "Em" => EuclideanSpace ℝ (Fin m) variable (A : Matrix (Fin n) (Fin m) ℝ) (b : En) (Qx : Set En) #check ((A.toEuclideanLin.toAffineMap +ᵥ AffineMap.const ℝ Em b) ⁻¹' Qx : Set Em)

Definition 7.83

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.83: a real-valued function is strictly positive on a closed convex set Q when Q is closed and convex, f is convex on the whole ambient space, and f is strictly positive on Q in the sense of Definition 7.81.

open scoped WithTopConvexAnalysis universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable (Q : Set E) (f : E → ℝ) #check (IsClosed Q ∧ Convex ℝ Q ∧ ConvexOn ℝ Set.univ f ∧ StrictlyPositiveOn Q f)

Definition 7.84

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.84: for a norm ‖·‖ on ℝⁿ, the dual norm is the support function of the closed unit ball. In the canonical project API this owner is Seminorm.dualNorm p for a separated seminorm p on a real inner-product space.

universe u
namespace Seminorm
recall dualNorm
    {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
    (p : Seminorm ℝ E) [p.IsNorm] :
    E → ℝ

Definition 7.85

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.85: a general minimization problem with strictly positive objective consists of a feasible type Q, a strictly positive objective function φ : Q → ℝ, and a chosen optimal solution x⋆ : Q minimizing φ over all feasible points.

universe u structure StrictlyPositiveObjectiveMinimizationProblem (Q : Type u) where /-- The objective function `φ : Q → ℝ`. -/ objective : Q → ℝ /-- The objective function is strictly positive on the feasible set `Q`. -/ objective_strictlyPositive : StrictlyPositive objective /-- The chosen optimal solution `x⋆ ∈ Q`. -/ optimalSolution : Q /-- The chosen optimal solution minimizes `φ` over the whole feasible set `Q`. -/ optimalSolution_isMin : IsMinOn objective Set.univ optimalSolution

Definition 7.86

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.86 reuses the Chapter 7 transformed-subgradient owner from Lemma_7_20.

open scoped RelativeScaleTransformNotation universe u variable {V : Type u} [NormedAddCommGroup V] [InnerProductSpace ℝ V] recall relativeScaleTransformedSubgradient

Definition 7.87

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.87 recalls the initial estimating function as the weighted quadratic prox owner centered at x₀, with the associated G₀-primal and dual norms supplied by the canonical weighted-norm API.

open scoped PositiveDefMatrixNorm variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) variable (G0 : {G : Matrix (Fin n) (Fin n) ℝ // G.PosDef}) (x0 : E) #check (positiveDefMatrixNorm G0.1 G0.2).quadraticDistanceTo x0

Definition 7.88

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.88 (1): a sequence xBest realizes the textbook best points x_k^* when each term xBest k minimizes f over the sampled prefix {x₀, ..., x_k}.

open scoped BigOperators ConstrainedArgmin universe u v variable {X : Type u} def IsSampledIteratesBestPointSequence (f : X → ℝ) (xSeq xBest : ℕ → X) : Prop := ∀ k : ℕ, xBest k ∈ argmin[Set.range (fun i : Fin (k + 1) ↦ xSeq i)] f

Definition 7.89

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.89: xBar has mixed (ε, δ)-accuracy for the objective hatf with respect to the reference point xStar when ε > 0, δ ∈ (0, 1), and (1 - δ) * hatf xBar ≤ hatf xStar + ε.

universe u def HasMixedAccuracy {Q : Type u} (hatf : Q → ℝ) (xStar : Q) (ε δ : ℝ) (xBar : Q) : Prop := 0 < ε ∧ δ ∈ Set.Ioo (0 : ℝ) 1 ∧ (1 - δ) * hatf xBar ≤ hatf xStar + ε

Definition 7.90

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.90: a feasible point xBar ∈ Q is an approximate solution with mixed (ε, δ)-accuracy for the minimization of hatF over Q with chosen optimal solution xStar when xStar minimizes hatF on Q and xBar satisfies the scalar mixed-accuracy owner from Definition 7.89 relative to xStar.

universe u variable {X : Type u} structure IsMixedApproximateSolution (Q : Set X) (hatF : X → ℝ) (xStar : X) (ε δ : ℝ) (xBar : X) : Prop where /-- The candidate point `xBar` belongs to the feasible set `Q`. -/ feasible : xBar ∈ Q /-- The reference point `xStar` is an optimal solution of `hatF` on `Q`. -/ optimal : IsMinOn hatF Q xStar /-- The scalar mixed-accuracy data are owned by `HasMixedAccuracy`. -/ mixedAccuracy : HasMixedAccuracy hatF xStar ε δ xBar

Definition 7.91

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.91 recalls the Chapter 7 mixed-accuracy iteration-count owner N_n(ε, δ).

recall mixedAccuracyIterationCountBound (n : ℕ+) (L R ε δ : ℝ) : ℝ

Definition 7.92

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.92: a point xBar is a relative δ-approximate solution of the minimization problem for f on Q when δ ∈ (0, 1 / 2), xBar ∈ Q, the canonical constrained optimal value is strictly positive, and f xBar is at most (1 + δ) times that owner optimal value.

universe u variable {X : Type u} def IsRelativeDeltaApproximateSolutionOn (Q : Set X) (f : X → ℝ) (δ : ℝ) (xBar : X) : Prop := let problem : SetConstrainedMinimizationProblem X := .mk Q f δ ∈ Set.Ioo (0 : ℝ) (1 / 2) ∧ xBar ∈ Q ∧ (0 : EReal) < problem.optimalValue ∧ (f xBar : EReal) ≤ (1 + δ) * problem.optimalValue

Definition 7.93

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.93: a point xBar is an absolute-accuracy ε-approximate solution for the minimization of phi over the feasible set Q when ε > 0 and xBar is an ε-approximate minimizer for the Chapter 1 constrained-minimization owner on (Q, phi).

universe u variable {X : Type u} def IsAbsoluteAccuracyApproximateSolutionOn (Q : Set X) (phi : X → ℝ) (ε : ℝ) (xBar : X) : Prop := 0 < ε ∧ (.mk Q phi : SetConstrainedMinimizationProblem X).IsApproximateMinimizer ε xBar

Definition 7.94

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 7.94: the shifted objective attached to φ, x₀, L, and R is the ambient function x ↦ φ(x) - φ(x₀) + 2LR. For a feasible set Q, the source-facing objective on Q is its restriction along Subtype.val : Q → E. The surrounding radius bound ‖x - x₀‖ ≤ R for x ∈ Q motivates the constant shift but is not primitive data of the definition.

universe u variable {E : Type u} def shiftedObjective (φ : E → ℝ) (x₀ : E) (L R : ℝ) : E → ℝ := fun x ↦ φ x - φ x₀ + 2 * L * R

Supporting modules

These source modules support the indexed items and are listed separately so the chapter inventory remains complete.

  • Lemma_7_3/Core.lean (Documentation unavailable) (Lean source)

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

  • Proposition_New_1.lean (Documentation unavailable) (Lean source)

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source