Chapter 10 — Penalty Function Methods

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

Exercise 10.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Exercise 10.1: for every positive penalty parameter σ, the Courant quadratic penalty function for the problem with objective x ↦ -2 * x 0 + x 1 and equality constraint x 1 - (x 0)^2 = 0 is minimized on Set.univ at chapter10Exercise101PenaltyMinimizer σ = (1, 1 - 1 / (2 * σ)).

open Filter local notation "Point" => EuclideanSpace ℝ (Fin 2) theorem chapter10Exercise101_quadraticPenalty_isMinOn (σ : ℝ) (hσ : 0 < σ) : IsMinOn (PenaltyFunction.quadratic chapter10Exercise101Problem σ hσ) Set.univ (chapter10Exercise101PenaltyMinimizer σ)

Exercise 10.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Exercise 10.2 as the chapter's canonical StandardPenaltyProblem: there are no equality constraints, and the three inequality constraints are 8 - x 0, 8 - x 1, and x 0 + x 1 - 1.

local notation "Point" => EuclideanSpace ℝ (Fin 2) -- Semantic recall: `lean_leansearch` surfaced `IsMinOn` as the canonical minimizer API, and -- nearby Chapter 10 example files keep concrete `ℝ²` objectives, constrained-problem owners, -- and optimizer points explicit on `Point = EuclideanSpace ℝ (Fin 2)`. def chapter10Exercise102Problem : StandardPenaltyProblem 2 3

Exercise 10.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Exercise 10.3 as a chapter-level InteriorPointPenaltyProblem with the objective x 0 - x 1 + (x 1)^2, the two nonnegativity constraints, and the logarithmic barrier c ↦ log (1 / c).

open Filter
local notation "Point" => EuclideanSpace ℝ (Fin 2)
def chapter10Exercise103Problem : InteriorPointPenaltyProblem Point (Fin 2)

Exercise 10.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Exercise 10.4 (1): with the explicit candidate chapter10Exercise104InitialAugmentedMinimizer σ, the initial augmented-Lagrangian subproblem is minimized on Set.univ.

open scoped BigOperators
local notation "Point" => EuclideanSpace ℝ (Fin 2)

-- Domain sampling:
-- * primary domain: Chapter 10 penalty-method owner surfaces for the Exercise
--   10.3/10.4 inequality-constrained problem on `ℝ²`: the augmented-Lagrangian
--   stage objective from Section 10.4 and the strict-feasible-set owner from
--   Section 10.3
-- * inspected project owner/view declarations:
--   `StandardPenaltyProblem` and `c⁽-⁾[problem]` in `Definition_10_1_extra_1`,
--   `StandardPenaltyProblem.augmentedLagrangian` and
--   `StandardPenaltyProblem.augmentedLagrangian_eq` in `Algorithm_10_4_1`,
--   `InteriorPointPenaltyProblem.toStandardPenaltyProblem` in
--   `Definition_10_3_extra_1`,
--   `InteriorPointPenaltyProblem.strictFeasibleSet` and
--   `InteriorPointPenaltyProblem.mem_strictFeasibleSet_iff` in
--   `Definition_10_3_extra_1`,
--   the inherited exercise data `chapter10Exercise103Objective`,
--   `chapter10Exercise103Constraint`, `chapter10Exercise103InitialPoint`,
--   `chapter10Exercise103BarrierMinimizer`,
--   `chapter10Exercise103_mem_strictFeasibleSet_iff`, and
--   `chapter10Exercise103Optimizer` in `Exercise_10_3`
-- * best owner abstractions: the canonical Chapter 10 owner for the constrained
--   problem surface is `chapter10Exercise103Problem.toStandardPenaltyProblem`,
--   and the stage objective is its `augmentedLagrangian`; meanwhile
--   `chapter10Exercise103Problem.strictFeasibleSet` is the canonical owner for
--   the strict-interiority statement about the barrier minimizer
-- * primitive data vs. derived API:
--   primitive data for this exercise are inherited from `chapter10Exercise103Problem`;
--   the initial augmented objective and its explicit minimizer are derived from
--   that owner together with the inherited Exercise 10.3 point data; the
--   coordinate positivity inequalities are derived from strict-feasible-set
--   membership, not primitive data
theorem chapter10Exercise104_initialAugmentedObjective_isMinOn
    (σ : Point) (hσ : ∀ i : Fin 2, 0 < σ i) :
    IsMinOn
      (chapter10Exercise104InitialAugmentedObjective σ)
      Set.univ
      (chapter10Exercise104InitialAugmentedMinimizer σ)

Exercise 10.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Exercise 10.5 (1): if x σ solves the reciprocal-barrier subproblem min_x f(x) + (1 / σ) * ∑ i, 1 / cᵢ(x) on the interior region {x | ∀ i, 0 < cᵢ(x)} for every positive σ, so in particular each x σ lies in that interior region, then the achieved penalty value P(x(σ), σ) is non-increasing as σ increases.

open scoped BigOperators
variable {Point : Type*} {ι : Type*} [Fintype ι]

-- Domain sampling:
-- * primary domain: Chapter 10 interior-point penalty problems
-- * inspected owner declarations in this domain:
--   `InteriorPointPenaltyProblem`,
--   `InteriorPointPenaltyProblem.penaltyFunction_apply`,
--   `InteriorPointPenaltyProblem.HasPositiveBarrierValues`,
--   `InteriorPointPenaltyProblem.penaltyValue_antitone`,
--   `InteriorPointPenaltyProblem.objective_antitone`,
--   `InteriorPointPenaltyProblem.barrierSum_monotone`
-- * best owner abstraction: `InteriorPointPenaltyProblem Point ι`
-- * source-facing layer here: the exercise penalty sums with the pointwise reciprocal
--   `1 / constraint i x`
-- * core/canonical layer here: owner-level minimizer monotonicity statements for
--   `problem.penaltyFunction σ` on `problem.strictFeasibleSet`
-- * bridge/view layer here: a private bundled `InteriorPointPenaltyProblem` using the
--   reciprocal barrier, only to reuse the chapter owner lemmas
-- Primitive data here is only the objective, the inequality constraints, and the nonempty
-- strict feasible region. The strict-feasible set, barrier sum, penalty function, and monotonicity
-- API are derived from the owner and are not stored again locally. The source-facing minimizer
-- hypothesis below records both strict-feasible membership and `IsMinOn`, since the mathlib
-- minimizer predicate alone does not imply membership in the minimizing set.
variable (objective : Point → ℝ) (constraint : ι → Point → ℝ)
variable (x : ℝ → Point)
variable
  (hx : ∀ {σ : ℝ}, 0 < σ →
    x σ ∈ {y : Point | ∀ i : ι, 0 < constraint i y} ∧
      IsMinOn
        (fun y ↦ objective y + (1 / σ) * ∑ i : ι, 1 / constraint i y)
        {y : Point | ∀ i : ι, 0 < constraint i y}
        (x σ))
include objective constraint x hx
theorem chapter10Exercise105_penaltyValue_nonincreasing
    {σ₁ σ₂ : ℝ} (hσ₁ : 0 < σ₁) (hσ₁₂ : σ₁ < σ₂) :
    objective (x σ₂) + (1 / σ₂) * ∑ i : ι, 1 / constraint i (x σ₂) ≤
      objective (x σ₁) + (1 / σ₁) * ∑ i : ι, 1 / constraint i (x σ₁)

Exercise 10.6

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Exercise 10.6: in the Definition 10.1 penalty-function surface (10.1.10), the choice h(c) = exp c is not an admissible penalty term, since its one-dimensional Chapter 10 bridge does not satisfy the required normalization at 0.

