Documentation

IntroductoryLecturesOnConvexOptimization_Nesterov_2004.Chap03.Definition_3_78

Statements

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

Definition 3.78: at fixed sampled affine models, the auxiliary slice x ↦ max (hatModel x - t) (checkModel x) is the direct owner specialization below.

#check (setConstrainedParametricObjective hatModel checkModel : ℝ → E → ℝ)

Lean source

Source context
universe u
variable {E : Type u} [SeminormedAddCommGroup E] [InnerProductSpace ℝ E]
variable {k : ℕ}
variable (Q : Set E)
variable (f fBar : E → ℝ)
variable (xSample gSample gBarSample : Fin (k + 1) → E)
local notation "hatMinorant" =>
  fun j : Fin (k + 1) ↦
    sampledAffineMinorant (xSample j) (gSample j) (f (xSample j))
local notation "checkMinorant" =>
  fun j : Fin (k + 1) ↦
    sampledAffineMinorant (xSample j) (gBarSample j) (fBar (xSample j))
local notation "hatMinorantFn" =>
  fun j : Fin (k + 1) ↦ (hatMinorant j : E → ℝ)
local notation "checkMinorantFn" =>
  fun j : Fin (k + 1) ↦ (checkMinorant j : E → ℝ)
local notation "hatModel" =>
  maxTypeObjective hatMinorantFn
local notation "checkModel" =>
  maxTypeObjective checkMinorantFn
local notation "hatFn" =>
  fun _ : Unit ↦ fun _ : Unit ↦ hatModel
local notation "checkFn" =>
  fun _ : Unit ↦ fun _ : Unit ↦ checkModel

The owner nonpositivity condition is exactly the textbook sampled affine inequality system.

#check
  (show
      x ∈ Q ∧ setConstrainedParametricObjective hatModel checkModel t x ≤ 0 ↔
        x ∈ Q ∧
          (∀ j : Fin (k + 1),
            f (xSample j) + inner ℝ (gSample j) (x - xSample j) ≤ t) ∧
          ∀ j : Fin (k + 1),
            fBar (xSample j) + inner ℝ (gBarSample j) (x - xSample j) ≤ 0 from
    by
      rw [setConstrainedParametricObjective_apply, max_le_iff]
      constructor
      · rintro ⟨hxQ, hhat, hcheck⟩
        refine ⟨hxQ, ?_, ?_⟩
        · have hhat' : hatModel x ≤ t := by
            simpa [sub_le_iff_le_add, zero_add] using hhat
          simpa using (maxTypeObjective_le_iff hatMinorantFn x t).1 hhat'
        · simpa using (maxTypeObjective_le_iff checkMinorantFn x (0 : ℝ)).1 hcheck
      · rintro ⟨hxQ, hhat, hcheck⟩
        refine ⟨hxQ, ?_, ?_⟩
        · have hhat' : hatModel x ≤ t :=
            (maxTypeObjective_le_iff hatMinorantFn x t).2 <|
              by simpa using hhat
          simpa [sub_le_iff_le_add, zero_add] using hhat'
        · exact
            (maxTypeObjective_le_iff checkMinorantFn x (0 : ℝ)).2 <|
              by simpa using hcheck
  )

Lean source

Source context
universe u
variable {E : Type u} [SeminormedAddCommGroup E] [InnerProductSpace ℝ E]
variable {k : ℕ}
variable (Q : Set E)
variable (f fBar : E → ℝ)
variable (xSample gSample gBarSample : Fin (k + 1) → E)
local notation "hatMinorant" =>
  fun j : Fin (k + 1) ↦
    sampledAffineMinorant (xSample j) (gSample j) (f (xSample j))
local notation "checkMinorant" =>
  fun j : Fin (k + 1) ↦
    sampledAffineMinorant (xSample j) (gBarSample j) (fBar (xSample j))
local notation "hatMinorantFn" =>
  fun j : Fin (k + 1) ↦ (hatMinorant j : E → ℝ)
local notation "checkMinorantFn" =>
  fun j : Fin (k + 1) ↦ (checkMinorant j : E → ℝ)
local notation "hatModel" =>
  maxTypeObjective hatMinorantFn
local notation "checkModel" =>
  maxTypeObjective checkMinorantFn
local notation "hatFn" =>
  fun _ : Unit ↦ fun _ : Unit ↦ hatModel
local notation "checkFn" =>
  fun _ : Unit ↦ fun _ : Unit ↦ checkModel
