Chapter 08 — Theory of Constrained Optimization

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

Exercise 8.1

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

Source header · Attribution source

Chapter08 Exercise 8.1: assume problem.objective is convex on Set.univ, each equality constraint of problem is linear, and each inequality constraint is concave. If xStar is a local minimizer of problem.objective on problem.feasibleSet, then xStar is a global minimizer of the constrained problem, formalized as IsMinOn problem.objective problem.feasibleSet xStar.

variable {n m : ℕ} {E I : Set (Fin m)} local notation "Point" => Fin n → ℝ -- Semantic recall: `IsMinOn.of_isLocalMinOn_of_convexOn` is the canonical local-to-global convex -- minimizer theorem, and Chapter 8 already owns the constrained-problem API and the affine -- feasible-set convexity bridge. theorem isMinOn_of_isLocalMinOn_of_convexObjective_of_eq_linear_of_ineq_concave (problem : ConstrainedOptimizationProblem n m E I) (xStar : Point) (h_objective : ConvexOn ℝ Set.univ problem.objective) (h_eq : ∀ i ∈ E, ∃ c : Point →ₗ[ℝ] ℝ, problem.constraint i = c) (h_ineq : ∀ i ∈ I, ConcaveOn ℝ Set.univ (problem.constraint i)) (hxStar : xStar ∈ problem) (h_localMin : IsLocalMinOn problem.objective problem.feasibleSet xStar) : IsMinOn problem.objective problem.feasibleSet xStar

Exercise 8.2

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

Source header · Attribution source

Chapter08 Exercise 8.2: if x satisfies all inequality constraints, the active inequality set I(x) is the intersection of the ε-active inequality sets I_ε(x) over all ε > 0, which formalizes the right-hand limit I_ε(x) → I(x) as ε → 0+.