variable {n : ℕ} local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin 1) -- Domain sampling: -- * primary domain: Chapter 10 penalty functions for `StandardPenaltyProblem` -- * inspected owner/canonical declarations: -- `StandardPenaltyProblem.constraintViolation` in `Definition_10_1_extra_1`, -- `PenaltyFunction` in `Definition_10_1_extra_1`, -- `PenaltyFunction.nonsmoothExact` in `Definition_10_6_extra_1`, -- `Real.exp_zero` in mathlib as the canonical normalization fact for the scalar kernel -- * best owner abstraction: `PenaltyFunction`; this file should reuse that owner rather than -- re-declaring problem and penalty structures -- * primitive data vs. derived API: -- primitive Chapter 10 data are the imported problem fields and `PenaltyFunction.penaltyTerm`; -- the exponential kernel `c ↦ exp (c 0)` is only a local bridge used to negate the -- normalization axiom `penaltyTerm_zero` theorem chapter10Exercise106_exponentialScalar_not_admissiblePenaltyTerm (problem : StandardPenaltyProblem n 1) : ¬ ∃ P : PenaltyFunction problem, P.penaltyTerm = (fun c : ConstraintPoint ↦ Real.exp (c 0))

Exercise 10.7

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Exercise 10.7: the centered log-sum-exp kernel is a strong distance function in the sense of Definition 10.6-extra-1, so the chapter's exact-penalty owners apply to it directly.

open scoped BigOperators variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m) -- Domain sampling: -- * `StandardPenaltyProblem`, `IsStrongDistanceFunction`, -- `StandardPenaltyProblem.nonsmoothExactPenalty`, and `PenaltyFunction.nonsmoothExact` -- from `Definition_10_6_extra_1` are the chapter's canonical owners for exact-penalty -- kernels, source-facing penalty objectives, and bundled penalty functions. -- * The source exercise adds only the log-sum-exp smoothing kernel on `ℝ^m` and its -- constant-offset relation to that existing exact-penalty layer. -- This file therefore keeps the source-facing `problem.logSumExpPenalty σ`, equips the -- centered kernel with the chapter's canonical strong-distance structure, and packages the -- resulting centered penalty function as `PenaltyFunction.logSumExp`, using the existing -- exact-penalty owners only as the implementation bridge. instance instIsStrongDistanceFunctionCenteredLogSumExpAbs : IsStrongDistanceFunction (centeredLogSumExpAbs : ConstraintPoint → ℝ)

Exercise 10.8

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Exercise 10.8: when the slack variables are chosen as yᵢ = max (cᵢ(x) - λᵢ / σᵢ) 0 on the inequality block, the augmented Lagrangian of the slack-variable reformulation agrees exactly with the chapter's mixed equality/inequality augmented Lagrangian problem.augmentedLagrangian lam σ x.

open scoped BigOperators variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m) theorem chapter10Exercise108_slackAugmentedLagrangian_eq_augmentedLagrangian (problem : StandardPenaltyProblem n m) (lam σ : ConstraintPoint) (hσ : ∀ i : Fin m, 0 < σ i) (x : Point) : problem.slackAugmentedLagrangian lam σ x (problem.optimalSlack lam σ x) = problem.augmentedLagrangian lam σ x

Exercise 10.9

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Exercise 10.9: direct recall of the Chapter 10 theorem stating that if x σ globally minimizes Fletcher's simple smooth exact penalty subproblem (10.5.5) for each positive penalty parameter σ, then the constraint residual norm is antitone in σ.

#check norm_constraint_le_of_isMinOn_fletcherSimpleSmoothExactPenaltyFunction

Exercise 10.10

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Exercise 10.10: direct recall of both theorem owners for Lemma 10.6.2.

#check nonsmoothExactPenaltyObjectiveValueMono

10.1 — Penalty Function

Lemma 10.1.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Lemma 10.1.1: let H ∈ ℝ^(n × n) be symmetric and A ∈ ℝ^(n × m). If dotProduct d (H.mulVec d) > 0 for every nonzero d with A.transpose.mulVec d = 0, then there exists σ ≥ 0 such that H + σ A Aᵀ is positive definite.

open Matrix variable {n m : ℕ} local notation "Point" => Fin n → ℝ local notation "HessianMatrix" => Matrix (Fin n) (Fin n) ℝ local notation "ConstraintMatrix" => Matrix (Fin n) (Fin m) ℝ theorem exists_nonneg_penalty_posDef_of_posOn_transposeKer (H : HessianMatrix) (A : ConstraintMatrix) (hHsymm : H.IsSymm) (hpos : ∀ d : Point, d ≠ 0 → Aᵀ.mulVec d = 0 → 0 < dotProduct d (H.mulVec d)) : ∃ σ : ℝ, 0 ≤ σ ∧ (H + σ • (A * Aᵀ)).PosDef

Definition 10.1.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

The feasible constraint-value set for an equality/inequality split with the first eqCount coordinates constrained to vanish and the remaining coordinates constrained to be nonnegative.

open Filter variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m) -- Domain sampling: -- * primary domain: Chapter 10 penalty methods for mixed equality/inequality constrained -- optimization problems on `ℝ^n` -- * inspected project owner/view declarations: -- `QuadraticProgram.lagrangian` together with the notation surface `ℒ[P]` and `Λ[P]` in -- Chapter 9 as the chapter's owner-notation precedent, -- `StandardPenaltyProblem.constraintViolation` and `PenaltyFunction` in this file as the -- source-facing problem owner and the penalty-layer owner, -- `PenaltyFunction.nonsmoothExact` in `Definition_10_6_extra_1` as direct downstream reuse of -- the same violation owner -- * best owner abstraction for the textbook object `c⁽-⁾(x)`: the problem-owned map -- `StandardPenaltyProblem.constraintViolation`; notation should therefore be a thin bridge, not -- a second owner -- * primitive data vs. derived API: -- primitive problem data are `eqCount`, `objective`, and `constraint`; -- `feasibleSet`, `constraintMap`, `constraintViolation`, and penalty evaluation are derived from -- that owner data def feasibleConstraintValueSet (eqCount : ℕ) : Set ConstraintPoint := {c | (∀ i : Fin m, i.1 < eqCount → c i = 0) ∧ ∀ i : Fin m, eqCount ≤ i.1 → 0 ≤ c i}

10.2 — The Simple Penalty Function Method

Lemma 10.2.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Lemma 10.2.1 (1): if 0 < σ₁ < σ₂ and x σ globally minimizes P_σ for every positive σ, with fixed exponent α, then P_(σ₁)(x σ₁) ≤ P_(σ₂)(x σ₂).

variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) -- Semantic recall: Section 10.2's source-facing family is the local notation `P_ σ` for -- `problem.simplePenaltyObjective σ α`, while `PenaltyFunction.simple` remains the canonical -- owner underneath and `IsMinOn` is the canonical global-minimizer API. variable (problem : StandardPenaltyProblem n m) {α : ℝ} local notation:max "P_" σ => problem.simplePenaltyObjective σ α theorem simplePenaltyMinValueMono (x : ℝ → Point) (hx : ∀ {σ : ℝ}, 0 < σ → IsMinOn (P_ σ) Set.univ (x σ)) {σ₁ σ₂ : ℝ} (hσ₁ : 0 < σ₁) (hσ₁₂ : σ₁ < σ₂) : (P_ σ₁) (x σ₁) ≤ (P_ σ₂) (x σ₂)

Lemma 10.2.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Lemma 10.2.2: if xσ solves the simple penalty subproblem with objective problem.simplePenaltyObjective σ α for a nonnegative penalty parameter σ and nonnegative exponent α, then it also minimizes problem.objective on the violation sublevel set {x | ‖c⁽-⁾(x)‖ ≤ ‖c⁽-⁾(xσ)‖}.

variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m) -- Semantic recall: Chapter 10 already owns the Section 10.2 source penalty objective as -- `problem.simplePenaltyObjective σ α`, so this lemma reuses that owner and adds only the -- source-facing violation sublevel set needed for the constrained conclusion. namespace StandardPenaltyProblem theorem isMinOnObjectiveOnSimplePenaltyViolationSublevelSet_of_isMinOn_simplePenaltyObjective (problem : StandardPenaltyProblem n m) {σ α : ℝ} (hσ : 0 ≤ σ) (hα : 0 ≤ α) (xσ : Point) (hxσ : IsMinOn (problem.simplePenaltyObjective σ α) Set.univ xσ) : IsMinOn problem.objective (simplePenaltyViolationSublevelSet problem.constraintViolation ‖problem.constraintViolation xσ‖) xσ

Algorithm 10.2.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Algorithm 10.2.3 reaches stage k + 1 exactly when stage k is reached and the source stopping test fails at stage k.

