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.
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.
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 3Exercise 10.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
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.
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.
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 σ xExercise 10.9
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
Chapter10 Exercise 10.10: direct recall of both theorem owners for Lemma 10.6.2.
#check nonsmoothExactPenaltyObjectiveValueMono10.1 — Penalty Function
Lemma 10.1.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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ᵀ)).PosDefDefinition 10.1.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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-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.
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.
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.
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 kTheorem 10.3.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.terminatesFinitelyAlgorithm 10.3.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.iterateDefinition 10.3.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
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.
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.
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 xStarRemark 10.4.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
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 xBarTheorem 10.6.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
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 σ xStarDefinition 10.6.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
-
ChosenPseudoInverse.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
StandardPenaltyProblemBridge.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_10_4_2/RunSemantics.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.