variable {n m : ℕ} {E I : Set (Fin m)} local notation "Point" => Fin n → ℝ namespace ConstrainedOptimizationProblem -- Domain sampling: -- * core/canonical owner: `Chapter01.ConstrainedOptimizationProblem` -- * Chapter 8 derived active-set owner: `activeIneqIndexSet` from `Definition_8_1_1` -- * this file is source-facing: it adds the ε-active inequality index set as a derived view on -- the existing owner rather than rebuilding constrained-problem data locally theorem iInter_epsilonActiveIneqIndexSet_pos_eq_activeIneqIndexSet (problem : _root_.ConstrainedOptimizationProblem n m E I) {x : Point} (hineq : ∀ i ∈ problem.ineqIndices, 0 ≤ problem.constraint i x) : (⋂ ε : {ε : ℝ // 0 < ε}, problem.epsilonActiveIneqIndexSet x ε.1) = problem.activeIneqIndexSet x

Exercise 8.3

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

Source header · Attribution source

Chapter08 Exercise 8.3: if every active constraint cᵢ of problem at the feasible point xStar is linear, then the Chapter 8 constraint qualification (8.2.19) holds at xStar. This is the source-facing bridge to the canonical owner problem.LfcqAt xStar.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
namespace ConstrainedOptimizationProblem
theorem constraintQualificationAt_of_activeConstraints_linear
    (problem : ConstrainedOptimizationProblem n m E I) (xStar : Point)
    (hxStar : xStar ∈ problem)
    (h_linear :
      ∀ i ∈ problem.activeConstraintIndexSet xStar,
        ∃ ci : Point →ₗ[ℝ] ℝ, problem.constraint i = ci) :
    problem.ConstraintQualificationAt xStar

Exercise 8.4

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

Source header · Attribution source

Chapter08 Exercise 8.4 (1): formula (8.3.16) is already the Chapter 8 theorem ConstrainedOptimizationProblem.sequentialNullConstraintDirections_subset_posTangentConeAt from Definition_8_3_2.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
namespace ConstrainedOptimizationProblem
#check ConstrainedOptimizationProblem.sequentialNullConstraintDirections_subset_posTangentConeAt

Exercise 8.5

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

Source header · Attribution source

Chapter08 Exercise 8.5: formula (8.3.18) is already the canonical Chapter 8 theorem ConstrainedOptimizationProblem.sequentialNullDirections_subset_linearizedNullDirections from Definition_8_3_2. This is the source-faithful statement because the upstream owner keeps the needed constraint-gradient hypothesis explicit instead of relying on totalized gradient outside its differentiability domain.

#check ConstrainedOptimizationProblem.sequentialNullDirections_subset_linearizedNullDirections

Exercise 8.6

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

Source header · Attribution source

Chapter08 Exercise 8.6: for the problem with objective exercise86Objective c and Euclidean ball constraint exercise86Constraint, the minimization-consistent boundary point exercise86Candidate c = -c / ‖c‖₂ is stated on the chapter's canonical second-order sufficient-condition surface using an existential multiplier.

open scoped Gradient
variable {n : ℕ}
local notation "Point" => Fin n → ℝ
local notation "ConstraintIndex" => Fin 1
local notation "Multiplier" => ConstraintIndex → ℝ
local notation "EPoint" => EuclideanSpace ℝ (Fin n)

-- Domain sampling:
-- * primary domain: second-order sufficiency for a concrete Chapter 8 constrained problem
-- * inspected owner declarations in this domain:
--   `ConstrainedOptimizationProblem.IsKKTPoint` from `Theorem_8_2_7`
--   `ConstrainedOptimizationProblem.linearizedNullConstraintDirections` from `Definition_8_3_2`
--   `ConstrainedOptimizationProblem.lagrangianHessianQuadratic` from `Theorem_8_3_3`
--   `ConstrainedOptimizationProblem
--      .isStrictLocalMinOn_of_positive_lagrangianHessian_on_linearizedNullConstraintDirections`
--   from `Theorem_8_3_4`
-- * semantic recall via `lean_leansearch`: no more specific mathlib/project owner surfaced than
--   the chapter KKT/SOSC API already used here
-- * owner abstraction chosen here: the chapter owner `ConstrainedOptimizationProblem`
-- * primitive data kept here: the exercise objective, the single inequality-constraint family,
--   the resulting constrained problem, and its explicit source-facing candidate data
-- * derived API deleted from the local file: the bespoke feasible-set and SOSC wrapper
--   definitions, now replaced by the canonical KKT/null-direction/Hessian owners
-- * transport note: the source uses the Euclidean norm on `ℝ^n`; on the chapter owner
--   `Point = Fin n → ℝ`, that norm is expressed via `WithLp.toLp 2`
theorem exercise86_candidate_satisfiesSecondOrderSufficientCondition
    (c : Point) (hc : c ≠ 0) :
    let problem := exercise86Problem c
    let xStar : Point := exercise86Candidate c
    ∃ lamStar : Multiplier,
      problem.IsKKTPoint xStar lamStar ∧
        ∀ d ∈ problem.linearizedNullConstraintDirections xStar lamStar,
          0 < problem.lagrangianHessianQuadratic xStar lamStar d

Exercise 8.7

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

Source header · Attribution source

Chapter08 Exercise 8.7 (1): after rewriting the disk constraint as 2 - x^2 - y^2 ≥ 0, the canonical KKT owner for the minimization problem with objective -(chapter08Exercise87Objective) is equivalent to the explicit scalar KKT system λ ≥ 0, μ ≥ 0, primal feasibility, stationarity 2 * (x + 1) - 2 * λ * x = 0, 2 * (y + 1) - 2 * λ * y - μ = 0, and complementary slackness for 2 - x^2 - y^2 and 1 - y.

local notation "Point" => Fin 2 → ℝ
local notation "EPoint" => EuclideanSpace ℝ (Fin 2)
theorem chapter08Exercise87_isKKTPoint_iff (x y lam mu : ℝ) :
    chapter08Exercise87Problem.IsKKTPoint
      ![x, y]
      ![lam, mu] ↔
      x ^ (2 : ℕ) + y ^ (2 : ℕ) ≤ 2 ∧
        1 - y ≥ 0 ∧
        lam ≥ 0 ∧
        mu ≥ 0 ∧
        (2 * (x + 1) - 2 * lam * x = 0) ∧
        (2 * (y + 1) - 2 * lam * y - mu = 0) ∧
        lam * (2 - x ^ (2 : ℕ) - y ^ (2 : ℕ)) = 0 ∧
        mu * (1 - y) = 0

Exercise 8.8

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

Source header · Attribution source

Chapter08 Exercise 8.8 (1): for the unconstrained quartic example x ↦ x₀^4 at the origin, the second-order necessary condition holds on the Chapter 8 owner G(xStar, lamStar), written as problem.linearizedNullConstraintDirections xStar lamStar.

local notation "Point" => Fin 1 → ℝ

-- Domain sampling:
-- * primary domain: second-order constrained optimization for a concrete no-constraint example
-- * inspected owner chain:
--   `ConstrainedOptimizationProblem` from `Chapter01.Definition_1_1_extra_1`
--   `ConstrainedOptimizationProblem.activeIneqIndexSet` from `Definition_8_1_1`
--   `ConstrainedOptimizationProblem.linearizedNullConstraintDirections` from `Definition_8_3_2`
--   `ConstrainedOptimizationProblem.lagrangianHessianQuadratic` from `Theorem_8_3_3`
-- * owner abstraction used here: the existing Chapter 8 constrained-problem/KKT/null-direction
--   surface, specialized to the unconstrained quartic example
-- * primitive data: the quartic objective and the empty constraint family
-- * derived API reused directly: KKT points, `G(xStar, lamStar)`, and the Lagrangian Hessian
--   quadratic form
theorem quarticNoConstraintExample_secondOrderNecessaryCondition :
    ∀ d ∈ quarticNoConstraintProblem.linearizedNullConstraintDirections
        quarticNoConstraintPoint quarticNoConstraintMultipliers,
      0 ≤ quarticNoConstraintProblem.lagrangianHessianQuadratic
        quarticNoConstraintPoint quarticNoConstraintMultipliers d

Exercise 8.9

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

Source header · Attribution source

Chapter08 Exercise 8.9: the point exercise89NearestPoint = (1 / 3, 2 / 3, 0) minimizes the squared distance to the origin on the ellipse defined by x 0 + x 1 = 1 and x 0^2 + 2 * x 1^2 + x 2^2 = 1.

local notation "Point" => EuclideanSpace ℝ (Fin 3) -- Semantic recall: `IsMinOn` is the canonical minimizer predicate for a concrete feasible set. -- This exercise keeps the explicit feasible set, squared-distance objective, and nearest point on -- the repo-standard carrier `Point = EuclideanSpace ℝ (Fin 3)`. theorem isMinOn_exercise89SquaredDistanceToOrigin : IsMinOn exercise89SquaredDistanceToOrigin exercise89FeasibleSet exercise89NearestPoint

Exercise 8.10

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

Source header · Attribution source

Chapter08 Exercise 8.10: the dual problem is the one-variable maximization problem in the multiplier λ; for σ = 1, the local dual solution agrees with the primal multiplier λ = 1, while for σ = -1 there are local dual solutions different from the primal multiplier.

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

-- Domain sampling:
-- * primary domain: constrained optimization / local duality for a single inequality problem
--   in `ℝ²`
-- * inspected owner declarations:
--   `ConstrainedOptimizationProblem.lagrangian` from `Definition_8_1_1`
--   the chapter notation bridge `𝓛[problem](x, lam)` from `Notation_8_2_extra_2`
--   `ConstrainedOptimizationProblem.euclideanLagrangian` and
--   `ConstrainedOptimizationProblem.IsKKTPoint` from `Theorem_8_2_7`
--   `ConstrainedOptimizationProblem.dualObjective` from `Theorem_8_4_1`
--   `IsLocalMinOn` / `IsLocalMaxOn` from mathlib `Topology.Order.LocalExtr`
-- * owner abstraction chosen here: the Chapter 8 constrained-problem owner
--   `exercise810Problem σ : ConstrainedOptimizationProblem 2 1 ∅ Set.univ`
-- * primitive data: the source objective and the single inequality constraint `x 0 ≥ 0`
-- * derived API kept here: the source scalar-`λ` bridge to the canonical KKT and dual-owner
--   surfaces via the canonical singleton vector literal `![λ]`
theorem exercise810_duality_behavior :
    (IsLocalMinOn (exercise810Problem 1) (exercise810Problem 1).feasibleSet 0 ∧
      (exercise810Problem 1).IsKKTPoint 0 ![1] ∧
      IsLocalMaxOn
        (fun lam ↦ (exercise810Problem 1).dualObjective ![lam])
        (Set.Ici (0 : ℝ)) 1 ∧
      ∀ {lam : ℝ},
        lam ∈ Set.Ici (0 : ℝ) →
          IsLocalMaxOn
            (fun μ ↦ (exercise810Problem 1).dualObjective ![μ])
            (Set.Ici (0 : ℝ)) lam →
          lam = 1) ∧
    (IsLocalMinOn (exercise810Problem (-1)) (exercise810Problem (-1)).feasibleSet 0 ∧
      (exercise810Problem (-1)).IsKKTPoint 0 ![1] ∧
      ∃ lam ∈ Set.Ici (0 : ℝ),
        lam ≠ 1 ∧
          IsLocalMaxOn
            (fun μ ↦ (exercise810Problem (-1)).dualObjective ![μ])
            (Set.Ici (0 : ℝ)) lam)

8.1 — Constrained Optimization Problems

Definition 8.1.1

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

Source header · Attribution source

Chapter08 Definition 8.1.1 (1). Membership in the feasible set is equivalent to satisfying every equality constraint and every inequality constraint.

variable {n m : ℕ} {E I : Set (Fin m)} local notation "Point" => Fin n → ℝ open scoped BigOperators namespace ConstrainedOptimizationProblem theorem mem_feasibleSet_iff (problem : _root_.ConstrainedOptimizationProblem n m E I) (x : Point) : x ∈ problem.feasibleSet ↔ (∀ i ∈ problem.eqIndices, problem.constraint i x = 0) ∧ ∀ i ∈ problem.ineqIndices, 0 ≤ problem.constraint i x

Definition 8.1.2

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

Source header · Attribution source

Chapter08 Definition 8.1.2 (1): xStar is a global minimizer of a constrained optimization problem when it is feasible and minimizes the objective on the feasible set.

variable {n m : ℕ} {E I : Set (Fin m)} local notation "Point" => Fin n → ℝ -- Domain sampling: -- * project owner: `ConstrainedOptimizationProblem` in `Definition_8_1_1` -- * mathlib owner: `IsMinOn` and `isMinOn_iff` -- * project owner for strict minima on a set: `IsStrictMinOn` and `isStrictMinOn_iff` in -- `Chapter01.Definition_1_4_2` -- Layer triage: -- * source-facing: `ConstrainedOptimizationProblem` -- * core/canonical: `IsMinOn` for non-strict minima and `IsStrictMinOn` for strict minima on -- the feasible set -- * bridge/view: `problem.IsGlobalMinimizer xStar` class ConstrainedOptimizationProblem.IsGlobalMinimizer (problem : _root_.ConstrainedOptimizationProblem n m E I) (xStar : Point) : Prop where feasible : xStar ∈ problem isMinOn : IsMinOn problem.objective problem.feasibleSet xStar

Definition 8.1.3

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

Source header · Attribution source

Chapter08 Definition 8.1.3 (1): a constrained local minimizer on s is a feasible point a that satisfies the canonical local-minimum owner IsLocalMinOn f s a.

open scoped Topology variable {X : Type*} [TopologicalSpace X] variable {α : Type*} [Preorder α] -- Domain sampling: -- * primary domain: constrained local extrema on subset neighborhoods in topological spaces -- * source-facing owner: `IsConstrainedLocalMinOn` -- * core/canonical owner: mathlib's `IsLocalMinOn` -- * related declarations inspected: -- `IsLocalMinOn`, `IsLocalMinOn.isLocalMin`, `nhdsWithin_insert`, -- `ConstrainedOptimizationProblem.IsGlobalMinimizer`, -- `IsStrictLocalMin` from `Chapter01/Definition_1_4_1` -- * layer triage: source-facing owner adds feasibility to the topological neighborhood-filter -- owner `IsLocalMinOn`, -- with metric closed-ball formulations kept as bridge API below -- * primitive data: feasibility together with the canonical local-minimum owner, and for the -- strict notion eventual strict inequality on `𝓝[s \ {a}] a` -- * derived API kept here: bridges to the canonical local-minimum owner and metric-ball -- formulations def IsConstrainedLocalMinOn (f : X → α) (s : Set X) (a : X) : Prop := a ∈ s ∧ IsLocalMinOn f s a

Definition 8.1.4

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

Source header · Attribution source

Chapter08 Definition 8.1.4: xStar is an isolated local minimizer of f on X when xStar is a constrained local minimizer of f on X, and there exists δ > 0 such that every local minimizer of f on X lying in X ∩ Metric.ball xStar δ is equal to xStar.

variable {X : Type*} [PseudoMetricSpace X] variable {α : Type*} [Preorder α] -- Domain sampling: -- * primary domain: constrained local minima in metric spaces -- * source-facing owner reused from `Definition_8_1_3`: `IsConstrainedLocalMinOn` -- * core/canonical owner: `IsLocalMinOn` -- * inspected related declarations: -- `IsLocalMinOn` / `IsLocalMinOn.on_subset` in `Mathlib.Topology.Order.LocalExtr` -- `IsStrictLocalMin` in `Chapter01/Definition_1_4_1` -- `isConstrainedLocalMinOn_iff_exists_forall_mem_closedBall` in `Chapter08/Definition_8_1_3` -- * layer triage: source-facing owner built from the Chapter 8 constrained-local-minimum owner -- and the canonical core owner `IsLocalMinOn` -- * primitive data here: constrained local minimality at `xStar` and the isolation -- radius/uniqueness clause -- * derived API here: accessors recovering feasibility and the canonical local-minimum owner def IsIsolatedLocalMinOn (f : X → α) (s : Set X) (xStar : X) : Prop := IsConstrainedLocalMinOn f s xStar ∧ ∃ δ > 0, ∀ x : X, x ∈ s ∩ Metric.ball xStar δ → IsLocalMinOn f s x → x = xStar

Definition 8.1.5

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

Source header · Attribution source

Chapter08 Definition 8.1.5: the active-set owner surface is already provided upstream by ConstrainedOptimizationProblem.activeIneqIndexSet and ConstrainedOptimizationProblem.activeConstraintIndexSet in Definition_8_1_1.

#check ConstrainedOptimizationProblem.activeIneqIndexSet

Definition 8.1.extra.1

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

Source header · Attribution source

Chapter08 Definition 8.1-extra-1 (1). A standard constrained optimization problem on ℝ^n consists of an objective f, a finite family of constraint functions c_i, a number eqCount ≤ m splitting the first eqCount constraints into equalities and the remaining constraints into inequalities. The source nonlinearity clause is treated below as a derived classification predicate rather than as primitive owner data, so linear and quadratic subclasses share the same ambient owner. Smoothness assumptions belong to later theorem hypotheses rather than to this source-facing owner.

variable {n m : ℕ} structure StandardConstrainedOptimizationProblem (n m : ℕ) where eqCount : ℕ eqCount_le : eqCount ≤ m objective : (Fin n → ℝ) → ℝ constraint : Fin m → (Fin n → ℝ) → ℝ

8.2 — First-Order Optimality Conditions

Definition 8.2.1

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

Source header · Attribution source

Chapter08 Definition 8.2.1 (1): a vector d is a feasible direction of X at xStar when d ≠ 0 and there exists δ > 0 such that xStar + t • d ∈ X for every t ∈ Set.Icc (0 : ℝ) δ. The source-side condition xStar ∈ X is then automatic by taking t = 0.

variable {E : Type*} [AddCommGroup E] [Module ℝ E] -- Semantic recall hits verified for this item: mathlib's canonical infinitesimal-set owner is -- `tangentConeAt`, and `mem_tangentConeAt_of_segment_subset` shows the expected bridge from small -- feasible segments. This source item is kept as the faithful ray-based predicate and its -- associated set of directions. class IsFeasibleDirectionAt (X : Set E) (xStar d : E) : Prop where ne : d ≠ 0 small_segment_mem : ∃ δ > 0, ∀ t ∈ Set.Icc (0 : ℝ) δ, xStar + t • d ∈ X

Definition 8.2.2

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

Source header · Attribution source

Chapter08 Definition 8.2.2: d is a linearized feasible direction of the feasible set of problem at xStar when xStar ∈ problem, every active constraint of problem is differentiable at xStar, every equality-constraint pairing dᵀ ∇ c_i(xStar) vanishes for i ∈ problem.eqIndices, and every active inequality-constraint pairing is nonnegative for i ∈ problem.activeIneqIndexSet xStar.

variable {n m : ℕ} {E I : Set (Fin m)} local notation "Point" => Fin n → ℝ local notation "EPoint" => EuclideanSpace ℝ (Fin n) namespace ConstrainedOptimizationProblem -- Domain sampling: -- * primary domain: first-order linearized feasibility for constrained optimization problems -- * inspected owners: -- `ConstrainedOptimizationProblem.activeConstraintIndexSet` from `Definition_8_1_1` -- mathlib's `fderiv` -- `ConstrainedOptimizationProblem.LicqAt` from `Definition_8_2_10` -- `ConstrainedOptimizationProblem.linearizedNullConstraintDirections` -- from `Definition_8_3_2` -- * owner abstraction chosen here: -- `source-facing`: `IsLinearizedFeasibleDirectionAt` -- `core/canonical`: `fderiv ℝ (problem.constraint i) xStar d` on `Point` -- `bridge/view`: `euclideanObjective` and `euclideanConstraint` for downstream gradient files -- * primitive data vs derived API: -- the primitive first-order pairing is the Fréchet derivative of the original constraint on -- `Point`; the Euclidean transport is derived bridge data and does not own the public pairing -- API -- This file keeps the source-facing feasible-direction predicate while reusing the chapter's -- active-set owner and mathlib's derivative owner directly. @[mk_iff isLinearizedFeasibleDirectionAt_iff] class IsLinearizedFeasibleDirectionAt (problem : ConstrainedOptimizationProblem n m E I) (xStar d : Point) : Prop where feasiblePoint : xStar ∈ problem hasActiveConstraintGradientsAt : problem.HasActiveConstraintGradientsAt xStar eq_pairing_eq_zero : ∀ i ∈ problem.eqIndices, problem.linearizedConstraintPairing xStar d i = 0 activeIneq_pairing_nonneg : ∀ i ∈ problem.activeIneqIndexSet xStar, 0 ≤ problem.linearizedConstraintPairing xStar d i

Definition 8.2.3

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

Source header · Attribution source

Chapter08 Definition 8.2.3: the source set SFD(xStar, X) is realized by the canonical positive tangent cone posTangentConeAt X xStar.

open Filter open scoped Pointwise -- Domain sampling: -- * primary domain: one-sided tangent directions in real normed spaces -- * inspected mathlib owners: -- `posTangentConeAt` -- `tangentConeAt NNReal` -- `mem_tangentConeAt_iff_exists_seq` -- * source/core/bridge triage: -- `source-facing`: the textbook set `SFD(xStar, X)`, represented here only through the -- sequence-membership bridge below -- `core/canonical`: `posTangentConeAt X xStar` -- `bridge/view`: `mem_posTangentConeAt_iff_exists_seq_pos` variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] #check (posTangentConeAt : Set E → E → Set E)

Lemma 8.2.4

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

Source header · Attribution source

Chapter08 Lemma 8.2.4 (1): exact recall of the existing source-facing theorem feasibleDirections_subset_tangentConeAt.

#check feasibleDirections_subset_tangentConeAt

Theorem 8.2.5

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

Source header · Attribution source

Chapter08 Theorem 8.2.5: if xStar is a feasible local minimizer of problem and the objective is differentiable at xStar, then every sequential feasible direction d ∈ SFD(xStar, problem.feasibleSet) has nonnegative first-order objective pairing inner ℝ d (gradient problem.objective xStar) ≥ 0.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
local notation "EPoint" => EuclideanSpace ℝ (Fin n)
local notation "inner" => pointInner
local notation "gradient" => pointGradient
local notation "descentDirections" => pointDescentDirections
theorem geometryOptimalityCondition_nonneg_pairing
    (problem : ConstrainedOptimizationProblem n m E I) (xStar : Point)
    (h_localMin : IsLocalMinOn problem.objective problem.feasibleSet xStar)
    (h_objective : DifferentiableAt ℝ problem.objective xStar) :
    ∀ d ∈ sequentialFeasibleDirections xStar problem.feasibleSet,
      0 ≤ inner ℝ d (gradient problem.objective xStar)

Lemma 8.2.6

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

Source header · Attribution source

Chapter08 Lemma 8.2.6: assuming E and I are disjoint, the source descent system (8.2.16) has no solution exactly when there exists a multiplier family lam, nonnegative on I, such that gradF = (∑ i : E, lam i • gradC i) + (∑ i : I, lam i • gradC i). Here hf identifies gradF as the gradient of f at xStar, while the constraint gradients stay as primitive source data.

open scoped BigOperators
variable {X : Type*} [NormedAddCommGroup X] [InnerProductSpace ℝ X] [CompleteSpace X]
variable {ι : Type*} [Finite ι]
theorem descentDirections_inter_constraintGradientSystem_eq_empty_iff_exists_multiplier
    (E I : Set ι) (h_disj : Disjoint E I) (f : X → ℝ) (xStar gradF : X) (gradC : ι → X)
    (hf : HasGradientAt f gradF xStar) :
    descentDirections f xStar ∩
        {d | (∀ i ∈ E, inner ℝ d (gradC i) = 0) ∧
          ∀ i ∈ I, 0 ≤ inner ℝ d (gradC i)} = (∅ : Set X) ↔
      ∃ lam : ι → ℝ,
        (∀ i ∈ I, 0 ≤ lam i) ∧
          gradF = (∑ i : E, lam i • gradC i) + (∑ i : I, lam i • gradC i)

Theorem 8.2.7

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

Source header · Attribution source

Chapter08 Theorem 8.2.7 uses the source constraint qualification (8.2.19) at xStar, namely the equality SFD(xStar, problem.feasibleSet) = LFD(xStar, problem.feasibleSet) between the Chapter 8 sequential and linearized feasible direction sets.

open scoped BigOperators Gradient
variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
local notation "EPoint" => EuclideanSpace ℝ (Fin n)
namespace ConstrainedOptimizationProblem
def ConstraintQualificationAt
    (problem : _root_.ConstrainedOptimizationProblem n m E I) (xStar : Point) : Prop :=
  posTangentConeAt problem.feasibleSet xStar =
    problem.linearizedFeasibleDirectionSet xStar

Definition 8.2.8

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

Source header · Attribution source

Chapter08 Definition 8.2.8: linear function constraint qualification (LFCQ) holds at xStar when every active constraint of problem at xStar is a linear function.

variable {n m : ℕ} {E I : Set (Fin m)} local notation "Point" => Fin n → ℝ namespace ConstrainedOptimizationProblem class LfcqAt (problem : ConstrainedOptimizationProblem n m E I) (xStar : Point) : Prop where /-- Every active constraint of `problem` at `xStar` is represented by a linear map. -/ constraint_eq_linearMap (i : Fin m) (hi : i ∈ problem.activeConstraintIndexSet xStar) : ∃ ci : Point →ₗ[ℝ] ℝ, problem.constraint i = ci

Corollary 8.2.9

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

Source header · Attribution source

Chapter08 Corollary 8.2.9: under the standing differentiability setup of the Chapter 8 KKT theorem, if xStar is a feasible local minimizer of problem and the linear function constraint qualification problem.LfcqAt xStar holds, then xStar admits a KKT multiplier vector for problem.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
theorem exists_isKKTPoint_of_isLocalMinOn_of_lfcqAt
    (problem : ConstrainedOptimizationProblem n m E I) (xStar : Point)
    (hxStar : xStar ∈ problem)
    (h_localMin : IsLocalMinOn problem.objective problem.feasibleSet xStar)
    (h_objective : DifferentiableAt ℝ problem.objective xStar)
    (h_constraints : problem.HasConstraintGradientsAt xStar)
    (h_lfcq : problem.LfcqAt xStar) :
    ∃ lamStar : Fin m → ℝ, problem.IsKKTPoint xStar lamStar

Definition 8.2.10

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

Source header · Attribution source

Chapter08 Definition 8.2.10: LICQ holds at xStar when every active constraint of problem is differentiable at xStar and the active-constraint gradients are linearly independent. The gradients are evaluated on the Euclidean transport already used by the chapter's gradient API.

variable {n m : ℕ} {E I : Set (Fin m)} -- Domain sampling: -- * primary domain: LICQ for constrained optimization problems -- * inspected owners: -- `ConstrainedOptimizationProblem.activeConstraintIndexSet` from `Definition_8_1_1` -- `ConstrainedOptimizationProblem.HasActiveConstraintGradientsAt` from `Definition_8_2_2` -- mathlib's `LinearIndepOn` -- `StandardPenaltyProblem.LicqAt` from Chapter 10 -- * owner abstraction chosen here: -- `source-facing`: `problem.LicqAt xStar` -- `core/canonical`: `LinearIndepOn` -- `bridge/view`: `problem.euclideanConstraint` and `WithLp.toLp 2 xStar` for mathlib's -- Euclidean gradient API -- * primitive data vs derived API: -- the primitive fields are active-constraint differentiability and active-gradient linear -- independence; pointwise differentiability of a single active constraint is derived namespace ConstrainedOptimizationProblem local notation "Point" => Fin n → ℝ @[mk_iff licqAt_iff] class LicqAt (problem : ConstrainedOptimizationProblem n m E I) (xStar : Point) : Prop where /-- Every active constraint of `problem` is differentiable at `xStar`. -/ hasActiveConstraintGradientsAt : problem.HasActiveConstraintGradientsAt xStar /-- The active-constraint gradients are linearly independent. -/ linearIndepOn : LinearIndepOn ℝ (fun i : Fin m ↦ gradient (problem.euclideanConstraint i) (WithLp.toLp 2 xStar)) (problem.activeConstraintIndexSet xStar)

Theorem 8.2.11

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

Source header · Attribution source

Chapter08 Theorem 8.2.11: let xStar be a feasible point. If each active constraint problem.constraint i is differentiable at xStar and LICQ holds at xStar. Then the Chapter 8 constraint qualification (8.2.19) holds; equivalently, the linearized feasible direction set agrees with posTangentConeAt problem.feasibleSet xStar.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
namespace ConstrainedOptimizationProblem
theorem constraintQualificationAt_of_licqAt
    (problem : ConstrainedOptimizationProblem n m E I) (xStar : Point)
    (hxStar : xStar ∈ problem)
    (h_licq : problem.LicqAt xStar) :
    problem.ConstraintQualificationAt xStar

Theorem 8.2.12

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

Source header · Attribution source

Chapter08 Theorem 8.2.12: under the standing differentiability setup of Chapter08 Theorem 8.2.7, if xStar is a feasible local minimizer of problem and LICQ holds at xStar, then there exists a multiplier vector lamStar such that problem.IsKKTPoint xStar lamStar.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ

-- Domain-style sampling:
-- * primary domain: first-order KKT existence for constrained optimization under LICQ
-- * sampled owner declarations:
--   `ConstrainedOptimizationProblem.LicqAt`
--   `ConstrainedOptimizationProblem.constraintQualificationAt_of_licqAt`
--   `exists_isKKTPoint_of_isLocalMinOn_of_constraintQualificationAt`
-- * source/core/bridge triage:
--   `source-facing`: the LICQ-based multiplier-existence theorem stated here
--   `core/canonical`: `problem.IsKKTPoint xStar lamStar`
--   `bridge/view`: `problem.ConstraintQualificationAt xStar`
-- * primitive data vs derived API:
--   the primitive source hypothesis is `problem.LicqAt xStar`; the constraint qualification is
--   derived bridge data already owned by Theorem 8.2.11, so this file should reuse that bridge
--   instead of re-owning a parallel proof surface
theorem exists_isKKTPoint_of_isLocalMinOn_of_licqAt
    (problem : ConstrainedOptimizationProblem n m E I) (xStar : Point)
    (hxStar : xStar ∈ problem)
    (h_localMin : IsLocalMinOn problem.objective problem.feasibleSet xStar)
    (h_objective : DifferentiableAt ℝ problem.objective xStar)
    (h_constraints : problem.HasConstraintGradientsAt xStar)
    (h_licq : problem.LicqAt xStar) :
    ∃ lamStar : Fin m → ℝ, problem.IsKKTPoint xStar lamStar

Theorem 8.2.13

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

Source header · Attribution source

Chapter08 Theorem 8.2.13: under the standing differentiability setup of the Chapter 8 KKT theorem, if xStar is a feasible local minimizer of problem and the regularity assumption problem.regularityAssumptionAt xStar from (8.2.42) holds, then there exists a multiplier vector lamStar such that (xStar, lamStar) satisfies the KKT conditions for problem.

open scoped BigOperators
variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
local notation "EPoint" => EuclideanSpace ℝ (Fin n)

-- Domain-style sampling:
-- * source-facing theorem: KKT-multiplier existence under the Chapter 8 regularity condition
--   `(8.2.42)`, which is weaker than the full constraint qualification from Theorem 8.2.7
-- * reused Chapter 8 owners:
--   `problem.regularityAssumptionAt` from `Assumption_8_2_extra_4`
--   `problem.HasConstraintGradientsAt` from `Definition_8_2_2`
--   `problem.IsKKTPoint` from `Theorem_8_2_7`
-- * companion API added here:
--   `problem.linearizedDescentDirections_eq_empty_of_regularityAssumptionAt`
--   isolates the source-semantic consequence of the weaker regularity assumption before the KKT
--   packaging step
-- * owner choice: this file is theorem-only, so it should reuse the chapter owners rather than
--   rebuilding a second constrained-problem/KKT API
theorem exists_isKKTPoint_of_isLocalMinOn_of_regularityAssumptionAt
    (problem : ConstrainedOptimizationProblem n m E I) (xStar : Point)
    (hxStar : xStar ∈ problem)
    (h_localMin : IsLocalMinOn problem.objective problem.feasibleSet xStar)
    (h_objective : DifferentiableAt ℝ problem.objective xStar)
    (h_constraints : problem.HasConstraintGradientsAt xStar)
    (h_regularity : problem.regularityAssumptionAt xStar) :
    ∃ lamStar : Fin m → ℝ, problem.IsKKTPoint xStar lamStar

Theorem 8.2.14

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

Source header · Attribution source

Chapter08 Theorem 8.2.14: let xStar be a feasible point of a constrained optimization problem. If the objective is differentiable at xStar, and every nonzero sequential feasible direction d ∈ posTangentConeAt problem.feasibleSet xStar has strictly positive directional derivative fderiv ℝ problem.objective xStar d, then xStar is a strict local minimizer of the constrained problem on X = problem.feasibleSet.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
open Filter
open scoped Pointwise Topology
theorem isStrictLocalMinOn_of_positive_pairing_on_sequentialFeasibleDirections
    (problem : ConstrainedOptimizationProblem n m E I) (xStar : Point)
    (hxStar : xStar ∈ problem)
    (h_objective : DifferentiableAt ℝ problem.objective xStar)
    (h_positive :
      ∀ d ∈ posTangentConeAt problem.feasibleSet xStar,
        d ≠ 0 → 0 < fderiv ℝ problem.objective xStar d) :
    IsStrictLocalMinOn problem.objective problem.feasibleSet xStar

Corollary 8.2.15

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

Source header · Attribution source

Chapter08 Corollary 8.2.15: let xStar ∈ X be a feasible point of a constrained optimization problem. If the objective and every active constraint function are differentiable at xStar, and every nonzero linearized feasible direction d ∈ LFD(xStar, X) has strictly positive directional derivative fderiv ℝ problem.objective xStar d, then xStar is a strict local minimizer of the constrained problem on X = problem.feasibleSet.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ

-- Domain sampling pass:
-- * primary domain: constrained local minima via first-order feasible-direction conditions
-- * inspected project owners/bridges:
--   `ConstrainedOptimizationProblem.HasActiveConstraintGradientsAt` from `Definition_8_2_2`
--   `ConstrainedOptimizationProblem.linearizedFeasibleDirectionSet` from `Definition_8_2_2`
--   `sequentialFeasibleDirections xStar problem.feasibleSet = posTangentConeAt _ _` from
--   `Definition_8_2_3`
--   `sequentialFeasibleDirections_subset_linearizedFeasibleDirectionSet` from `Lemma_8_2_4`
--   `isStrictLocalMinOn_of_positive_pairing_on_sequentialFeasibleDirections` from
--   `Theorem_8_2_14`
-- * owner abstraction chosen here: the existing Chapter 8 constrained-problem owner together
--   with the source-facing linearized-feasible-direction set; this corollary is only the bridge
--   from the sequential theorem to the stronger linearized hypothesis
-- * companion API added here: the canonical `IsLocalMinOn` consequence, matching the Chapter 8
--   theorem/corollary pattern for strict local minima
theorem isStrictLocalMinOn_of_positive_pairing_on_linearizedFeasibleDirectionSet
    (problem : ConstrainedOptimizationProblem n m E I) (xStar : Point)
    (hxStar : xStar ∈ problem)
    (h_objective : DifferentiableAt ℝ problem.objective xStar)
    (h_constraints : problem.HasActiveConstraintGradientsAt xStar)
    (h_positive :
      ∀ d ∈ problem.linearizedFeasibleDirectionSet xStar,
        d ≠ 0 → 0 < fderiv ℝ problem.objective xStar d) :
    IsStrictLocalMinOn problem.objective problem.feasibleSet xStar

Theorem 8.2.16

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

Source header · Attribution source

Chapter08 Theorem 8.2.16: if xStar is a feasible local minimizer of the constrained problem problem, and the objective and every constraint function are differentiable at xStar, then there exist a scalar multiplier lambdaZero and a vector multiplier lambda such that problem.IsFritzJohnPoint xStar lambdaZero lambda.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
local notation "EPoint" => EuclideanSpace ℝ (Fin n)
open scoped BigOperators Gradient
theorem exists_fritzJohnMultipliers_of_isLocalMinOn
    (problem : ConstrainedOptimizationProblem n m E I) (xStar : Point)
    (hxStar : xStar ∈ problem)
    (h_localMin : IsLocalMinOn problem.objective problem.feasibleSet xStar)
    (h_objective : DifferentiableAt ℝ problem.objective xStar)
    (h_constraints : problem.HasConstraintGradientsAt xStar) :
    ∃ lambdaZero : ℝ, ∃ lambda : Fin m → ℝ,
      problem.IsFritzJohnPoint xStar lambdaZero lambda

Theorem 8.2.17

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

Source header · Attribution source

Chapter08 Theorem 8.2.17 (1): each local minimizer of a convex programming problem is a global minimizer on the feasible set. This item is an exact Point = ℝ^n specialization of the canonical mathlib owner IsMinOn.of_isLocalMinOn_of_convexOn, so it stays at the recall layer instead of re-owning a parallel theorem name.

variable {n : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) -- Domain sampling: -- * primary domain: convex-analysis extremum theory on a feasible set; -- * inspected canonical owners: -- `IsMinOn.of_isLocalMinOn_of_convexOn`, -- `ConvexOn.convex_le`, -- `StrictConvexOn.eq_of_isMinOn`; -- * source/core/bridge triage: -- the local-to-global item is a recall of the core owner -- `IsMinOn.of_isLocalMinOn_of_convexOn`, -- while the convexity of the feasible minimizer set is the source-facing bridge/view theorem -- derived from `ConvexOn`. #check (fun {S : Set Point} {f : Point → ℝ} {xStar : Point} (hxStar : xStar ∈ S) (h_localMin : IsLocalMinOn f S xStar) (hf_convex : ConvexOn ℝ S f) ↦ IsMinOn.of_isLocalMinOn_of_convexOn hxStar h_localMin hf_convex)

Theorem 8.2.18

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

Source header · Attribution source

Chapter08 Theorem 8.2.18: under the Chapter 8 differentiability setup, if problem is a convex programming problem and (xStar, lamStar) is a KKT pair for problem, then xStar is a global minimizer of problem on its feasible set.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
local notation "EPoint" => EuclideanSpace ℝ (Fin n)

-- Domain-style sampling:
-- * primary domain: convex constrained optimization and KKT sufficiency
-- * sampled owner declarations:
--   `ConstrainedOptimizationProblem.IsKKTPoint`
--   `ConstrainedOptimizationProblem.HasConstraintGradientsAt`
--   `IsMinOn`
--   `ConstrainedOptimizationProblem.IsConvexProgramming`
--   `ConstrainedOptimizationProblem.IsGlobalMinimizer`
-- * source/core/bridge triage:
--   `source-facing`: the global-minimizer conclusion for constrained problems
--   `core/canonical`: the KKT owner `problem.IsKKTPoint`, the convex-programming owner
--     `problem.IsConvexProgramming`, and the minimizer owner `IsMinOn`
--   `bridge/view`: `problem.IsGlobalMinimizer xStar`, which packages feasibility together with
--     the core `IsMinOn` conclusion
-- * primitive data: the constrained problem, the candidate point, the multiplier vector, and
--   the smoothness data at `xStar`
-- * derived API: the `IsMinOn` conclusion and its constrained-global-minimizer bridge
namespace ConstrainedOptimizationProblem
theorem IsKKTPoint.isGlobalMinimizer_of_isConvexProgramming
    {problem : ConstrainedOptimizationProblem n m E I} {xStar : Point} {lamStar : Fin m → ℝ}
    (h_kkt : problem.IsKKTPoint xStar lamStar)
    (h_objective : DifferentiableAt ℝ problem.objective xStar)
    (h_constraints : problem.HasConstraintGradientsAt xStar)
    (h_convex : problem.IsConvexProgramming) :
    problem.IsGlobalMinimizer xStar

Theorem 8.2.19

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

Source header · Attribution source

Chapter08 Theorem 8.2.19: if the objective of a constrained optimization problem is strictly convex on its feasible set and a feasible global minimizer exists, then that minimizer is unique.

variable {n m : ℕ} {E I : Set (Fin m)} local notation "Point" => Fin n → ℝ theorem existsUnique_globalMinimizer_of_strictConvexObjective (problem : ConstrainedOptimizationProblem n m E I) (h_strict : StrictConvexOn ℝ problem.feasibleSet problem.objective) (h_exists : ∃ x : Point, problem.IsGlobalMinimizer x) : ∃! x : Point, problem.IsGlobalMinimizer x

Definition 8.2.extra.1

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

Source header · Attribution source

Chapter08 Definition 8.2-extra-1: descentDirections f xStar is the set of descent directions of f at xStar.

variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
def descentDirections (f : E → ℝ) (xStar : E) : Set E :=
  {d | IsDescentDirectionAt f xStar d}

Notation 8.2.extra.2

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

Source header · Attribution source

Chapter08 Notation 8.2-extra-2: the textbook notation 𝓛[problem](x, lam) unfolds to the canonical Chapter 8 Lagrangian owner call problem.lagrangian x lam.

notation:max "𝓛[" problem "](" x ", " lam ")" => ConstrainedOptimizationProblem.lagrangian problem x lam variable {n m : ℕ} {E I : Set (Fin m)} local notation "Point" => Fin n → ℝ namespace ConstrainedOptimizationProblem theorem lagrangian_notation_eq (problem : _root_.ConstrainedOptimizationProblem n m E I) (x : Point) (lam : Fin m → ℝ) : 𝓛[problem](x, lam) = problem.lagrangian x lam

Example 8.2.extra.3

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

Source header · Attribution source

The objective in the Chapter 8 constraint-qualification counterexample is x ↦ x 0.

local notation "Point" => Fin 2 → ℝ
local notation "EPoint" => EuclideanSpace ℝ (Fin 2)
def cubicConstraintCounterexampleObjective (x : Point) : ℝ :=
  x 0

Assumption 8.2.extra.4

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

Source header · Attribution source

Chapter08 Assumption 8.2-extra-4: the regularity assumption at xStar is that the sequential feasible directions of problem.feasibleSet at xStar which are descent directions of problem.objective, computed via the Euclidean model already used for gradients in Definition_8_2_2, are exactly the linearized feasible directions at xStar with the same descent property.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
namespace ConstrainedOptimizationProblem
def regularityAssumptionAt
    (problem : ConstrainedOptimizationProblem n m E I) (xStar : Point) : Prop :=
  posTangentConeAt problem.feasibleSet xStar ∩
      ((WithLp.toLp 2) ⁻¹'
        descentDirections problem.euclideanObjective (WithLp.toLp 2 xStar)) =
    problem.linearizedFeasibleDirectionSet xStar ∩
      ((WithLp.toLp 2) ⁻¹'
        descentDirections problem.euclideanObjective (WithLp.toLp 2 xStar))

Definition 8.2.extra.5

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

Source header · Attribution source

Chapter08 Definition 8.2-extra-5 (1): the source notion “minimize f over Ω as a convex program” is the canonical convex-analysis owner ConvexOn ℝ Ω f.

variable {n m : ℕ} {E I : Set (Fin m)} local notation "Point" => Fin n → ℝ -- Domain-style sampling: -- * primary domain: convex analysis of constrained feasible sets -- * sampled owner declarations: -- `ConstrainedOptimizationProblem.feasibleSet`, -- `ConvexOn`, -- `Convex.affine_preimage`, -- `ConcaveOn.convex_ge` -- * owner abstraction: `ConstrainedOptimizationProblem` carries the primitive objective and -- constraints, while convex programming is the bridge -- `ConvexOn ℝ problem.feasibleSet problem.objective` -- * primitive data: the objective, the constraint family, and the equality/inequality index sets -- * derived API: `problem.feasibleSet`, its convexity under linear/concave hypotheses, and -- `problem.IsConvexProgramming` -- Layer triage: -- * source-facing: `ConstrainedOptimizationProblem.IsConvexProgramming` -- * core/canonical: `ConvexOn ℝ Ω f` -- * bridge/view: `problem.IsConvexProgramming ↔ ConvexOn ℝ problem.feasibleSet problem.objective` #check (ConvexOn ℝ : Set Point → (Point → ℝ) → Prop)

8.3 — Second-Order Optimality Conditions

Definition 8.3.1

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

Source header · Attribution source

Chapter08 Definition 8.3.1: equivalently, d ∈ S(xStar, lamStar) exactly when d ∈ SFD(xStar, problem.feasibleSet) admits witnessing sequences xStar + delta k • dSeq k along which the multiplier-weighted constraint sum ∑ i : Fin m, lamStar i * problem.constraint i (xStar + delta k • dSeq k) vanishes.

open Filter
open scoped BigOperators
variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
namespace ConstrainedOptimizationProblem

-- Domain sampling:
-- * primary domain: constrained optimization with KKT multipliers and tangent-cone feasible
--   directions
-- * inspected Chapter 8 owner declarations:
--   `ConstrainedOptimizationProblem.activeIneqIndexSet` from `Definition_8_1_1`
--   `ConstrainedOptimizationProblem.IsKKTPoint` from `Theorem_8_2_7`
--   `posTangentConeAt` and
--   `mem_posTangentConeAt_iff_exists_seq_pos` from `Definition_8_2_3`
-- * source-facing owner kept here: `problem.IsSequentialNullConstraintDirectionAt`
-- * primitive data reused from upstream owners:
--   KKT feasibility/duality/stationarity/complementary-slackness from `problem.IsKKTPoint`
--   and active inequality indices from `problem.activeIneqIndexSet`
-- * derived API kept here: positive active indices, the sequence witness predicate, the
--   source-facing sequential null constraint direction owner, and the derived nonnegativity of
--   the remaining active inequalities from feasibility
-- * core/canonical feasible-direction owner reused directly:
--   `posTangentConeAt problem.feasibleSet xStar`, with the tangent-cone bridge supplied by
--   mathlib
theorem mem_sequentialNullConstraintDirections_iff_exists_seq
    (problem : ConstrainedOptimizationProblem n m E I)
    (xStar d : Point) (lamStar : Fin m → ℝ) :
    d ∈ problem.sequentialNullConstraintDirections xStar lamStar ↔
      problem.IsKKTPoint xStar lamStar ∧
        d ≠ 0 ∧
        ∃ dSeq : ℕ → Point, ∃ delta : ℕ → ℝ,
          problem.IsSequentialNullConstraintDirectionSeq xStar lamStar d dSeq delta ∧
            (∀ k,
              ∑ i : Fin m, lamStar i * problem.constraint i (xStar + delta k • dSeq k) = 0)

Definition 8.3.2

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

Source header · Attribution source

Chapter08 Definition 8.3.2 (2): formula (8.3.15) rewrites G(xStar, lamStar) against the Chapter 8 owner problem.linearizedFeasibleDirectionSet xStar.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
namespace ConstrainedOptimizationProblem

-- Domain sampling:
-- * primary domain: second-order constrained optimization via the Chapter 8 null-constraint set
--   `G(xStar, lamStar)`
-- * inspected owner declarations:
--   `ConstrainedOptimizationProblem.linearizedFeasibleDirectionSet` from `Definition_8_2_2`
--   `ConstrainedOptimizationProblem.IsKKTPoint`,
--   `ConstrainedOptimizationProblem.positiveActiveIneqIndexSet`, and
--   `ConstrainedOptimizationProblem.sequentialNullConstraintDirections`
--   from `Definition_8_3_1`
--   `tangentConeAt ℝ X xStar` as the canonical owner behind the source's sequential feasible
--   directions from `Definition_8_2_3`
-- * owner abstraction chosen here: the source-facing set
--   `linearizedNullConstraintDirections`, expressed directly as a bridge/view on the canonical
--   upstream owner `problem.linearizedFeasibleDirectionSet xStar`
-- * primitive data reused from the owner chain: a linearized feasible direction and the positive
--   active inequality index set
-- * derived API here: the explicit `G(xStar, lamStar)` membership formulas and subset lemmas
theorem mem_linearizedNullConstraintDirections_iff
    (problem : ConstrainedOptimizationProblem n m E I)
    (xStar : Point) (lamStar : Fin m → ℝ) (d : Point) :
    d ∈ problem.linearizedNullConstraintDirections xStar lamStar ↔
      d ∈ problem.linearizedFeasibleDirectionSet xStar ∧
        d ≠ 0 ∧
          ∀ i ∈ problem.positiveActiveIneqIndexSet xStar lamStar,
            problem.linearizedConstraintPairing xStar d i = 0

Theorem 8.3.3

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

Source header · Attribution source

Chapter08 Theorem 8.3.3 (1): if xStar is a local minimizer of problem, the objective and every constraint are twice continuously differentiable at xStar, the constraint qualification (8.2.19) holds at xStar, and lamStar is a KKT multiplier at xStar, then the Lagrangian Hessian is nonnegative on every direction in the source set problem.sequentialNullConstraintDirections xStar lamStar = S(xStar, lamStar).

open Filter InnerProductSpace
open scoped Gradient
variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
local notation "EPoint" => EuclideanSpace ℝ (Fin n)
local notation "Multiplier" => Fin m → ℝ
namespace ConstrainedOptimizationProblem

-- Source-facing reuse:
-- * owner chain: `Definition_8_3_2` already provides the Chapter 8 constrained problem,
--   `sequentialNullConstraintDirections = S(xStar, lamStar)`, and
--   `linearizedNullConstraintDirections = G(xStar, lamStar)`
-- * source constraint qualification owner reused directly from `Theorem_8_2_7`:
--   `problem.ConstraintQualificationAt xStar`
-- * this file adds only the Lagrangian Hessian quadratic surface used in Theorem 8.3.3
-- * the Lagrangian owner is already `problem.euclideanLagrangian` upstream, so the Hessian is
--   expressed on that existing Euclidean transport instead of rebuilding a function-space model
theorem secondOrderNecessaryCondition_on_sequentialNullConstraintDirections
    (problem : ConstrainedOptimizationProblem n m E I)
    (xStar d : Point) (lamStar : Multiplier)
    (h_localMin : IsLocalMinOn problem.objective problem.feasibleSet xStar)
    (h_objective : ContDiffAt ℝ 2 problem.objective xStar)
    (h_constraints : ∀ i, ContDiffAt ℝ 2 (problem.constraint i) xStar)
    (h_cq : problem.ConstraintQualificationAt xStar)
    (h_kkt : problem.IsKKTPoint xStar lamStar)
    (hd : d ∈ problem.sequentialNullConstraintDirections xStar lamStar) :
    0 ≤ problem.lagrangianHessianQuadratic xStar lamStar d

Theorem 8.3.4

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

Source header · Attribution source

Chapter08 Theorem 8.3.4: if xStar is a KKT point of problem with multiplier vector lamStar, the objective and every constraint are twice continuously differentiable at xStar, and the Lagrangian Hessian quadratic form is strictly positive on every direction in problem.linearizedNullConstraintDirections xStar lamStar = G(xStar, lamStar), then xStar is a strict local minimizer of problem.objective on problem.feasibleSet.

open Filter InnerProductSpace
open scoped Gradient
variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
local notation "EPoint" => EuclideanSpace ℝ (Fin n)
local notation "Multiplier" => Fin m → ℝ
namespace ConstrainedOptimizationProblem

-- Domain sampling:
-- * primary domain: second-order sufficient conditions for constrained nonlinear programming
-- * source-facing owner in the chapter: `ConstrainedOptimizationProblem`
-- * inspected owner-chain declarations:
--   `ConstrainedOptimizationProblem.IsKKTPoint` and
--   `ConstrainedOptimizationProblem.linearizedNullConstraintDirections`
--   from `Definition_8_3_2`
-- * inspected theorem-local owner:
--   `ConstrainedOptimizationProblem.lagrangianHessianQuadratic`
--   from `Theorem_8_3_3`
-- * layer targeted here: source-facing theorem stated on the existing owner chain, not a new
--   wrapper or duplicate critical-cone API
-- * primitive data reused: constrained problem, feasible set, KKT pair, and
--   `linearizedNullConstraintDirections = G(xStar, lamStar)`
-- * derived API reused: `lagrangianHessianQuadratic`
theorem isStrictLocalMinOn_of_positive_lagrangianHessian_on_linearizedNullConstraintDirections
    (problem : ConstrainedOptimizationProblem n m E I)
    (xStar : Point) (lamStar : Multiplier)
    (h_kkt : problem.IsKKTPoint xStar lamStar)
    (h_objective : ContDiffAt ℝ 2 problem.objective xStar)
    (h_constraints : ∀ i, ContDiffAt ℝ 2 (problem.constraint i) xStar)
    (h_positive :
      ∀ d ∈ problem.linearizedNullConstraintDirections xStar lamStar,
        0 < problem.lagrangianHessianQuadratic xStar lamStar d) :
    IsStrictLocalMinOn problem.objective problem.feasibleSet xStar

Corollary 8.3.5

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

Source header · Attribution source

Chapter08 Corollary 8.3.5: under the C² hypotheses of Theorem 8.3.4, if xStar is a KKT point of problem with multiplier vector lamStar and the Lagrangian Hessian quadratic form is strictly positive on every nonzero direction whose equality-constraint pairings and strictly positive active-inequality pairings vanish at xStar, then xStar is a strict local minimizer of problem.objective on problem.feasibleSet.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => Fin n → ℝ
local notation "Multiplier" => Fin m → ℝ
namespace ConstrainedOptimizationProblem

-- Domain sampling:
-- * primary domain: second-order sufficient conditions for constrained nonlinear programming
-- * inspected owner declarations in the same chapter/project:
--   `ConstrainedOptimizationProblem.positiveActiveIneqIndexSet` from `Definition_8_3_1`
--   `ConstrainedOptimizationProblem.linearizedNullConstraintDirections` and
--   `mem_linearizedNullConstraintDirections_iff_explicit` from `Definition_8_3_2`
--   `ConstrainedOptimizationProblem.lagrangianHessianQuadratic` from `Theorem_8_3_3`
--   `isStrictLocalMinOn_of_positive_lagrangianHessian_on_linearizedNullConstraintDirections`
--   from `Theorem_8_3_4`
-- * owner abstraction chosen first: `problem.linearizedNullConstraintDirections xStar lamStar`
-- * layer targeted here: `bridge/view`; the corollary keeps the textbook `A₊`-style vanishing
--   hypotheses but reuses the canonical owner theorem instead of restating a parallel core API
-- * primitive data reused: KKT pair, active-set owners, linearized pairings, and the
--   Lagrangian Hessian quadratic form
-- * derived API here: only the source-facing bridge from the unpacked `A₊` conditions to the
--   canonical linearized-null-direction positivity hypothesis
theorem isStrictLocalMinOn_of_isKKTPoint_of_positive_lagrangianHessian_on_APlusDirections
    (problem : ConstrainedOptimizationProblem n m E I)
    (xStar : Point) (lamStar : Multiplier) (h_kkt : problem.IsKKTPoint xStar lamStar)
    (h_objective : ContDiffAt ℝ 2 problem.objective xStar)
    (h_constraints : ∀ i, ContDiffAt ℝ 2 (problem.constraint i) xStar)
    (h_positive :
      ∀ d : Point,
        d ≠ 0 →
          (∀ i ∈ problem.eqIndices, problem.linearizedConstraintPairing xStar d i = 0) →
          (∀ i ∈ problem.positiveActiveIneqIndexSet xStar lamStar,
            problem.linearizedConstraintPairing xStar d i = 0) →
          0 < problem.lagrangianHessianQuadratic xStar lamStar d) :
    IsStrictLocalMinOn problem.objective problem.feasibleSet xStar

Definition 8.3.extra.1

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

Source header · Attribution source

Chapter08 Definition 8.3-extra-1: the source's strong active constraint index set I₊(xStar) is already owned by ConstrainedOptimizationProblem.positiveActiveIneqIndexSet in Definition_8_3_1.lean. This file therefore stays at the recall layer and reuses that canonical Chapter 8 owner directly instead of keeping a duplicate local alias.

variable {n m : ℕ} {E I : Set (Fin m)}
local notation "Point" => EuclideanSpace ℝ (Fin n)
#check ConstrainedOptimizationProblem.positiveActiveIneqIndexSet

8.4 — Duality

Theorem 8.4.1

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

Source header · Attribution source

Chapter08 Theorem 8.4.1: let xStar be a global minimizer of the convex primal problem min problem.objective x subject to 0 ≤ problem.constraint i x for i : Fin m. If problem.objective and every problem.constraint i are C¹ and the regularity condition problem.regularityAssumptionAt xStar holds, then there exists a multiplier vector lamStar such that lamStar maximizes the dual objective problem.dualObjective on the admissible multiplier set problem.admissibleMultiplierSet, xStar minimizes 𝓛[problem](·, lamStar) on Set.univ, and the primal value agrees with problem.dualObjective lamStar in WithBot ℝ.

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

-- Domain-style sampling:
-- * source-facing theorem: dual-maximizer existence for the inequality-only convex primal
--   problem
-- * reused Chapter 8 owners:
--   `problem.IsGlobalMinimizer`, `problem.regularityAssumptionAt`, and the notation
--   `𝓛[problem](x, lam)`
-- * local dual owners kept here:
--   the multiplier-level extended-real dual objective `problem.dualObjective`, the admissible
--   multiplier set
--   `problem.admissibleMultiplierSet`, the derived dual-solution owner `problem.IsDualSolution`,
--   and the attained bridge `problem.attainedDualFeasibleSet`
-- * layer triage:
--   source-facing: `problem.IsDualOptimalPair xStar lamStar`
--   core/canonical: `problem.dualObjective` and `problem.IsDualSolution lamStar`
--   bridge/view: `problem.attainedDualFeasibleSet`
theorem exists_dualMaximizer_of_isGlobalMinimizer_of_convexProblem
    (problem : ConstrainedOptimizationProblem n m (∅ : Set (Fin m)) Set.univ) (xStar : Point)
    (h_min : problem.IsGlobalMinimizer xStar)
    (h_objective_convex : ConvexOn ℝ Set.univ problem.objective)
    (h_constraint_concave : ∀ i, ConcaveOn ℝ Set.univ (problem.constraint i))
    (h_objective_contDiff : ContDiff ℝ 1 problem.objective)
    (h_constraint_contDiff : ∀ i, ContDiff ℝ 1 (problem.constraint i))
    (h_regularity : problem.regularityAssumptionAt xStar) :
    ∃ lamStar : Multiplier,
      problem.IsDualOptimalPair xStar lamStar

Theorem 8.4.2

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

Source header · Attribution source

Chapter08 Theorem 8.4.2: if xPrime is feasible for the primal problem (8.4.1) and (x, λ) is attained dual feasible for the dual problem (8.4.2), then problem.objective xPrime ≥ 𝓛[problem](x, lam).

variable {n m : ℕ}
local notation "Point" => Fin n → ℝ
local notation "Multiplier" => Fin m → ℝ
namespace ConstrainedOptimizationProblem

-- Domain sampling:
-- * primary domain: convex constrained optimization duality
-- * inspected owner declarations:
--   `ConstrainedOptimizationProblem.feasibleSet`,
--   `ConstrainedOptimizationProblem.lagrangian`,
--   `ConstrainedOptimizationProblem.attainedDualFeasibleSet`,
--   `ConstrainedOptimizationProblem.lagrangian_le_of_mem_attainedDualFeasibleSet`,
--   `ConstrainedOptimizationProblem.mem_attainedDualFeasibleSet_iff`
--   from `Chapter08.Theorem_8_4_1`
-- * owner abstraction reused here: the Chapter 8 constrained-problem owner surface
--   `problem.feasibleSet`, `problem.attainedDualFeasibleSet`, and the notation
--   `𝓛[problem](x, lam)`
-- * layer triage:
--   source-facing: primal/dual feasibility and the weak-duality inequality
--   core/canonical: `ConstrainedOptimizationProblem.lagrangian`
--   bridge/view: the notation `𝓛[problem](x, lam)`
-- * primitive data reused from that owner: the problem objective, common constraint family,
--   primal feasible set, Lagrangian, and attained dual-feasible bridge
-- * derived API kept here: only the new weak-duality theorem
theorem weakDuality
    (problem : ConstrainedOptimizationProblem n m (∅ : Set (Fin m)) Set.univ)
    {xPrime x : Point} {lam : Multiplier}
    (hxPrime : xPrime ∈ problem.feasibleSet)
    (hdual : (x, lam) ∈ problem.attainedDualFeasibleSet) :
    problem.objective xPrime ≥ 𝓛[problem](x, lam)