Documentation

IntroductoryLecturesOnConvexOptimization_Nesterov_2004.Chap03.Proposition_3_55

Statements

Source excerpts; proofs omitted. recall restates an existing declaration; #check records an expression, not its inferred type.

Proposition 3.55 (2): the chapter already owns the full-step internal-iteration estimate in Lemma_3_3_9 under the canonical constrained-level method API.

recall full_step_increment_le_uniform_internal_iteration_bound

Lean source

Source context
namespace ConstrainedLevelMethod

Module source

theorem LevelMethodHistory.gap_le_kappa_mul_optimalValue_of_termination_rule (history : LevelMethodHistory) {κ : ℝ} (k : ℕ) (htermination : history.approximateOptimalValue k ≥ (1 - κ) * history.optimalValue k) :
history.gap k ≤ κ * history.optimalValue k

Proposition 3.55 (1): if the relative termination rule fhat(history, k) ≥ (1 - κ) fstar(history, k) holds at a selected full step, then the owner gap δ[history](k) = fstar(history, k) - fhat(history, k) is bounded by κ fstar(history, k).