local notation:max "P_[" problem ", " α "](" σ ")" =>
  StandardPenaltyProblem.simplePenaltyObjective problem σ α

-- Domain sampling:
-- * primary domain: Chapter 10 simple-penalty methods for mixed equality/inequality constrained
--   problems in `ℝ^n`
-- * inspected project declarations of the same kind:
--   `StandardPenaltyProblem` and `c⁽-⁾[problem]` in `Definition_10_1_extra_1`,
--   `PenaltyFunction` in the same file as the canonical penalty-layer owner,
--   `StandardPenaltyProblem.simplePenaltyObjective` and `PenaltyFunction.simple` in
--   `Definition_10_2_extra_1`
-- * best owner abstraction: the source-facing stage objective belongs to
--   `StandardPenaltyProblem`; `PenaltyFunction.simple` is only the bundled bridge/view
-- * primitive data vs. derived API:
--   primitive data are the constrained problem, exponent, tolerance, the reached-stage
--   predicate, iterates, penalty parameters, and recorded reached-stage solves;
--   the stage penalty function, stopping predicate, and minimizer/update views are derived API
namespace SimplePenaltyFunctionMethod
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
theorem reached_succ_iff_not_terminatedAt
    (method : SimplePenaltyFunctionMethod n m) {k : ℕ} (hk : 1 ≤ k) :
    method.reached (k + 1) ↔ method.reached k ∧ ¬ method.terminatedAt k

Theorem 10.2.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Theorem 10.2.4: if the tolerance ε in Algorithm 10.2.3 is strictly larger than the minimum of x ↦ ‖c⁽-⁾[method.problem] x‖ on the ambient decision space, encoded here by a global minimizer xHat of the violation norm with ‖c⁽-⁾[method.problem] xHat‖ < ε, then the simple penalty function method terminates at some reached stage.

variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)

-- Semantic recall: Chapter 10 already owns the simple penalty method in
-- `Algorithm_10_2_3`, while `Theorem_10_2_5` owns the canonical minimal-violation value
-- `method.problem.minimalViolationValue`. This file keeps Theorem 10.2.4 source-facing through
-- the explicit minimizing-point hypothesis and adds only a thin bridge to that canonical owner.
theorem simplePenaltyFunctionMethod_finiteTermination
    (method : SimplePenaltyFunctionMethod n m)
    (hTol :
      ∃ xHat : Point,
        IsMinOn (fun x : Point ↦ ‖c⁽-⁾[method.problem] x‖) Set.univ xHat ∧
          ‖c⁽-⁾[method.problem] xHat‖ < method.tolerance) :
    ∃ k : ℕ, 1 ≤ k ∧ method.reached k ∧ method.terminatedAt k

Theorem 10.2.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Theorem 10.2.5 (1): if Algorithm 10.2.3 does not terminate finitely, then the minimal violation value of x ↦ ‖c⁽-⁾[method.problem] x‖ is at least the tolerance ε.

open Filter
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)

-- Semantic recall: `Algorithm_10_2_3` already owns the source-facing simple penalty method and
-- its stagewise stopping/minimizer API, while `StandardPenaltyProblem` owns the underlying
-- constraint-violation norm. This theorem file therefore keeps nontermination method-level, but
-- lifts the minimal-violation objects to the problem-level owner they actually depend on.
theorem simplePenaltyFunctionMethod_minimalViolationValue_ge_tolerance
    (method : SimplePenaltyFunctionMethod n m)
    (hNoTerminate : method.doesNotTerminateFinitely) :
    method.tolerance ≤ method.problem.minimalViolationValue

Corollary 10.2.6

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Corollary 10.2.6: if the original constrained problem has a feasible point, then Algorithm 10.2.3 either finitely terminates at a stage solution that also minimizes method.problem.objective on its attained violation sublevel set, or every accumulation point of the generated iterate sequence, encoded by a convergent subsequence x_(φ k + 1), solves the original problem, represented here by membership in method.problem.feasibleSet together with IsMinOn on that feasible set.

open Filter
open StandardPenaltyProblem
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)

-- Domain sampling:
-- * primary domain: Chapter 10 simple-penalty methods for mixed equality/inequality constrained
--   problems in `ℝ^n`
-- * inspected project declarations:
--   `StandardPenaltyProblem.feasibleSet` and
--   `StandardPenaltyProblem.mem_iff_constraintViolation_eq_zero` in
--   `Definition_10_1_extra_1` as the owner API for the original constrained problem,
--   `simplePenaltyViolationSublevelSet` in `Lemma_10_2_2` as the source-facing owner for the
--   attained violation sublevel sets,
--   `SimplePenaltyFunctionMethod.terminatedAt` in `Algorithm_10_2_3` as the stagewise stopping
--   owner,
--   `StandardPenaltyProblem.minimalViolationSet` and
--   `simplePenaltyFunctionMethod_accumulationPoint_isMinOn_minimalViolationSet` in
--   `Theorem_10_2_5` as the nontermination-side owner API
-- * best owner abstraction: `method.problem.feasibleSet` for "solves the original problem",
--   together with `simplePenaltyViolationSublevelSet` for the attained-violation finite branch
-- * primitive data vs. derived API:
--   primitive method data are the constrained problem, tolerance, iterates, and stage
--   subproblem minimizers already bundled by `SimplePenaltyFunctionMethod`;
--   attained-sublevel optimality is derived API, and original-problem feasibility/optimality
--   should reuse `method.problem.feasibleSet` rather than a parallel zero-sublevel wrapper
theorem simplePenaltyFunctionMethod_finiteTermination_or_accumulationPoint_solvesOriginalProblem
    (method : SimplePenaltyFunctionMethod n m)
    (hfeasible : Set.Nonempty method.problem.feasibleSet) :
    (∃ k : ℕ,
      1 ≤ k ∧
        method.reached k ∧
          method.terminatedAt k ∧
          method.subproblemSolution k ∈
            simplePenaltyViolationSublevelSet
              (c⁽-⁾[method.problem])
              ‖c⁽-⁾[method.problem] (method.subproblemSolution k)‖ ∧
          IsMinOn
            method.problem.objective
            (simplePenaltyViolationSublevelSet
              (c⁽-⁾[method.problem])
              ‖c⁽-⁾[method.problem] (method.subproblemSolution k)‖)
            (method.subproblemSolution k))
    ∨
      ∀ {xStar : Point} {φ : ℕ → ℕ},
        StrictMono φ →
        Tendsto (fun k : ℕ ↦ method.iterate (φ k + 1)) atTop (nhds xStar) →
        xStar ∈ method.problem.feasibleSet ∧
          IsMinOn method.problem.objective method.problem.feasibleSet xStar

Example 10.2.7

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Example 10.2.7 as a StandardPenaltyProblem with one equality constraint and no inequalities.

local notation "Point" => EuclideanSpace ℝ (Fin 2)

-- Primary domain: Chapter 10 penalty methods for constrained minimization in `ℝ²`.
-- Source-facing layer: the concrete objective, equality constraint, and closed-form solution data
-- of Example 10.2.7 together with the Section 10.2 stage objective `P_σ`.
-- Core/canonical layer inspected in the chapter: `StandardPenaltyProblem` for the constrained
-- problem, `StandardPenaltyProblem.simplePenaltyObjective` for the Section 10.2 owner,
-- `PenaltyFunction.simple` for the canonical penalty owner beneath that source view, and
-- `SimplePenaltyFunctionMethod` for Algorithm 10.2.3. The older
-- `PenaltyFunction.quadratic` specialization is therefore kept only as a bridge view in this
-- quadratic example.
-- Primitive data kept local: the concrete objective, constraint, constrained solution, penalty
-- shift, and closed-form stage minimizer. Derived API: the feasible-set theorems, the source
-- stage objective `P_σ`, and the method-level iterate statement.
def example1027Problem : StandardPenaltyProblem 2 1

Definition 10.2.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Source-facing layer for Chapter10 Definition 10.2-extra-1: for a fixed problem and exponent α, the Section 10.2 family P_σ is the stage objective x ↦ f(x) + σ * ‖c⁽-⁾[problem] x‖^α.