variable {Q f fBar xSample gSample gBarSample}
variable {x : E} {t : ℝ}

Definition 3.78: the auxiliary threshold is the direct sampled specialization of the chapter owner constrainedThreshold.

#check (constrainedThreshold Q hatFn checkFn () () : EReal)

Lean source

Source context
universe u
variable {E : Type u} [SeminormedAddCommGroup E] [InnerProductSpace ℝ E]
variable {k : ℕ}
variable (Q : Set E)
variable (f fBar : E → ℝ)
variable (xSample gSample gBarSample : Fin (k + 1) → E)
local notation "hatMinorant" =>
  fun j : Fin (k + 1) ↦
    sampledAffineMinorant (xSample j) (gSample j) (f (xSample j))
local notation "checkMinorant" =>
  fun j : Fin (k + 1) ↦
    sampledAffineMinorant (xSample j) (gBarSample j) (fBar (xSample j))
local notation "hatMinorantFn" =>
  fun j : Fin (k + 1) ↦ (hatMinorant j : E → ℝ)
local notation "checkMinorantFn" =>
  fun j : Fin (k + 1) ↦ (checkMinorant j : E → ℝ)
local notation "hatModel" =>
  maxTypeObjective hatMinorantFn
local notation "checkModel" =>
  maxTypeObjective checkMinorantFn
local notation "hatFn" =>
  fun _ : Unit ↦ fun _ : Unit ↦ hatModel
local notation "checkFn" =>
  fun _ : Unit ↦ fun _ : Unit ↦ checkModel

Unfolding the owner threshold recovers the textbook infimum of feasible upper bounds for the sampled affine models of f and fBar.

#check
  (show
      constrainedThreshold Q hatFn checkFn () () =
        sInf (((↑) : ℝ → EReal) ''
          {t : ℝ | ∃ x ∈ Q,
            (∀ j : Fin (k + 1),
              f (xSample j) + inner ℝ (gSample j) (x - xSample j) ≤ t) ∧
            ∀ j : Fin (k + 1),
              fBar (xSample j) + inner ℝ (gBarSample j) (x - xSample j) ≤ 0}) from
    by
      rw [constrainedThreshold_def]
      refine congrArg sInf ?_
      ext u
      constructor
      · rintro ⟨t, ⟨x, hxQ, hhat, hcheck⟩, rfl⟩
        refine ⟨t, ⟨x, hxQ, ?_, ?_⟩, rfl⟩
        · simpa using (maxTypeObjective_le_iff hatMinorantFn x t).1 hhat
        · simpa using (maxTypeObjective_le_iff checkMinorantFn x (0 : ℝ)).1 hcheck
      · rintro ⟨t, ⟨x, hxQ, hhat, hcheck⟩, rfl⟩
        refine ⟨t, ⟨x, hxQ, ?_, ?_⟩, rfl⟩
        · exact
            (maxTypeObjective_le_iff hatMinorantFn x t).2 <|
              by simpa using hhat
        · exact
            (maxTypeObjective_le_iff checkMinorantFn x (0 : ℝ)).2 <|
              by simpa using hcheck
  )

Lean source

Source context
universe u
variable {E : Type u} [SeminormedAddCommGroup E] [InnerProductSpace ℝ E]
variable {k : ℕ}
variable (Q : Set E)
variable (f fBar : E → ℝ)
variable (xSample gSample gBarSample : Fin (k + 1) → E)
local notation "hatMinorant" =>
  fun j : Fin (k + 1) ↦
    sampledAffineMinorant (xSample j) (gSample j) (f (xSample j))
local notation "checkMinorant" =>
  fun j : Fin (k + 1) ↦
    sampledAffineMinorant (xSample j) (gBarSample j) (fBar (xSample j))
local notation "hatMinorantFn" =>
  fun j : Fin (k + 1) ↦ (hatMinorant j : E → ℝ)
local notation "checkMinorantFn" =>
  fun j : Fin (k + 1) ↦ (checkMinorant j : E → ℝ)
local notation "hatModel" =>
  maxTypeObjective hatMinorantFn
local notation "checkModel" =>
  maxTypeObjective checkMinorantFn
local notation "hatFn" =>
  fun _ : Unit ↦ fun _ : Unit ↦ hatModel
local notation "checkFn" =>
  fun _ : Unit ↦ fun _ : Unit ↦ checkModel

Module source