open Filter variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m) -- Domain sampling: -- * primary domain: Chapter 10 simple penalty functions for `StandardPenaltyProblem`. -- * inspected chapter/project owners of the same kind: -- `StandardPenaltyProblem.constraintViolation` and `PenaltyFunction` in -- `Definition_10_1_extra_1`, -- `PenaltyFunction.quadratic` there as the existing bundled penalty constructor for the same -- owner, -- `StandardPenaltyProblem.nonsmoothExactPenalty` and `PenaltyFunction.nonsmoothExact` in -- `Definition_10_6_extra_1` as the same source-facing/bridge split in a later section. -- * best owner abstraction: the Section 10.2 stage objective belongs to -- `StandardPenaltyProblem`; `PenaltyFunction.simple` is the bundled bridge/view under the -- positivity hypotheses. -- * primitive data vs. derived API: -- primitive data are the constrained problem, the penalty parameter `σ`, and the exponent `α`; -- the bundled `PenaltyFunction.simple` object is derived from that source-facing owner. namespace StandardPenaltyProblem def simplePenaltyObjective (problem : StandardPenaltyProblem n m) (σ α : ℝ) : Point → ℝ := fun x ↦ problem.objective x + σ * Real.rpow ‖c⁽-⁾[problem] x‖ α

10.3 — Interior Point Penalty Functions

Lemma 10.3.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Lemma 10.3.1 (2): under the same interior-point penalty minimizer hypotheses, the source barrier sum problem.barrierSum (x σ) is monotone in the opposite direction, so problem.barrierSum (x σ₂) ≥ problem.barrierSum (x σ₁) whenever 0 < σ₁ < σ₂.

namespace InteriorPointPenaltyProblem variable {Point : Type*} {ι : Type*} [Fintype ι] -- Semantic recall: `IsMinOn` is the canonical mathlib minimizer API, and -- `Definition_10_3_extra_1` now owns the strict-feasible and penalty-function surfaces. variable (problem : InteriorPointPenaltyProblem Point ι) (x : ℝ → Point) theorem barrierSum_monotone (hx : ∀ {σ : ℝ}, 0 < σ → x σ ∈ problem.strictFeasibleSet ∧ IsMinOn (problem.penaltyFunction σ) problem.strictFeasibleSet (x σ)) {σ₁ σ₂ : ℝ} (hσ₁ : 0 < σ₁) (hσ₁₂ : σ₁ < σ₂) : problem.barrierSum (x σ₂) ≥ problem.barrierSum (x σ₁)

Lemma 10.3.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Lemma 10.3.2: if δ = problem.barrierSum xσ for a solution xσ of the interior-point penalty subproblem with parameter σ > 0, and if the budget condition problem.barrierSum x ≤ δ forces strict feasibility, then xσ also solves min problem.objective x subject to problem.barrierSum x ≤ δ.

namespace InteriorPointPenaltyProblem variable {Point : Type*} {ι : Type*} [Fintype ι] -- Semantic recall: `IsMinOn` is the canonical minimizer API, while -- `Definition_10_3_extra_1` now owns the barrier sum and strict-feasible-region surfaces. theorem isMinOnObjectiveOnBarrierBudgetSet (problem : InteriorPointPenaltyProblem Point ι) {σ : ℝ} (hσ : 0 < σ) (xσ : Point) (hxσ : IsMinOn (problem.penaltyFunction σ) problem.strictFeasibleSet xσ) (h_budget_strict : ∀ ⦃x : Point⦄, problem.barrierSum x ≤ problem.barrierSum xσ → x ∈ problem.strictFeasibleSet) : IsMinOn problem.objective {x | problem.barrierSum x ≤ problem.barrierSum xσ} xσ

Algorithm 10.3.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Algorithm 10.3.3: an algorithm based on the interior point penalty function extends the Chapter 10 interior-point penalty problem on a decision space Point with finitely many inequality constraints indexed by ι by recording a tolerance ε ≥ 0, an initial strictly feasible point x₁ satisfying the source side condition (10.3.15), an initial barrier parameter σ₁ > 0, and for each active stage k ≥ 1 the current iterate x_k, the barrier parameter σ_k, and a selected solution x(σ_k) of the interior-point penalty subproblem. Step 2 is represented by requiring that, at each active stage, x(σ_k) minimizes method.toInteriorPointPenaltyProblem.penaltyFunction (σ_k) on method.toInteriorPointPenaltyProblem.strictFeasibleSet and that x_(k+1) = x(σ_k). Step 3 is represented by a recursive activity predicate: the stage k + 1 is active exactly when stage k is active and the source stopping inequality (1 / σ_k) * ∑ i, h (cᵢ(x_(k+1))) ≤ ε fails, and whenever the algorithm continues it updates σ_(k+1) = 10 * σ_k.

variable {Point : Type*} {ι : Type*} [Fintype ι] structure InteriorPointPenaltyFunctionMethod (Point : Type*) (ι : Type*) [Fintype ι] extends InteriorPointPenaltyProblem Point ι where tolerance : ℝ toleranceNonneg : 0 ≤ tolerance initialPoint : Point initialPoint_mem_strictFeasibleSet : initialPoint ∈ toInteriorPointPenaltyProblem.strictFeasibleSet initialPenaltyParameter : ℝ initialPenaltyParameterPos : 0 < initialPenaltyParameter active : ℕ → Prop iterate : ℕ → Point penaltyParameter : ℕ → ℝ subproblemSolution : ℕ → Point active_one : active 1 iterate_one : iterate 1 = initialPoint penaltyParameter_one : penaltyParameter 1 = initialPenaltyParameter subproblemSolution_spec (k : ℕ) (_ : 1 ≤ k) (_ : active k) : IsMinOn (toInteriorPointPenaltyProblem.penaltyFunction (penaltyParameter k)) toInteriorPointPenaltyProblem.strictFeasibleSet (subproblemSolution k) iterate_succ (k : ℕ) (_ : 1 ≤ k) (_ : active k) : iterate (k + 1) = subproblemSolution k active_succ_iff (k : ℕ) (_ : 1 ≤ k) : active (k + 1) ↔ active k ∧ ¬ ((1 / penaltyParameter k) * toInteriorPointPenaltyProblem.barrierSum (iterate (k + 1)) ≤ tolerance) penaltyParameter_update (k : ℕ) (_ : 1 ≤ k) (_ : active k) (_ : active (k + 1)) : penaltyParameter (k + 1) = 10 * penaltyParameter k

Theorem 10.3.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Theorem 10.3.4 (1): if f is bounded below on the feasible region X and ε > 0, then Algorithm 10.3.3 terminates finitely at an active stage.

open Filter variable {Point : Type*} {ι : Type*} [Fintype ι] theorem interiorPointPenaltyFunctionMethod_terminatesFinitely (method : InteriorPointPenaltyFunctionMethod Point ι) (hTolerance : 0 < method.tolerance) (hBoundedBelow : BddBelow (method.objective '' method.toInteriorPointPenaltyProblem.feasibleSet)) : method.terminatesFinitely

Algorithm 10.3.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Algorithm 10.3.5: an inexact log-barrier function method records an objective f, inequality constraints cᵢ, explicit Hessian matrix fields for f and the cᵢ, a tolerance ε ≥ 0, an initial point x₁ together with an explicit field initialState_satisfies10315 formalizing the source side condition (10.3.15) as strict interiority, and an initial barrier parameter σ₁ > 0, packaged as an explicit initial Step-2 state carrying x₁, σ₁, and the Newton direction from (10.3.42). The dynamic part of the source algorithm is exposed through IsStageState, StepSizeSpec, and Transition: IsStageState says that a state is strictly interior, has positive penalty parameter, has a nonsingular Newton matrix, and records the exact direction formula (10.3.42); StepSizeSpec encodes Step 3; and Transition separates the four textbook Step-2/Step-4 branches, including the same-stage update σ := 10 * σ with unchanged x before recomputation at the same textbook stage.

open scoped BigOperators Gradient variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ -- Domain sampling: -- * `InteriorPointPenaltyProblem` in `Definition_10_3_extra_1` is the chapter's core owner for -- interior-point objective/constraint/barrier data. -- * `InteriorPointPenaltyProblem.strictFeasibleSet` and `.barrierSum` are the canonical derived -- strict-feasibility and barrier-budget surfaces in this domain. -- * `InteriorPointPenaltyFunctionMethod` in `Algorithm_10_3_3` and `Theorem_10_3_4` already -- reuses those same strict-feasible and barrier-sum ideas downstream. -- This file therefore keeps the Newton-system data source-facing, but reuses the existing -- interior-point owner for the strict-feasible and log-barrier-sum surfaces instead of -- duplicating them locally. structure InexactLogBarrierFunctionMethod (n m : ℕ) where objective : EuclideanSpace ℝ (Fin n) → ℝ constraint : Fin m → EuclideanSpace ℝ (Fin n) → ℝ objectiveHessian : EuclideanSpace ℝ (Fin n) → Matrix (Fin n) (Fin n) ℝ constraintHessian : Fin m → EuclideanSpace ℝ (Fin n) → Matrix (Fin n) (Fin n) ℝ objective_hessian : IsHessianMatrixField objective objectiveHessian constraint_hessian : ∀ i : Fin m, IsHessianMatrixField (constraint i) (constraintHessian i) tolerance : ℝ toleranceNonneg : 0 ≤ tolerance initialState : InexactLogBarrierStageState n m /-- The source initial-point side condition `(10.3.15)` is recorded here as strict interiority of `x₁` for the inequalities `cᵢ(x) ≥ 0`. -/ initialState_satisfies10315 : ∀ i : Fin m, 0 < constraint i initialState.iterate initialPenaltyParameterPos : 0 < initialState.penaltyParameter initialNewtonMatrix_nonsingular : logBarrierNewtonMatrixNonsingular constraint objectiveHessian constraintHessian initialState.penaltyParameter initialState.iterate initialDirection_eq : initialState.direction = logBarrierDirection objective constraint objectiveHessian constraintHessian initialState.penaltyParameter initialState.iterate

Definition 10.3.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Definition 10.3-extra-1: an interior point penalty problem on a decision space Point with finitely many inequality constraints indexed by ι consists of an objective f, constraint functions cᵢ, a nonempty strict feasible region {x | ∀ i, 0 < cᵢ(x)}, and a barrier term h whose values become arbitrarily large as c → 0+ and which decreases as the constraint value increases. The associated penalty objective is Pσ(x) = f x + (1 / σ) * ∑ i, h (cᵢ x), to be minimized on the strict feasible region.

open scoped BigOperators -- Domain sampling: -- * `StandardPenaltyProblem` in `Definition_10_1_extra_1` is the chapter's canonical owner for -- objective/constraint/feasible-set data. -- * `PenaltyFunction` in the same file keeps penalty-specific data separate from that owner. -- * `InteriorPointPenaltyFunctionMethod` in `Algorithm_10_3_3` uses the same strict-feasibility -- and barrier-penalty surfaces downstream. -- This file therefore keeps only the barrier-specific source data in the owner, exposes the -- intrinsic strict-feasible and penalty-function API generically over a decision type and finite -- constraint index type, and adds a thin bridge back to the chapter's concrete -- `StandardPenaltyProblem` surface when the ambient space is `EuclideanSpace ℝ (Fin n)`. variable {Point : Type*} {ι : Type*} [Fintype ι] structure InteriorPointPenaltyProblem (Point : Type*) (ι : Type*) [Fintype ι] where objective : Point → ℝ constraint : ι → Point → ℝ strictFeasibleSet_nonempty : Set.Nonempty {x : Point | ∀ i : ι, 0 < constraint i x} barrier : ℝ → ℝ barrier_large_near_zero : ∀ R : ℝ, ∃ δ > 0, ∀ ⦃c : ℝ⦄, 0 < c → c < δ → R < barrier c barrier_antitone : ∀ ⦃c₁ c₂ : ℝ⦄, 0 < c₁ → c₁ < c₂ → barrier c₂ ≤ barrier c₁

10.4 — Augmented Lagrangian Method

Algorithm 10.4.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Algorithm 10.4.1: an augmented Lagrangian method records a constrained problem problem, a tolerance ε ≥ 0, an initial point x₁, initial multipliers λ⁽¹⁾ whose inequality coordinates are nonnegative, and an initial penalty vector σ⁽¹⁾. For each stage k ≥ 1, the algorithm records the current primal iterate x_k, multiplier vector λ⁽k⁾, and positive componentwise penalty vector σ⁽k⁾, with σ⁽¹⁾ identified with the initial penalty vector. Step 2 requires x_(k+1) to be an approximate minimizer of the concrete stage objective problem.augmentedLagrangian (λ⁽k⁾) (σ⁽k⁾), Step 3 uses the source test (10.4.11) |c⁽-⁾ᵢ(x_(k+1))| ≤ (1 / 4) * |c⁽-⁾ᵢ(x_k)|, and Step 4 updates λ⁽k+1⁾ by the concrete formula (10.4.7)-(10.4.8). The method stops when ‖c⁽-⁾(x_(k+1))‖∞ ≤ ε; otherwise Step 3 updates σᵢ⁽k+1⁾ = σᵢ⁽k⁾ if (10.4.11) holds and σᵢ⁽k+1⁾ = max (10 * σᵢ⁽k⁾) (k²) otherwise.

open scoped BigOperators variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m) structure AugmentedLagrangianMethod (n m : ℕ) where problem : StandardPenaltyProblem n m tolerance : ℝ toleranceNonneg : 0 ≤ tolerance initialPoint : EuclideanSpace ℝ (Fin n) initialMultiplier : EuclideanSpace ℝ (Fin m) initialMultiplier_nonneg : ∀ i : Fin m, problem.eqCount ≤ i.1 → 0 ≤ initialMultiplier i initialPenaltyParameter : EuclideanSpace ℝ (Fin m) iterate : ℕ → EuclideanSpace ℝ (Fin n) multiplier : ℕ → EuclideanSpace ℝ (Fin m) penaltyParameter : ℕ → EuclideanSpace ℝ (Fin m) penaltyParameterPos : ∀ k, 1 ≤ k → ∀ i : Fin m, 0 < penaltyParameter k i iterate_one : iterate 1 = initialPoint multiplier_one : multiplier 1 = initialMultiplier penaltyParameter_one : penaltyParameter 1 = initialPenaltyParameter approximateMinimizer_spec : ∀ k, 1 ≤ k → (problem.augmentedLagrangian (multiplier k) (penaltyParameter k)).IsApproximateMinimizer (iterate (k + 1)) stop_or_step : ∀ k, 1 ≤ k → problem.linftyConstraintViolation (iterate (k + 1)) ≤ tolerance ∨ (∀ i : Fin m, penaltyParameter (k + 1) i = if problem.penaltyUpdateTest (iterate k) (iterate (k + 1)) i then penaltyParameter k i else max (10 * penaltyParameter k i) ((k : ℝ) ^ (2 : ℕ))) ∧ multiplier (k + 1) = problem.multiplierUpdate (multiplier k) (penaltyParameter k) (iterate (k + 1))

Theorem 10.4.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Theorem 10.4.2: let the feasible region X of problem (10.1.1)-(10.1.3) be nonempty. Then for some ε > 0, Algorithm 10.4.1 is either finitely terminated, or the sequence {x_k} produced by Algorithm 10.4.1 satisfies liminf_{k → ∞} f(x_k) = -∞, encoded here by saying that the objective values f(x_k) lie below every real threshold frequently along atTop. In the current Chapter 10 API, a produced sequence is represented by a recorded run method : AugmentedLagrangianMethod n m whose stored problem and tolerance match the source parameters. Since the source theorem speaks about one sequence produced by Algorithm 10.4.1, the theorem keeps the source existential choice of a positive tolerance ε together with a recorded run having those source parameters, and states the source alternative for that run.

variable {n m : ℕ} theorem augmentedLagrangianMethod_existsTolerance_finiteTermination_or_liminfBot (problem : StandardPenaltyProblem n m) (hFeasible : Set.Nonempty problem.feasibleSet) : ∃ ε : ℝ, 0 < ε ∧ ∃ method : AugmentedLagrangianMethod n m, method.finiteTerminationOrObjectiveLiminfBot problem ε

Theorem 10.4.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Theorem 10.4.3 (2): under the same nonempty-feasible-region and zero-tolerance hypotheses, if the multiplier sequence λ⁽k⁾ is bounded, then any accumulation point xStar of the sequence x_k generated by Algorithm 10.4.1, encoded by a convergent subsequence x_(φ k + 1), solves the original problem (10.1.1)-(10.1.3), recorded by the canonical Chapter 10 mixed-constraint minimizer owner method.problem.IsGlobalMinimizer xStar. The generated-sequence context is bundled in AugmentedLagrangianTheorem1043Run, which also records the source bounded-multiplier route to (10.4.27) needed by the textbook proof; the continuity assumptions used at the accumulation point are exposed by method.AccumulationPointHypotheses.

open Filter variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) namespace AugmentedLagrangianMethod theorem accumulationPoint_solvesProblem_of_boundedMultipliers (method : AugmentedLagrangianTheorem1043Run n m) (hFeasible : Set.Nonempty method.problem.feasibleSet) (hTolerance : method.tolerance = 0) (hSource : method.AccumulationPointHypotheses) (hMultiplierBounded : Bornology.IsBounded (Set.range fun k : ℕ ↦ method.multiplier (k + 1))) {xStar : Point} {φ : ℕ → ℕ} (hφ : StrictMono φ) (hxStar : Tendsto (fun k : ℕ ↦ method.iterate (φ k + 1)) atTop (nhds xStar)) : method.problem.IsGlobalMinimizer xStar

Remark 10.4.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

If every constraint is an equality constraint, the chapter's augmented Lagrangian reduces to the quadratic-penalty-corrected Lagrangian from the equality-only case.

open scoped BigOperators variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m) namespace StandardPenaltyProblem theorem augmentedLagrangian_eq_of_eqCount_eq (problem : StandardPenaltyProblem n m) (lam σ : ConstraintPoint) (x : Point) (hEq : problem.eqCount = m) : problem.augmentedLagrangian lam σ x = problem.objective x + ∑ i : Fin m, (-(lam i) * problem.constraint i x + (1 / 2 : ℝ) * σ i * (problem.constraint i x) ^ (2 : ℕ))

10.5 — Smooth Exact Penalty Functions

Definition 10.5.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

The equality-feasible set c(x) = 0 for an equality-constrained problem on ℝ^n.

open scoped BigOperators
variable {n m : ℕ}

-- Source/core/bridge triage:
-- * source-facing layer here: Fletcher's equality-constrained smooth exact penalty data and the
--   source theorems attached to `(10.5.3)`-`(10.5.5)`.
-- * reused canonical owners: `IsStrictLocalMinOn` from Chapter 8 together with its unconstrained
--   specialization `IsStrictLocalMin`, `isMinOn_univ_iff` for whole-space global minimizers, and
--   the Euclidean matrix action `Matrix.toEuclideanLin`.
-- * item-local foundation imports: `constraintJacobian`,
--   `isConstraintJacobianPseudoInverseField`, `fletcherMultiplierEstimate1023`,
--   `equalitySmoothExactPenaltyFunction`, `simpleSmoothExactPenaltyFunction`, and
--   `constantConstraintPoint`.
-- * local chapter-specific owners retained here: the equality-feasible set, linearized feasible
--   directions, and the labeled Fletcher source-facing declarations/theorems.
def equalityFeasibleSet
    (c : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)) :
    Set (EuclideanSpace ℝ (Fin n)) :=
  {x | c x = 0}

Definition 10.5.extra.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

The matrix whose ith column is the chosen gradient vector gradConstraint i x.

open scoped BigOperators
variable {n m : ℕ}

-- Local notation justification (file-local vocabulary): Chapter 10 optimization files use
-- `Point` and `MultiplierVec` as readable Euclidean-space shorthands, and keeping them local
-- avoids introducing public alias owners for ambient types that this item does not own.
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MultiplierVec" => EuclideanSpace ℝ (Fin m)

-- Domain-style sampling pass:
-- * primary domain: Chapter 10 equality-constrained smooth exact penalty functions and their
--   linearized subproblems.
-- * sampled owner declarations in the minimal project closure:
--   - `equalitySmoothExactPenaltyFunction`
--   - `simpleSmoothExactPenaltyFunction`
--   - `constantConstraintPoint`
--   - `fletcherSimpleSmoothExactPenaltyFunction`
-- * best owner abstraction: `Definition_10_5_extra_1.equalitySmoothExactPenaltyFunction`.
-- * primitive data kept here: the explicit multiplier field
--   `equalitySmoothExactPenaltyMultiplier` and the correction matrix
--   `equalitySmoothExactPenaltyCorrection`.
-- * derived API here: bridge comments pointing back to that owner, together with the associated
--   linearized multiplier/dual statements.
--
-- Source/core/bridge triage:
-- * source-facing layer here: the explicit multiplier formula and the linearized subproblem
--   predicates attached to Definition 10.5-extra-2.
-- * core/canonical owners reused here:
--   `equalitySmoothExactPenaltyFunction` from `Definition_10_5_extra_1`,
--   `equalitySmoothExactPenaltySubproblemObjective`,
--   `generalSmoothExactPenaltyFeasibleSet`,
--   `isGeneralSmoothExactPenaltySubproblemMultiplier`,
--   and the Euclidean matrix action `Matrix.toEuclideanLin`.
-- * bridge/view retained here:
--   `constraintGradientMatrix`, which packages an explicit gradient family into the Jacobian
--   matrix used by `HasFDerivAt`, and the equality-case specialization lemmas relating the
--   matrix-based subproblem formulas to the general gradient-family owner.
def constraintGradientMatrix
    (gradConstraint : Fin m → Point → Point) (x : Point) :
    Matrix (Fin n) (Fin m) ℝ :=
  fun j i ↦ gradConstraint i x j

Definition 10.5.extra.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Definition 10.5-extra-3: for an equality-constrained problem with objective f, constraint map c, gradient-like term g, matrix fields A and M, penalty parameters σ and ρ, the smooth exact penalty function is `(x, λ) ↦ f x - dotProduct (c x) λ + (1 / 2) * σ * ‖c x‖ ^ 2 + (1 / 2) * ρ * ‖(M x).mulVec (g x - (A x).mulVec λ)‖ ^ 2`. The source allows M x to be chosen, for example, as (A x)ᵀ, a generalized inverse of A x, or the identity matrix.

open Matrix
variable {n m p q : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "GradientPoint" => EuclideanSpace ℝ (Fin p)
local notation "ResidualPoint" => EuclideanSpace ℝ (Fin q)

-- Sampled owner declarations in the Chapter 10 smooth-penalty domain:
-- * `simpleSmoothExactPenaltyFunction` in `Definition_10_5_extra_1` is the chapter's
--   core/canonical equal-parameter smooth exact penalty owner.
-- * `equalitySmoothExactPenaltyFunction` in `Definition_10_5_extra_1` is the diagonal-penalty
--   generalization upstream.
-- * the present `(10.5.17)` formula is the source-facing extension that adds the extra
--   residual-square term involving `g`, `A`, `M`, `ρ`, and the free multiplier variable `λ`.
def smoothExactPenaltyFunction
    (f : Point → ℝ)
    (c : Point → ConstraintPoint)
    (g : Point → GradientPoint)
    (A : Point → Matrix (Fin p) (Fin m) ℝ)
    (M : Point → Matrix (Fin q) (Fin p) ℝ)
    (σ ρ : ℝ) (x : Point) (lam : ConstraintPoint) : ℝ :=
  simpleSmoothExactPenaltyFunction f (fun _ ↦ lam) c σ x +
    (1 / 2 : ℝ) * ρ * ‖(M x).mulVec (g x - (A x).mulVec lam)‖ ^ (2 : ℕ)

10.6 — Nonsmooth Exact Penalty Functions

Theorem 10.6.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Theorem 10.6.1: let xStar and the corresponding multiplier vector lamStar satisfy the second-order sufficient condition on problem.linearizedFeasibleDirectionSet xStar. If h is a strong distance function on ConstraintPoint, if δ is a positive lower ℓ₁ bound constant for h, and if σ * δ > ‖lamStar‖∞, then xStar is a strict local minimizer of the nonsmooth exact penalty function problem.nonsmoothExactPenalty h σ. The local-minimum assumption from the prose is omitted because it is already implied by the second-order sufficient condition.

open Filter
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "∇" => @gradient ℝ Point _ _ _ _

-- Domain sampling:
-- * `StandardPenaltyProblem`, `problem.feasibleSet`, and the source notation `c⁽-⁾[problem]`
--   are already owned by `Definition_10_1_extra_1`.
-- * `StandardPenaltyProblem.toConstrainedOptimizationProblem` and
--   `StandardPenaltyProblem.IsGlobalMinimizer` are the chapter's reusable mixed-constraint
--   bridge/view owners in `StandardPenaltyProblemBridge`.
-- * `ConstrainedOptimizationProblem.IsKKTPoint`,
--   `ConstrainedOptimizationProblem.linearizedFeasibleDirectionSet`, and
--   `ConstrainedOptimizationProblem.lagrangianHessianQuadratic` in Chapter 8 are the canonical
--   constrained-optimization owners reused here through a mixed-constraint bridge.
-- * `IsStrongDistanceFunction` is the chapter's canonical kernel owner from
--   `Definition_10_6_extra_1`.
-- * `IsStrictLocalMin` is the canonical strict local minimizer owner from
--   `Chapter01.Definition_1_4_1`.
-- This file therefore keeps the Chapter 10 source-facing SOSC surface and strict-penalty
-- conclusion while presenting its KKT, feasible-direction, and Hessian APIs as thin bridges to
-- the Chapter 8 constrained-optimization owners.
theorem isStrictLocalMin_nonsmoothExactPenalty_of_secondOrderSufficientCondition
    (problem : StandardPenaltyProblem n m) (xStar : Point) (lamStar : ConstraintPoint)
    (σ δ : ℝ) (h : ConstraintPoint → ℝ) [IsStrongDistanceFunction h]
    (h_sosc : problem.SecondOrderSufficientCondition xStar lamStar)
    (hδ : 0 < δ)
    (h_lower_l1 : ∀ c : ConstraintPoint, δ * ‖c‖₁ ≤ h c)
    (h_sigma : σ * δ > ‖lamStar‖∞) :
    IsStrictLocalMin (problem.nonsmoothExactPenalty h σ) xStar

Lemma 10.6.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Lemma 10.6.2 (1): if 0 < σ₁ < σ₂ and x σ globally minimizes the chapter's source exact-penalty objective problem.nonsmoothExactPenalty h σ for every positive σ, then f (x σ₂) ≥ f (x σ₁).

variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m) -- Domain sampling: -- * `StandardPenaltyProblem` from `Definition_10_1_extra_1` is the chapter's source-facing owner -- for mixed equality/inequality constrained problems. -- * `StandardPenaltyProblem.nonsmoothExactPenalty` from `Definition_10_6_extra_1` is the -- source-facing owner for the nonsmooth exact penalty `x ↦ f(x) + σ * h(c⁽-⁾(x))`. -- * Section 10.2's local notation `P_σ` in `Lemma_10_2_1` is the chapter's notation precedent -- for repeated penalty-stage objectives once the ambient problem data are fixed. -- * `PenaltyFunction.nonsmoothExact` remains the bundled bridge/view once `σ > 0` is used to -- package that objective as a `PenaltyFunction`. -- * `IsMinOn` is the canonical mathlib minimizer predicate. -- This lemma is therefore source-facing theorem API built on the existing exact-penalty owner, -- not a second local penalty-object definition. variable (problem : StandardPenaltyProblem n m) theorem nonsmoothExactPenaltyObjectiveValueMono (h : ConstraintPoint → ℝ) (x : ℝ → Point) (hx : ∀ {σ : ℝ}, 0 < σ → IsMinOn (problem.nonsmoothExactPenalty h σ) Set.univ (x σ)) {σ₁ σ₂ : ℝ} (hσ₁ : 0 < σ₁) (hσ₁₂ : σ₁ < σ₂) : problem.objective (x σ₂) ≥ problem.objective (x σ₁)

Lemma 10.6.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Lemma 10.6.3: if xσ solves the nonsmooth exact penalty subproblem min_x problem.objective x + σ * h (c⁽-⁾[problem] x) on ℝ^n, and η = h (c⁽-⁾[problem] xσ), then xσ also solves the constrained problem min_x problem.objective x subject to h (c⁽-⁾[problem] x) ≤ η, for any σ ≥ 0.

variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m) -- Domain sampling: -- * `StandardPenaltyProblem` from `Definition_10_1_extra_1` is the chapter's source-facing owner -- for mixed equality/inequality constrained problems. -- * `StandardPenaltyProblem.nonsmoothExactPenalty` and -- `StandardPenaltyProblem.nonsmoothExactPenaltySublevelSet` from -- `Definition_10_6_extra_1` are the source-facing exact-penalty owner and its sublevel-set -- view. -- * `IsMinOn` is the canonical mathlib minimizer predicate. -- This lemma therefore reuses the Chapter 10 exact-penalty owner directly instead of restating -- the problem, violation, and kernel API locally. theorem isMinOnObjectiveOnNonsmoothExactPenaltySublevelSet (problem : StandardPenaltyProblem n m) (h : ConstraintPoint → ℝ) {σ : ℝ} (hσ : 0 ≤ σ) (xσ : Point) (hxσ : IsMinOn (problem.nonsmoothExactPenalty h σ) Set.univ xσ) : IsMinOn problem.objective (problem.nonsmoothExactPenaltySublevelSet h (h (c⁽-⁾[problem] xσ))) xσ

Algorithm 10.6.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Algorithm 10.6.4: if the method terminates at a reached stage k, then no later stage j > k is reached.

variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)

-- Domain sampling:
-- * primary domain: Chapter 10 nonsmooth exact penalty methods for mixed constrained
--   optimization problems.
-- * inspected owner declarations:
--   `StandardPenaltyProblem.constraintViolation` and `PenaltyFunction` in
--   `Definition_10_1_extra_1`,
--   `IsStrongDistanceFunction`, the Chapter 1 `ℓ₁` notation `‖·‖₁`, and
--   `PenaltyFunction.nonsmoothExact` in
--   `Definition_10_6_extra_1`,
--   `SimplePenaltyFunctionMethod.terminatedAt` in `Algorithm_10_2_3` as the chapter's
--   algorithm-layer precedent.
-- * best owner abstraction: the source-facing stage objective
--   `problem.nonsmoothExactPenalty penaltyKernel σ`, with `PenaltyFunction.nonsmoothExact` only
--   as the bundled bridge/view once positivity is needed.
-- * primitive data vs derived API: the method stores the stagewise problem/kernel/iterate data
--   and minimizer certificates; the stage penalty function and the stopping predicate are
--   derived bridge API.
namespace NonsmoothExactPenaltyMethod
theorem not_reached_of_terminatedAt
    (method : NonsmoothExactPenaltyMethod n m) {k j : ℕ} (hk : 1 ≤ k)
    (hreached : method.reached k) (hterm : method.terminatedAt k) (hkj : k < j) :
    ¬ method.reached j

Theorem 10.6.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Theorem 10.6.5: let method be Algorithm 10.6.4 and assume the objective method.problem.objective and every constraint method.problem.constraint i are twice continuously differentiable, and that the feasible set method.problem.feasibleSet is nonempty. If every local minimizer of the constrained problem satisfies the Chapter 10 second-order sufficient condition (10.6.3) with some multiplier vector, then either Algorithm 10.6.4 terminates finitely at a strict local minimizer of the original constrained problem, or the generated iterate sequence satisfies ‖x_k‖ → ∞.

open Filter
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)

-- Domain sampling:
-- * `NonsmoothExactPenaltyMethod` in `Algorithm_10_6_4` is the chapter's algorithm owner.
-- * `StandardPenaltyProblem.SecondOrderSufficientCondition` in `Theorem_10_6_1` is the
--   chapter's canonical SOSC owner.
-- * `IsStrictLocalMinOn` in `Chapter08.Definition_8_1_3` is the canonical constrained strict
--   local-minimum owner.
-- * `StandardPenaltyProblem.nonsmoothExactPenalty` in `Definition_10_6_extra_1` is the
--   canonical exact-penalty owner already used by the algorithm layer.
-- This file therefore keeps only the convergence layer specific to Theorem 10.6.5.
theorem finiteTerminationAt_strictLocalMinimizer_or_iterateNorm_tendsto_atTop
    (method : NonsmoothExactPenaltyMethod n m)
    (h_objectiveContDiff : ContDiff ℝ 2 method.problem.objective)
    (h_constraintContDiff : ∀ i, ContDiff ℝ 2 (method.problem.constraint i))
    (hfeasible : Set.Nonempty method.problem.feasibleSet)
    (h_sosc :
      ∀ ⦃xStar : Point⦄,
        IsLocalMinOn method.problem.objective method.problem.feasibleSet xStar →
          ∃ lamStar : ConstraintPoint,
            method.problem.SecondOrderSufficientCondition xStar lamStar) :
    method.terminatesFinitelyAtStrictLocalMinimizer ∨
      Tendsto (fun k : ℕ ↦ ‖method.iterate (k + 1)‖) atTop atTop

Lemma 10.6.6

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Lemma 10.6.6: if h (c⁽-⁾[problem] xBar) = 0 and xBar is a local minimizer of the nonsmooth exact penalty objective problem.nonsmoothExactPenalty h σ, then xBar is also a local minimizer of the constrained optimization problem, i.e. of problem.objective on problem.feasibleSet. The source's positivity assumption σ > 0 is redundant for this implication, so the source-facing statement omits it.

variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m) -- Layer choice: -- * source-facing owner: `StandardPenaltyProblem.nonsmoothExactPenalty`; -- * core/canonical owner: `PenaltyFunction`; -- * bridge/view: `PenaltyFunction.nonsmoothExact`. -- This lemma keeps the source-facing objective as the main surface and adds only the minimal -- bridge API needed to pass from `h (c⁽-⁾[problem] x) = 0` to feasibility. theorem isLocalMinOn_objective_on_feasibleSet_of_isLocalMinOn_nonsmoothExactPenalty (problem : StandardPenaltyProblem n m) (h : ConstraintPoint → ℝ) [IsStrongDistanceFunction h] {σ : ℝ} {xBar : Point} (h_zero : h (c⁽-⁾[problem] xBar) = 0) (h_localMin : IsLocalMinOn (problem.nonsmoothExactPenalty h σ) Set.univ xBar) : IsLocalMinOn problem.objective problem.feasibleSet xBar

Theorem 10.6.7

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Theorem 10.6.7: let xStar be a local minimizer of the constrained problem problem.objective on problem.feasibleSet and let lamStar be a corresponding Lagrange multiplier. If LICQ holds at xStar for the active constraint gradients, if h is a strong distance function with lower ℓ₁ bound constant δ, and if σ * δ > ‖lamStar‖∞, then xStar is also a local minimizer of the nonsmooth exact penalty function problem.nonsmoothExactPenalty h σ.

variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)

-- Domain sampling:
-- * `StandardPenaltyProblem.nonsmoothExactPenalty` and `IsStrongDistanceFunction` in
--   `Definition_10_6_extra_1` are the canonical Chapter 10 exact-penalty owners.
-- * `StandardPenaltyProblem.activeConstraintSet`, `StandardPenaltyProblem.LicqAt`, and
--   `StandardPenaltyProblem.toConstrainedOptimizationProblem` in
--   `StandardPenaltyProblemBridge` are the chapter's canonical active-set, LICQ, and bridge
--   owners.
-- * `StandardPenaltyProblem.IsLagrangeMultiplier` in `Theorem_10_6_1` is the chapter's
--   mixed-constraint KKT owner.
-- * `IsLocalMin` in Chapter 1 is the canonical unconstrained local-minimum owner, while
--   `IsLocalMinOn` remains the constrained owner for the source hypothesis on
--   `problem.feasibleSet`.
-- This file therefore uses the consolidated Chapter 10 source-facing bridge surface and states
-- Theorem 10.6.7 with the canonical Chapter 1 local-minimum owners and the canonical Chapter 10
-- LICQ owner.
theorem isLocalMin_nonsmoothExactPenalty_of_isLagrangeMultiplier_of_licq
    (problem : StandardPenaltyProblem n m) (xStar : Point) (lamStar : ConstraintPoint)
    (σ δ : ℝ) (h : ConstraintPoint → ℝ) [IsStrongDistanceFunction h]
    (h_localMin : IsLocalMinOn problem.objective problem.feasibleSet xStar)
    (h_multiplier : problem.IsLagrangeMultiplier xStar lamStar)
    (h_licq : problem.LicqAt xStar)
    (hδ : 0 < δ)
    (h_lower_l1 : ∀ c : ConstraintPoint, δ * ‖c‖₁ ≤ h c)
    (h_sigma : σ * δ > ‖lamStar‖∞) :
    IsLocalMin (problem.nonsmoothExactPenalty h σ) xStar

Theorem 10.6.8

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter10 Theorem 10.6.8: write T for the maximum norm over Euclidean subgradients v ∈ ∂ h(0). If 0 ≤ σ and σ * ‖fderiv ℝ (c⁽-⁾[problem]) xStar‖ < ‖gradient problem.objective xStar‖ / T, then xStar is not stationary for the exact-penalty objective problem.nonsmoothExactPenalty h σ. The source's local-minimizer preamble and explicit nonzero-gradient hypothesis are omitted because this obstruction is purely pointwise and the displayed strict inequality already forces ‖gradient problem.objective xStar‖ > 0.

variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m) -- Domain sampling: -- * `StandardPenaltyProblem.nonsmoothExactPenalty` in `Definition_10_6_extra_1` is the -- canonical Chapter 10 exact-penalty owner. -- * `subgradientNormSet` is the source-facing owner for the maximal Euclidean norm bound on -- `∂ h 0`, expressed directly by the Euclidean affine-support inequality -- `h y ≥ h 0 + ⟪v, y⟫` for all `y`. -- * `ContinuousLinearMap.adjoint` is the canonical calculus owner for the transposed derivative -- term appearing in the source subgradient representation. -- This file therefore keeps only the source stationarity/norm-obstruction layer, reuses the -- chapter's exact-penalty owner directly, and records the subgradient condition in its Euclidean -- affine-support form. namespace StandardPenaltyProblem theorem not_isPenaltyStationaryAt_of_norm_mul_lt_gradient_norm_div_subgradientMax (problem : StandardPenaltyProblem n m) (h : ConstraintPoint → ℝ) (σ T : ℝ) (xStar : Point) (hT : IsGreatest (subgradientNormSet h) T) (hσ_nonneg : 0 ≤ σ) (hσ : σ * ‖fderiv ℝ (c⁽-⁾[problem]) xStar‖ < ‖gradient problem.objective xStar‖ / T) : ¬ problem.IsPenaltyStationaryAt h σ xStar

Definition 10.6.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

The Chapter 1 ℓ^∞ norm transported to the Euclidean-space model EuclideanSpace ℝ (Fin m).

open Filter open scoped BigOperators variable {n m : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m) -- Domain sampling: -- * `sunYuanL1Norm` and the notation `‖·‖₁` in `Chapter01.Definition_1_2_1` are the chapter's -- canonical `ℓ₁` owners on finite coordinate spaces. -- * `StandardPenaltyProblem` in `Definition_10_1_extra_1` is the chapter's source-facing owner -- for mixed equality/inequality constrained problems. -- * `PenaltyFunction` in the same file is the canonical penalty-layer owner above that problem -- data. -- * `ConvexOn` remains the core/canonical convex-analysis owner for the new kernel property in -- this file. -- This file therefore adds only the Section 10.6 kernel property and exact-penalty constructor, -- reusing the upstream problem and penalty owners directly. namespace EuclideanSpace abbrev linftyNorm (c : EuclideanSpace ℝ (Fin m)) : ℝ := ‖c.ofLp‖∞

Supporting modules

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

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source