Chapter 09 — Quadratic Programming

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

Exercise 9.1

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

Source header · Attribution source

Exercise 9.1 as the chapter's canonical QuadraticProgram: diagonal Hessian Diag(h), linear term g, and the box feasible set ‖x‖∞ ≤ 1.

variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin (n + n))
def chapter09Exercise91Problem (h : Point) (g : Point) : QuadraticProgram n 0 (n + n)

Exercise 9.2

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

Source header · Attribution source

Chapter09 Exercise 9.2: if xStar is a feasible local minimizer of the quadratic program P, then there exists a multiplier vector λ* such that (xStar, λ*) is a Chapter 8 KKT pair for the constrained-problem bridge of P and the Chapter 9 second-order necessary condition holds.

variable {n me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "pointEquiv" => EuclideanSpace.equiv (Fin n) ℝ
theorem localMinimizer_has_isKKTPoint_with_secondOrderNecessaryCondition
    (P : QuadraticProgram n me mi) (xStar : Point)
    (hLocalMin : IsLocalMinOn P P.feasibleSet xStar)
    (hxStar : xStar ∈ P.feasibleSet)
    ∃ lamStar : Fin (me + mi) → ℝ,
      P.toConstrainedOptimizationProblem.IsKKTPoint (pointEquiv xStar) lamStar ∧
        P.HasSecondOrderNecessaryCondition xStar lamStar

Exercise 9.3

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

Source header · Attribution source

Chapter09 Exercise 9.3: when P.G is positive definite, the explicit dual objective from (9.2.8) equals the infimum over x : ℝ^n of the Chapter 9 quadratic-program Lagrangian with the multiplier pair (dual.eqMultiplier, dual.ineqMultiplier) for every dual variable dual satisfying the stationarity relation (9.2.9). The inequality-multiplier nonnegativity from (9.2.10) is irrelevant for this identity and is recovered later by passing to a dual-feasible variable. This is the source bridge identifying the explicit dual objective formula with the Lagrangian dual of (9.1.1)-(9.1.3).

namespace QuadraticProgram

-- Domain-style sampling in Chapter 9:
-- * core/canonical owner: `QuadraticProgram` from `Definition_9_1_extra_1`
-- * derived dual API: `DualVariable`, `SatisfiesDualStationarity`, `dualObjective`, and
--   `IsDualFeasible` from
--   `Theorem_9_2_1`
-- * bridge/view here: Exercise 9.3 identifies that explicit dual objective with the infimum of
--   the canonical quadratic-program Lagrangian from `Theorem_9_2_3`
--
-- Primitive data stay upstream in the chapter owner. This file contributes only the source-facing
-- bridge theorem.
variable {n me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
open scoped QuadraticProgram
theorem dualObjective_eq_sInf_lagrangian_of_stationarity
    (P : QuadraticProgram n me mi) (hG : P.G.PosDef) (dual : DualVariable P)
    (hstationarity : P.SatisfiesDualStationarity dual) :
    P.dualObjective hG dual =
      sInf (Set.range fun x : Point ↦ ℒ[P] x (dual.eqMultiplier, dual.ineqMultiplier))

Exercise 9.4

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

Source header · Attribution source

Chapter09 Exercise 9.4 (1): the explicit dual problem max chapter09Exercise94DualObjective λ subject to λ ∈ chapter09Exercise94DualFeasibleSet is solved by chapter09Exercise94DualOptimizer = 1.

theorem chapter09Exercise94DualIsMaxOn : IsMaxOn chapter09Exercise94DualObjective chapter09Exercise94DualFeasibleSet chapter09Exercise94DualOptimizer

Exercise 9.5

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

Source header · Attribution source

Chapter09 Exercise 9.5: if problem.objective is convex, each problem.constraint i is concave, and problem satisfies Slater's condition, then xStar is a global minimizer of problem exactly when it can be paired with an admissible multiplier vector forming a saddle point of the Lagrangian 𝓛[problem].

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

-- Domain-style sampling:
-- * primary domain: convex programming duality for inequality-only constrained problems
-- * inspected owner declarations:
--   `ConstrainedOptimizationProblem.feasibleSet` from `Chapter01.Definition_1_1_extra_1`
--   `ConstrainedOptimizationProblem.IsGlobalMinimizer` from `Chapter08.Definition_8_1_2`
--   `ConstrainedOptimizationProblem.IsDualOptimalPair` and
--   `ConstrainedOptimizationProblem.admissibleMultiplierSet` from `Chapter08.Theorem_8_4_1`
--   `IsSaddlePointOn` from mathlib
-- * best owner abstraction: the Chapter 8 inequality-only constrained-problem owner
--   `ConstrainedOptimizationProblem n m (∅ : Set (Fin m)) Set.univ`
-- * primitive data vs. derived API:
--   the primitive data are already upstream in `ConstrainedOptimizationProblem`;
--   this file keeps only the derived Slater-condition predicate, the saddle-pair predicate,
--   and the exercise theorem
-- * layer triage:
--   source-facing: `problem.SatisfiesSlaterCondition` and `problem.IsSaddlePair`
--   core/canonical: `problem.IsGlobalMinimizer`, `problem.admissibleMultiplierSet`,
--   `𝓛[problem](x, lam)`, and `IsSaddlePointOn`
--   bridge/view: `problem.IsDualOptimalPair xStar lamStar` from Chapter 8
namespace ConstrainedOptimizationProblem
theorem isGlobalMinimizer_iff_exists_isSaddlePair_of_convex_of_slaterCondition
    (problem : ConstrainedOptimizationProblem n m (∅ : Set (Fin m)) Set.univ) (xStar : Point)
    (h_objective_convex : ConvexOn ℝ Set.univ problem.objective)
    (h_constraint_concave : ∀ i, ConcaveOn ℝ Set.univ (problem.constraint i))
    (h_slater : problem.SatisfiesSlaterCondition) :
    problem.IsGlobalMinimizer xStar ↔ ∃ lamStar : Multiplier, problem.IsSaddlePair xStar lamStar

Exercise 9.6

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

Source header · Attribution source

Chapter09 Exercise 9.6 (1): the smallest-circle problem is formulated as the convex program minimizing chapter09Exercise96PrimalObjective over chapter09Exercise96PrimalFeasibleSet, and the optimizer is the center-radius pair chapter09Exercise96PrimalOptimizer.

open scoped BigOperators local notation "Point" => EuclideanSpace ℝ (Fin 2) local notation "DualPoint" => Fin 4 → ℝ -- Domain sampling: -- * source-facing layer: the smallest-enclosing-circle exercise on center/radius-squared pairs -- and dual simplex multipliers; -- * core/canonical owners inspected: `IsMinOn`, `IsMaxOn`, `Metric.closedBall`, `stdSimplex`, -- `Finset.centerMass`; -- * owner choice: keep the source-facing center/radius primitive data for the primal feasible set -- because the radius varies with the point, so `Metric.closedBall` is only a companion -- geometric owner here, while the dual feasible region itself is canonically `stdSimplex`. -- * bridge/view decision: keep the raw weighted dual sum because the dual objective is defined on -- all multipliers, then expose the canonical `centerMass` view on the feasible simplex where -- the weights sum to `1`. theorem chapter09Exercise96PrimalIsMinOn : IsMinOn chapter09Exercise96PrimalObjective chapter09Exercise96PrimalFeasibleSet chapter09Exercise96PrimalOptimizer

Exercise 9.7

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

Source header · Attribution source

Exercise 9.7: if the Hessian B = problem.G is positive definite, then the source explicit dual expression λ ↦ bᵀ λ - (1 / 2) * (A λ - g)ᵀ B⁻¹ (A λ - g) is exactly the infimum over x : ℝ^n of the canonical Chapter 9 Lagrangian ℒ[problem.toQuadraticProgram] x (λ, 0). This is the source-faithful bridge from the equality- constrained textbook dual formula to the existing Chapter 9 dual owner.

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

-- Domain-style sampling for this file:
-- * primary domain: equality-constrained quadratic-program duality.
-- * inspected owner declarations:
--   - `EqualityConstrainedQuadraticProgram.toQuadraticProgram` and
--     `EqualityConstrainedQuadraticProgram.toDualVariable` from
--     `Problem_9_3_extra_1`;
--   - `QuadraticProgram.DualVariable`, `QuadraticProgram.dualObjective`, and
--     `QuadraticProgram.SatisfiesDualStationarity` from `Theorem_9_2_1`;
--   - `QuadraticProgram.dualObjective_eq_sInf_lagrangian_of_stationarity` from `Exercise_9_3`.
-- * source/core/bridge triage:
--   - source-facing layer here: the Exercise 9.7 equality-multiplier formula;
--   - core/canonical layer: `QuadraticProgram` together with its dual-variable owner;
--   - bridge/view layer: `problem.toDualVariable λ`, converting an equality multiplier `λ` to
--     the canonical dual variable of the associated quadratic program.
-- * primitive data vs. derived API:
--   - primitive data remain owned by `EqualityConstrainedQuadraticProgram`;
--   - this file contributes only the canonical bridge from `λ` to the upstream dual owner and
--     the positive-definite theorem identifying the source formula with the Lagrangian dual
--     value.
namespace EqualityConstrainedQuadraticProgram
open scoped QuadraticProgram
theorem dualObjective_eq_sInf_lagrangian
    (problem : EqualityConstrainedQuadraticProgram n m) (hG : problem.G.PosDef)
    (lam : ConstraintPoint) :
    dotProduct problem.b lam - (1 / 2 : ℝ) *
        dotProduct (WithLp.toLp 2 (problem.A.mulVec lam.ofLp) - problem.g)
          (WithLp.toLp 2
            (problem.G⁻¹.mulVec (WithLp.toLp 2 (problem.A.mulVec lam.ofLp) - problem.g).ofLp)) =
      sInf (Set.range fun x : Point ↦ ℒ[problem.toQuadraticProgram] x (lam, 0))

Exercise 9.8

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

Source header · Attribution source

Chapter09 Exercise 9.8 (1): the equality-constrained quadratic program with objective (1, -1)ᵀ x + (1 / 2) * xᵀ [[1, 2], [2, 4]] x and constraint x 0 + x 1 = 1 is minimized at (0, 1)ᵀ.

open Matrix
local notation "Point" => EuclideanSpace ℝ (Fin 2)
theorem chapter09Exercise98_isMinOn :
    IsMinOn
      chapter09Exercise98Problem.objective
      chapter09Exercise98Problem.feasibleSet
      chapter09Exercise98Optimizer

Exercise 9.9

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

Source header · Attribution source

Chapter09 Exercise 9.9 (1): for the block partition Aᵀ = [B N], inserting the seed matrix [[0], [I_(n-m)]] into the generic construction (9.3.42) recovers the standard choice V = [[-B⁻¹ N], [I_(n-m)]] from (9.3.37)-(9.3.38).

open Matrix variable {m k : ℕ} local notation "Ambient" => Sum (Fin m) (Fin k) local notation "ConstraintMatrix" => Matrix Ambient (Fin m) ℝ local notation "ChoiceMatrix" => Matrix Ambient (Fin k) ℝ theorem chapter09Exercise99_blockSeed_recovers_standardChoice (B : Matrix (Fin m) (Fin m) ℝ) (N : Matrix (Fin m) (Fin k) ℝ) : nullSpaceCorrection (Matrix.fromRows B⁻¹ (0 : Matrix (Fin k) (Fin m) ℝ)) (Matrix.fromCols B N)ᵀ (Matrix.fromRows (0 : Matrix (Fin m) (Fin k) ℝ) (1 : Matrix (Fin k) (Fin k) ℝ)) = Matrix.fromRows (-(B⁻¹ * N)) (1 : Matrix (Fin k) (Fin k) ℝ)

Exercise 9.10

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

Source header · Attribution source

Chapter09 Exercise 9.10: if A : ℝ^(n × m) has full column rank, if Z is a reduced-null- space matrix for A, and if the reduced Hessian Zᵀ G Z is positive definite, then the KKT matrix (9.3.47) is nonsingular.

open Matrix variable {n m k : ℕ} local notation "HessianMatrix" => Matrix (Fin n) (Fin n) ℝ local notation "ConstraintMatrix" => Matrix (Fin n) (Fin m) ℝ local notation "ReducedBasisMatrix" => Matrix (Fin n) (Fin k) ℝ theorem kktMatrix_isUnit_of_fullColumnRank_of_reducedHessian_posDef (G : HessianMatrix) (A : ConstraintMatrix) (Z : ReducedBasisMatrix) (hA : Matrix.rank A = m) (hZ : IsReducedNullMatrix A Z) (hReduced : (Z.transpose * G * Z).PosDef) : IsUnit (kktMatrix G A)

Exercise 9.11

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

Source header · Attribution source

Chapter09 Exercise 9.11 (1): if G is positive definite and A has full column rank, then the U block in (9.3.50) is G⁻¹ - G⁻¹ A (Aᵀ G⁻¹ A)⁻¹ Aᵀ G⁻¹, which is equation (9.3.53).

open Matrix variable {n m : ℕ} local notation "HessianMatrix" => Matrix (Fin n) (Fin n) ℝ local notation "ConstraintMatrix" => Matrix (Fin n) (Fin m) ℝ local notation "DualMatrix" => Matrix (Fin m) (Fin m) ℝ -- Domain-style sampling for this file: -- * primary domain: KKT block matrices and Schur-complement inverse formulas. -- * core/canonical owners inspected: the Chapter 9 KKT owner `kktMatrix`, together with -- mathlib's block extraction owners `Matrix.toBlocks₁₁`/`toBlocks₁₂`/`toBlocks₂₂` and the -- Schur-complement inverse formula `Matrix.invOf_fromBlocks₁₁_eq`. -- * source-facing owner layer kept here: the inverse-KKT blocks `kktInverseU`, `kktInverseW`, -- and `kktInverseT` from formula `(9.3.50)`. -- * primitive data vs derived API: the primitive data are only these three extracted inverse -- blocks; the Exercise 9.11 formulas are derived equalities for those owners. theorem chapter09Exercise911_primalBlock_eq (G : HessianMatrix) (A : ConstraintMatrix) (hG : G.PosDef) (hA : Matrix.rank A = m) : kktInverseU G A = G⁻¹ - G⁻¹ * A * (A.transpose * G⁻¹ * A)⁻¹ * A.transpose * G⁻¹

Exercise 9.12

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

Source header · Attribution source

Chapter09 Exercise 9.12 (1): if A has full column rank, G is symmetric, Z spans ker Aᵀ, and the reduced Hessian Zᵀ G Z is positive definite, then the U block of (kktMatrix G A)⁻¹ is Z (Zᵀ G Z)⁻¹ Zᵀ, i.e. formula (9.3.58).

open Matrix variable {n m k : ℕ} local notation "HessianMatrix" => Matrix (Fin n) (Fin n) ℝ local notation "ConstraintMatrix" => Matrix (Fin n) (Fin m) ℝ local notation "LeftInverseMatrix" => Matrix (Fin n) (Fin m) ℝ local notation "ReducedBasisMatrix" => Matrix (Fin n) (Fin k) ℝ theorem kktInverseU_eq_nullSpaceFormula (G : HessianMatrix) (A : ConstraintMatrix) (Z : ReducedBasisMatrix) (hA : Function.Injective A.mulVec) (hGsym : G.IsSymm) (hZ : IsReducedNullMatrix A Z) (hReduced : (Zᵀ * G * Z).PosDef) : kktInverseU G A = Z * (Zᵀ * G * Z)⁻¹ * Zᵀ

Exercise 9.13

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

Source header · Attribution source

Chapter09 Exercise 9.13: if A : 𝕜^(m × n) has full row rank and Z is a reduced-null-space matrix for Aᵀ, then the block matrix [[B, Aᵀ], [A, 0]] = kktMatrix B (-Aᵀ) is nonsingular if and only if Zᵀ B Z is nonsingular. This packages the textbook null-space assumptions through the Chapter 9 owner IsReducedNullMatrix Aᵀ Z.

open Matrix
variable {𝕜 : Type*} [Field 𝕜] {m n : ℕ}
local notation "HessianMatrix" => Matrix (Fin n) (Fin n) 𝕜
local notation "ConstraintMatrix" => Matrix (Fin m) (Fin n) 𝕜
local notation "ReducedBasisMatrix" => Matrix (Fin n) (Fin (n - m)) 𝕜
local notation "PrimalPoint" => Fin n → 𝕜
local notation "DualPoint" => Fin m → 𝕜
local notation "ReducedPoint" => Fin (n - m) → 𝕜

-- Domain-style sampling for this file:
-- * primary domain: KKT block-matrix nonsingularity via reduced-null-space compression.
-- * core/canonical owners inspected: the Chapter 9 owners `kktMatrix` and
--   `IsReducedNullMatrix`, together with mathlib's block-matrix constructor
--   `Matrix.fromBlocks` and matrix rank owner `Matrix.rank`.
-- * source/core/bridge triage: this exercise is source-facing, while `IsReducedNullMatrix`
--   is the core owner for the null-space data and the displayed block matrix is the direct
--   `kktMatrix B (-Aᵀ)` specialization.
-- * primitive data vs derived API: the primitive data here are the block matrix and the
--   reduced-null-space owner hypothesis; the nonsingularity equivalence is derived API.
theorem blockMatrix_isUnit_iff_compression_isUnit
    (B : HessianMatrix)
    (A : ConstraintMatrix)
    (Z : ReducedBasisMatrix)
    (hA : Matrix.rank A = m)
    (hZ : IsReducedNullMatrix Aᵀ Z) :
    IsUnit (kktMatrix B (-Aᵀ)) ↔
      IsUnit (Zᵀ * B * Z)

Exercise 9.14

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

Source header · Attribution source

Chapter09 Exercise 9.14: the canonical QuadraticProgram formulation of the exercise, equivalently the problem with constraints 3 ≤ 3 * x 0 + x 1, 4 ≤ x 0 + 4 * x 1, 0 ≤ x 0, and 0 ≤ x 1, is minimized at (500, 500)ᵀ.

open Matrix

-- Domain sampling:
-- * primary domain: concrete quadratic programming on `ℝ²`
-- * inspected owner declarations:
--   `QuadraticProgram.objective`, `QuadraticProgram.feasibleSet`,
--   `QuadraticProgram.mem_feasibleSet_iff` from `Definition_9_1_extra_1`,
--   `IsMinOn` from mathlib
-- * best owner abstraction: the chapter's `QuadraticProgram`
-- * layer triage in this file:
--   source-facing: the concrete Exercise 9.14 quadratic program and its optimizer
--   core/canonical: `QuadraticProgram` with its objective/coercion and feasible-set API
--   bridge/view: the displayed polynomial and inequality characterizations below
-- * primitive data: Hessian, linear term, inequality matrix, inequality bound, optimizer
-- * derived API: the displayed objective formula, feasible-set membership, minimizer, and
--   optimal-value statements
local notation "Point" => EuclideanSpace ℝ (Fin 2)
local notation "ConstraintMatrix" => Matrix (Fin 4) (Fin 2) ℝ
theorem chapter09Exercise914_isMinOn :
    IsMinOn
      chapter09Exercise914Problem
      chapter09Exercise914Problem.feasibleSet
      chapter09Exercise914Optimizer

Exercise 9.15

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

Source header · Attribution source

Chapter09 Exercise 9.15: the canonical QuadraticProgram formulation of the exercise, equivalently the problem with constraints (1 / 2) * x 0 + (1 / 2) * x 1 ≤ 1, -x 0 + x 1 ≤ 2, 0 ≤ x 0, and 0 ≤ x 1, is minimized at (4 / 5, 6 / 5)ᵀ.

open Matrix

-- Domain sampling:
-- * primary domain: concrete quadratic programming on `ℝ²`
-- * inspected owner declarations:
--   `QuadraticProgram.objective`, `QuadraticProgram.feasibleSet`,
--   `QuadraticProgram.mem_feasibleSet_iff` from `Definition_9_1_extra_1`,
--   `IsMinOn` from mathlib
-- * best owner abstraction: the chapter's `QuadraticProgram`
-- * layer triage in this file:
--   source-facing: the concrete Exercise 9.15 quadratic program and its optimizer
--   core/canonical: `QuadraticProgram` with its objective/coercion and feasible-set API
--   bridge/view: the explicit polynomial and inequality characterizations below
-- * primitive data: Hessian, linear term, inequality matrix, inequality bound, optimizer
-- * derived API: the displayed objective formula, feasible-set membership, minimizer, and
--   optimal-value statements
local notation "Point" => EuclideanSpace ℝ (Fin 2)
local notation "ConstraintMatrix" => Matrix (Fin 4) (Fin 2) ℝ
theorem chapter09Exercise915_isMinOn :
    IsMinOn
      chapter09Exercise915Problem
      chapter09Exercise915Problem.feasibleSet
      chapter09Exercise915Optimizer

Exercise 9.16

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

Source header · Attribution source

Chapter09 Exercise 9.16: a primal-dual interior-point framework for the convex quadratic program P, obtained by extending the Section 9.7 linear-program scheme (9.7.20)-(9.7.21) with the quadratic Hessian term Q Δx in the dual linearization. The sequence state k represents (xᵏ, yᵏ, zᵏ), direction k represents (Δxᵏ, Δyᵏ, Δzᵏ), sigma k ∈ [0, 1] is the centering parameter σ_k, and alpha k is the step length. The initial state is strictly feasible, each direction solves the convex-quadratic primal-dual Newton system, and the next iterate is updated by (x, y, z) ↦ (x, y, z) + α (Δx, Δy, Δz) with x and z staying strictly positive.

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

-- Domain-style sampling in Chapter 9:
-- * source-facing layer here: convex quadratic programs in the standard primal-dual interior-point
--   form `min (1 / 2) xᵀ Q x + cᵀ x` subject to `A x = b` and `x ≥ 0`;
-- * core/canonical owner upstream: `QuadraticProgram n me mi` from
--   `Definition_9_1_extra_1`, together with the Chapter 9 primal-dual state API from
--   `Algorithm_9_7_1`;
-- * bridge/view here: `toQuadraticProgram`, specializing the canonical owner to the standard-form
--   inequality block `x ≥ 0`.
structure ConvexQuadraticPrimalDualInteriorPointFramework
    (P : ConvexQuadraticProgram n m) where
  state : ℕ → PrimalDualState n m
  direction : ℕ → PrimalDualDirection n m
  sigma : ℕ → ℝ
  alpha : ℕ → ℝ
  initial_mem : state 0 ∈ P.strictlyFeasibleSet
  sigma_mem_Icc : ∀ k : ℕ, sigma k ∈ Set.Icc (0 : ℝ) 1
  newton_system :
    ∀ k : ℕ, P.solvesPrimalDualNewtonSystem (state k) (sigma k) (direction k)
  update :
    ∀ k : ℕ, state (k + 1) = (state k).updated (alpha k) (direction k)
  next_strictPos :
    ∀ k : ℕ,
      IsStrictlyPositive (state (k + 1)).x ∧
        IsStrictlyPositive (state (k + 1)).s

9.1 — Optimality for Quadratic Programming

Theorem 9.1.1

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

Source header · Attribution source

Chapter09 Theorem 9.1.1: if xStar is a feasible local minimizer of the quadratic program P, then there exists a multiplier vector λ* for the associated constrained optimization problem such that (xStar, λ*) satisfies the Chapter 8 KKT conditions and dᵀ G d ≥ 0 on the Chapter 8 set `P.toConstrainedOptimizationProblem.linearizedNullConstraintDirections ((EuclideanSpace.equiv (Fin n) ℝ) xStar) λ*`, which is the source critical cone G(xStar, λ*) for the quadratic program.

variable {n me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
namespace QuadraticProgram
theorem exists_isKKTPoint_with_secondOrderNecessaryCondition
    (P : QuadraticProgram n me mi) (xStar : Point)
    (hxStar : xStar ∈ P.feasibleSet)
    (hLocalMin : IsLocalMinOn P.objective P.feasibleSet xStar) :
    ∃ lamStar : Fin (me + mi) → ℝ,
      P.toConstrainedOptimizationProblem.IsKKTPoint
          ((EuclideanSpace.equiv (Fin n) ℝ) xStar) lamStar ∧
        P.HasSecondOrderNecessaryCondition xStar lamStar

Theorem 9.1.2

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

Source header · Attribution source

Chapter09 Theorem 9.1.2: if xStar is a Chapter 8 KKT point of P.toConstrainedOptimizationProblem with multiplier vector λ*, then positivity of dᵀ G d on the Chapter 8 null-constraint directions implies that xStar is a strict local minimizer of P.objective on P.feasibleSet.

variable {n me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
namespace QuadraticProgram
theorem isStrictLocalMinOn_of_isKKTPoint_of_positive_on_linearizedNullConstraintDirections
    (P : QuadraticProgram n me mi) (xStar : Point) (lamStar : Fin (me + mi) → ℝ)
    (hKKT :
      P.toConstrainedOptimizationProblem.IsKKTPoint
        ((EuclideanSpace.equiv (Fin n) ℝ) xStar) lamStar)
    (hPositive :
      ∀ d : Point,
        (EuclideanSpace.equiv (Fin n) ℝ d) ∈
          P.toConstrainedOptimizationProblem.linearizedNullConstraintDirections
            ((EuclideanSpace.equiv (Fin n) ℝ) xStar) lamStar →
          0 < inner ℝ d (Matrix.toEuclideanLin P.G d)) :
    IsStrictLocalMinOn P.objective P.feasibleSet xStar

Theorem 9.1.3

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

Source header · Attribution source

Chapter09 Theorem 9.1.3: for a feasible point xStar of the quadratic program P, xStar is a local minimizer if and only if there exists a multiplier vector λ* such that (xStar, λ*) is a Chapter 8 KKT pair for the constrained-problem bridge of P and the Chapter 9 second-order necessary condition holds on the corresponding null-constraint directions.

variable {n me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "pointEquiv" => EuclideanSpace.equiv (Fin n) ℝ

-- Domain sampling:
-- * primary domain: quadratic-program local optimality, KKT multipliers, and second-order
--   necessary conditions;
-- * inspected project owners:
--   `QuadraticProgram` from `Definition_9_1_extra_1`,
--   `ConstrainedOptimizationProblem.IsKKTPoint` from `Chapter08.Theorem_8_2_7`,
--   `QuadraticProgram.HasSecondOrderNecessaryCondition` from `Theorem_9_1_1`,
--   and `ConstrainedOptimizationProblem.sequentialNullConstraintDirections` from
--   `Chapter08.Definition_8_3_1`;
-- * best owner abstraction: the matrix-based Chapter 9 owner `QuadraticProgram n me mi`,
--   together with the Chapter 8 KKT owner on `P.toConstrainedOptimizationProblem` and the
--   Chapter 9 second-order owner `P.HasSecondOrderNecessaryCondition`;
-- * source/core/bridge triage:
--   - source-facing item here: Theorem 9.1.3 itself;
--   - core/canonical owners: `P.toConstrainedOptimizationProblem.IsKKTPoint` and
--     `P.HasSecondOrderNecessaryCondition`;
--   - bridge/view: the Euclidean-space transport `pointEquiv`;
-- * primitive data vs derived API:
--   - primitive data already live in the Chapter 9 owner `QuadraticProgram`;
--   - the theorem surface here is derived API over that owner, so the previous duplicate local
--     quadratic-program/KKT/critical-cone packaging is deleted in favor of the canonical owner.
namespace QuadraticProgram
theorem isLocalMinOn_iff_exists_isKKTPoint_with_secondOrderNecessaryCondition
    (P : QuadraticProgram n me mi) (xStar : Point)
    (hxStar : xStar ∈ P.feasibleSet) :
    IsLocalMinOn P P.feasibleSet xStar ↔
      ∃ lamStar : Fin (me + mi) → ℝ,
        P.toConstrainedOptimizationProblem.IsKKTPoint (pointEquiv xStar) lamStar ∧
          P.HasSecondOrderNecessaryCondition xStar lamStar

Definition 9.1.extra.1

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

Source header · Attribution source

The matrix-based quadratic-program owner used for Chapter09 Definition 9.1-extra-1 (1) is determined by a symmetric matrix G, a linear term g, equality constraints Aeq x = beq, and inequality constraints Aineq x ≥ bineq. The finite index sets E = {1, ..., me} and I = {me + 1, ..., me + mi} are encoded by the row types Fin me and Fin mi.

variable {n me mi : ℕ} structure QuadraticProgram (n me mi : ℕ) where G : Matrix (Fin n) (Fin n) ℝ hG_symm : G.IsSymm g : EuclideanSpace ℝ (Fin n) Aeq : Matrix (Fin me) (Fin n) ℝ beq : EuclideanSpace ℝ (Fin me) Aineq : Matrix (Fin mi) (Fin n) ℝ bineq : EuclideanSpace ℝ (Fin mi)

9.2 — Duality for Quadratic Programming

Theorem 9.2.1

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

Source header · Attribution source

Chapter09 Theorem 9.2.1: let P encode primal problem (9.1.1)-(9.1.3) with positive-definite Hessian P.G. For a feasible point xStar ∈ X = P.feasibleSet, xStar solves the primal problem if and only if there exists a dual solution of (9.2.8)-(9.2.10) whose auxiliary vector satisfies y* = G xStar.

open Matrix
namespace QuadraticProgram
variable {n me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "EqMultiplier" => EuclideanSpace ℝ (Fin me)
local notation "IneqMultiplier" => EuclideanSpace ℝ (Fin mi)
local notation "pointEquiv" => EuclideanSpace.equiv (Fin n) ℝ

-- Domain-style sampling:
-- * primary domain: quadratic-program duality with the explicit source dual problem
-- * inspected owner declarations:
--   `ConstrainedOptimizationProblem.lagrangian`,
--   `ConstrainedOptimizationProblem.IsDualSolution`, and
--   `ConstrainedOptimizationProblem.IsDualOptimalPair` from Chapter 8,
--   together with the Chapter 9 owner `QuadraticProgram`
-- * best owner abstraction here: the source-facing Chapter 9 owner `QuadraticProgram`, while
--   the split-multiplier/Lagrangian owner surface and the positive-definite explicit dual
--   objective follow the Chapter 8 duality API shape
-- * layer triage:
--   source-facing: `Multiplier`, `Λ[P]`, `ℒ[P]`, `DualVariable`, `SatisfiesDualStationarity`,
--   and `IsDualFeasible`
--   core/canonical: `P.dualObjective hG dual` and `P.IsDualSolution hG dual`
--   bridge/view: `multiplierVector` and `dualFeasibleSet`
local notation "Multiplier" => QuadraticProgram.Multiplier me mi
open scoped QuadraticProgram
theorem primalSolution_iff_dualSolution
    (P : QuadraticProgram n me mi)
    (hG : P.G.PosDef)
    {xStar : Point}
    (hxStar : xStar ∈ P.feasibleSet) :
    IsMinOn P P.feasibleSet xStar ↔
      ∃ dualStar : DualVariable P,
        dualStar.y = P.G.mulVec xStar ∧ P.IsDualSolution hG dualStar

Theorem 9.2.2

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

Source header · Attribution source

Chapter09 Theorem 9.2.2: if G is positive definite, then the primal problem (9.1.1)-(9.1.3) is infeasible if and only if the dual problem (9.2.8)-(9.2.10) is unbounded above.

namespace QuadraticProgram
variable {n me mi : ℕ}
theorem primalInfeasible_iff_dualUnboundedAbove
    (P : QuadraticProgram n me mi) (hG : P.G.PosDef) :
    P.feasibleSet = ∅ ↔ ¬ BddAbove ((P.dualObjective hG) '' P.dualFeasibleSet)

Theorem 9.2.3

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

Source header · Attribution source

Chapter09 Theorem 9.2.3: if P.G is positive definite, then xStar ∈ X is a minimizer of the quadratic program (9.1.1)-(9.1.3) if and only if there exists a multiplier pair (λeq⋆, λineq⋆) ∈ Λ[P] such that (xStar, (λeq⋆, λineq⋆)) is a saddle point of the Lagrangian ℒ[P]; equivalently, `ℒ[P] xStar λ ≤ ℒ[P] xStar (λeq⋆, λineq⋆) ≤ ℒ[P] x (λeq⋆, λineq⋆)for allx ∈ Xandλ ∈ Λ[P]`.

namespace QuadraticProgram
variable {n me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Multiplier" => QuadraticProgram.Multiplier me mi

-- Domain sampling:
-- * primary domain: quadratic-program duality via Lagrangian saddle points
-- * inspected relevant owner declarations:
--   `ConstrainedOptimizationProblem.lagrangian` from Chapter 8,
--   `QuadraticProgram.Multiplier`, `QuadraticProgram.multiplierVector`, `Λ[P]`, and `ℒ[P]`
--   from `Theorem_9_2_1`,
--   `IsSaddlePointOn` from mathlib
-- * best owner abstractions:
--   the upstream Chapter 9 split-multiplier/Lagrangian owner surface from `Theorem_9_2_1`,
--   `IsSaddlePointOn` for the saddle-point predicate
-- * layer triage in this file:
--   source-facing: the saddle-pair predicate
--   core/canonical: the upstream Chapter 9 owners `Λ[P]`, `ℒ[P]`, and `Multiplier`
--   together with mathlib's `IsSaddlePointOn`
--   bridge/view: none beyond the upstream owner surface
-- * primitive data vs. derived API:
--   primitive source-facing data already live upstream in the Chapter 9 owner surface;
--   this file contributes only the saddle-pair predicate and its equivalence theorem, built
--   from that owner surface and mathlib's saddle-point abstraction
open scoped QuadraticProgram
theorem isMinOn_iff_exists_isSaddlePair_of_posDef
    (P : QuadraticProgram n me mi) (xStar : Point) (hG : P.G.PosDef) :
    IsMinOn P P.feasibleSet xStar ↔
      ∃ multStar : Multiplier, P.IsSaddlePair xStar multStar

9.3 — Equality-Constrained Quadratic Programming

Example 9.3.1

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

Source header · Attribution source

Chapter09 Example 9.3.1 (1): the point (-1, 3 / 2, 1 / 2)ᵀ is a global solution of the problem min Q(x) = x 0^2 - x 1^2 - x 2^2 subject to x 0 + x 1 + x 2 = 1 and x 1 - x 2 = 1.

open Matrix -- Semantic recall: Chapter 9 already provides the canonical owner -- `EqualityConstrainedQuadraticProgram` for equality-constrained quadratic programs. This example -- is therefore recorded as a concrete source-facing problem together with the solved point, -- multiplier, and textbook bridge lemmas back to the displayed formulas. local notation "Point" => EuclideanSpace ℝ (Fin 3) local notation "MultiplierPoint" => EuclideanSpace ℝ (Fin 2) local notation "ConstraintMatrix" => Matrix (Fin 3) (Fin 2) ℝ theorem chapter09Example931_isMinOn : IsMinOn chapter09Example931Problem chapter09Example931Problem.feasibleSet chapter09Example931Solution

Theorem 9.3.2

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

Source header · Attribution source

Chapter09 Theorem 9.3.2 (1): if A has full column rank, Z spans ker Aᵀ, and the reduced Hessian Zᵀ G Z is positive definite, then the KKT matrix kktMatrix G A is nonsingular.

open Matrix variable {n m k : ℕ} local notation "PrimalPoint" => Fin n → ℝ local notation "DualPoint" => Fin m → ℝ local notation "ReducedPoint" => Fin k → ℝ local notation "HessianMatrix" => Matrix (Fin n) (Fin n) ℝ local notation "ConstraintMatrix" => Matrix (Fin n) (Fin m) ℝ local notation "ReducedBasisMatrix" => Matrix (Fin n) (Fin k) ℝ theorem kktMatrix_isUnit_of_reducedHessian_posDef (G : HessianMatrix) (A : ConstraintMatrix) (Z : ReducedBasisMatrix) (hA : Function.Injective A.mulVec) (hZ : IsReducedNullMatrix A Z) (hReduced : (Z.transpose * G * Z).PosDef) : IsUnit (kktMatrix G A)

Problem 9.3.extra.1

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

Source header · Attribution source

Chapter09 Problem 9.3-extra-1: an equality-constrained quadratic programming problem on ℝ^n is specified by vectors g : ℝ^n and b : ℝ^m, a matrix A = [a₁, ..., a_m] : ℝ^(n × m), and a symmetric matrix G : ℝ^(n × n). The textbook's full-column-rank assumption Matrix.rank A = m is recorded separately as problem.HasFullColumnRank, since it is not primitive data for the canonical Chapter 9 bridge.

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

-- Domain-style sampling in Chapter 9:
-- * source-facing layer here: equality-constrained quadratic programs with the column-oriented
--   matrix presentation `A = [a₁, ..., a_m]`.
-- * core/canonical owner upstream: `QuadraticProgram n me mi` from
--   `Definition_9_1_extra_1`, together with `QuadraticProgram.objective_eq` and
--   `QuadraticProgram.mem_feasibleSet_iff`.
-- * bridge/view used here: `toQuadraticProgram`, specializing the canonical owner to `mi = 0`
--   and replacing the source constraint `Aᵀ x = b` by the owner's equality block
--   `Aeq.mulVec x = beq` with `Aeq = Aᵀ`.
--
-- Primitive data in this file are therefore only the source vectors and matrices; the
-- full-column-rank hypothesis from the textbook is a separate property, while the objective and
-- feasible-set APIs are derived from the Chapter 9 owner.
structure EqualityConstrainedQuadraticProgram (n m : ℕ) where
  g : EuclideanSpace ℝ (Fin n)
  G : Matrix (Fin n) (Fin n) ℝ
  A : Matrix (Fin n) (Fin m) ℝ
  b : EuclideanSpace ℝ (Fin m)
  hG_symm : G.IsSymm

9.4 — Active Set Methods

Lemma 9.4.1

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

Source header · Attribution source

Chapter09 Lemma 9.4.1 (2): if xStar is feasible for P, if mult satisfies the active-set equality-constrained KKT system at xStar, and if the active inequality multipliers are nonnegative, then (mult.1, mult.2) is a Chapter 8 KKT multiplier pair for the original quadratic program.

variable {n me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "EqMultiplier" => EuclideanSpace ℝ (Fin me)
local notation "IneqMultiplier" => EuclideanSpace ℝ (Fin mi)
local notation "Multiplier" => EqMultiplier × IneqMultiplier
local notation "pointEquiv" => EuclideanSpace.equiv (Fin n) ℝ
open scoped BigOperators Gradient

-- Domain sampling:
-- * primary domain: quadratic-program active-set reduction and KKT transfer;
-- * inspected owner declarations:
--   `QuadraticProgram` from `Definition_9_1_extra_1`,
--   `QuadraticProgram.activeSet` from `Algorithm_9_4_2`,
--   `ConstrainedOptimizationProblem.IsKKTPoint` from `Chapter08.Theorem_8_2_7`,
--   and `IsLocalMinOn.on_subset` from mathlib;
-- * best owner abstraction: the Chapter 9 quadratic-program owner together with the canonical
--   Chapter 8 KKT owner on `P.toConstrainedOptimizationProblem`;
-- * source/core/bridge triage:
--   - source-facing layer here: the active-set feasible system and Lemma 9.4.1 itself;
--   - core/canonical layer: `P.toConstrainedOptimizationProblem.IsKKTPoint`;
--   - bridge/view: `P.activeSet xStar` and `pointEquiv`;
-- * primitive data vs derived API:
--   - primitive data already live in `QuadraticProgram`;
--   - the active-set equality system and its KKT transfer are derived API over that owner.
namespace QuadraticProgram
theorem isKKTPoint_of_feasible_of_satisfiesActiveSetKKT
    (P : QuadraticProgram n me mi) (xStar : Point) (mult : Multiplier)
    (hFeasible : xStar ∈ P.feasibleSet)
    (hActiveKKT : P.SatisfiesActiveSetKKT xStar mult)
    (hActiveDualNonneg : ∀ i, i ∈ P.activeSet xStar → 0 ≤ mult.2 i) :
    P.toConstrainedOptimizationProblem.IsKKTPoint
      (pointEquiv xStar)
      (Fin.append mult.1 mult.2)

Algorithm 9.4.2

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

Source header · Attribution source

Chapter09 Algorithm 9.4.2: an active-set method for the quadratic program P starts from an initial point x1, stores the source working set S₁ = E ∪ I(x₁) as the inequality part workingSet 0 = P.activeSet x1, and records the Step-2 and Step-3 update rules stage by stage. Here x 0 corresponds to the source iterate x₁, and the initial-feasibility fact x1 ∈ P.feasibleSet is recovered from feasible 0 together with x_initial rather than stored as separate data. For every stage k, direction k solves the equality-based working-set subproblem. If direction k = 0, then Step 2 either satisfies the stopping test that all working-set inequality multipliers are nonnegative or removes the working inequality selected by (9.4.18) without changing the iterate. If direction k ≠ 0, then Step 3 uses a maximal feasible step size, updates x (k + 1) = x k + stepSize k • direction k, keeps the working set unchanged for a full step, and adds a newly active inequality for a partial step.

open Matrix variable {n me mi : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) local notation "EqMultiplier" => EuclideanSpace ℝ (Fin me) local notation "IneqMultiplier" => EuclideanSpace ℝ (Fin mi) -- This file reuses the Chapter 9 quadratic-program owner from -- `Definition_9_1_extra_1` and adds the source-facing Algorithm 9.4.2 working-set API. namespace QuadraticProgram structure ActiveSetMethod (P : QuadraticProgram n me mi) (x1 : Point) where x : ℕ → Point workingSet : ℕ → Finset (Fin mi) direction : ℕ → Point stepSize : ℕ → ℝ eqMultiplier : ℕ → EqMultiplier ineqMultiplier : ℕ → IneqMultiplier enteringIndex : ℕ → Fin mi leavingIndex : ℕ → Fin mi x_initial : x 0 = x1 workingSet_initial : workingSet 0 = P.activeSet x1 feasible : ∀ k : ℕ, x k ∈ P.feasibleSet subproblem_solution : ∀ k : ℕ, P.solvesWorkingSetSubproblem (x k) (workingSet k) (direction k) zeroDirection_stationarity : ∀ k : ℕ, direction k = 0 → P.G.mulVec (x k) + P.g = P.Aeqᵀ *ᵥ eqMultiplier k + P.Aineqᵀ *ᵥ ineqMultiplier k zeroDirection_inactiveMultiplier : ∀ k : ℕ, direction k = 0 → ∀ i : Fin mi, i ∉ workingSet k → ineqMultiplier k i = 0 zeroDirection_branch : ∀ k : ℕ, direction k = 0 → (∀ i : Fin mi, i ∈ workingSet k → 0 ≤ ineqMultiplier k i) ∨ ZeroDirectionDropState (workingSet k) (workingSet (k + 1)) (x k) (x (k + 1)) (ineqMultiplier k) (leavingIndex k) nonzeroDirection_stepSize : ∀ k : ℕ, direction k ≠ 0 → P.isActiveSetStepSize (x k) (direction k) (stepSize k) nonzeroDirection_update : ∀ k : ℕ, direction k ≠ 0 → x (k + 1) = x k + stepSize k • direction k fullStep_workingSet : ∀ k : ℕ, direction k ≠ 0 → stepSize k = 1 → workingSet (k + 1) = workingSet k partialStep_entersConstraint : ∀ k : ℕ, direction k ≠ 0 → stepSize k < 1 → PartialStepConstraintEntry P (workingSet k) (workingSet (k + 1)) (x (k + 1)) (enteringIndex k)

Lemma 9.4.3

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

Source header · Attribution source

Chapter09 Lemma 9.4.3: let k₀ satisfy (9.4.30). If k₂ > k₁ > k₀ satisfy the source conditions (9.4.35)-(9.4.37), then 𝒮_{k₂} ≠ 𝒮_{k₁}. This is the source conclusion (9.4.38).

variable {n me mi : ℕ} local notation "Point" => EuclideanSpace ℝ (Fin n) namespace QuadraticProgram theorem ActiveSetMethod.sourceWorkingSet_ne_of_eventuallyConstant_of_drop_then_nonzeroDirection {P : QuadraticProgram n me mi} {x1 : Point} (A : ActiveSetMethod P x1) {k₀ k₁ k₂ : ℕ} (hk₀₁ : k₀ < k₁) (hk₁₂ : k₁ < k₂) (h9430 : A.satisfies9430 k₀) (h9435 : A.satisfies9435 k₁) (h9436 : A.satisfies9436 k₁) (h9437 : A.satisfies9437 k₁ k₂) : A.sourceWorkingSet k₂ ≠ A.sourceWorkingSet k₁

Theorem 9.4.4

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

Source header · Attribution source

Chapter09 Theorem 9.4.4 in canonical owner form: if the Chapter 8 LICQ condition holds at every iterate x_k generated by Algorithm 9.4.2, then either some stage k is a terminating stage and the corresponding iterate is a KKT point of P, or the quadratic program is unbounded below on its feasible set.

variable {n me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "pointEquiv" => EuclideanSpace.equiv (Fin n) ℝ

-- Domain-style sampling:
-- * primary domain: quadratic programming, active-set methods, LICQ, and KKT points
-- * inspected owner declarations:
--   `ConstrainedOptimizationProblem.LicqAt` from `Chapter08.Definition_8_2_10`
--   `QuadraticProgram.toConstrainedOptimizationProblem_hasConstraintGradientsAt`
--   from `Chapter09.Theorem_9_1_1`
--   `ConstrainedOptimizationProblem.IsKKTPoint` from `Chapter08.Theorem_8_2_7`
--   `QuadraticProgram.multiplierVector` from `Chapter09.Theorem_9_2_1`
--   the Chapter 9 bridge `QuadraticProgram.toConstrainedOptimizationProblem`
-- * best owner abstractions:
--   `P.toConstrainedOptimizationProblem.LicqAt` is the canonical Chapter 8 owner for the LICQ
--   hypothesis, while the active-gradient `LinearIndepOn` condition is a source-facing bridge to
--   that owner, and `P.toConstrainedOptimizationProblem.IsKKTPoint` remains the KKT conclusion
--   owner
-- * source/core/bridge triage:
--   source-facing: `ActiveSetMethod.terminatedAt` and Theorem 9.4.4 itself
--   core/canonical: `LicqAt`, `LinearIndepOn`, and `IsKKTPoint`
--   bridge/view: `P.toConstrainedOptimizationProblem`, `pointEquiv`, and `multiplierVector`
-- * primitive data vs. derived API:
--   primitive data are the active-set method iterates and stagewise multiplier data already stored
--   by `ActiveSetMethod`; the QP-side differentiability facts are derived from the affine
--   constraint bridge, and the KKT conclusion is derived API on top of the canonical owner
namespace QuadraticProgram
theorem activeSetMethod_finiteKKT_or_unboundedBelow_of_licqAt
    (P : QuadraticProgram n me mi) {x1 : Point} (A : ActiveSetMethod P x1)
    (hlicq : ∀ k : ℕ, P.toConstrainedOptimizationProblem.LicqAt (pointEquiv (A k))) :
    (∃ k : ℕ,
      A.terminatedAt k ∧
        P.toConstrainedOptimizationProblem.IsKKTPoint
          (pointEquiv (A k))
          (multiplierVector (A.eqMultiplier k, A.ineqMultiplier k))) ∨
      ¬ BddBelow (P.objective '' P.feasibleSet)

9.5 — Dual Method

Algorithm 9.5.1

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

Source header · Attribution source

Chapter09 Algorithm 9.5.1: the dual method as a one-step transition relation on control states. entering = none records the Step-2 state before an entering constraint is chosen, while entering = some p records that the Step-3/4/7 loop continues with the fixed source choice p. IsDualMethodStep P none (some s) is the Step-1 initialization into Step 2. A Step-2 state may either stop, or choose an entering constraint without changing the stage data. A continuation state with remembered p may either stop infeasibly, continue the Step-4/7 drop or Step-5/7 short-step loop with the same p, or take the Step-5/6 full step and return to Step 2 at the next stage.

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

-- Semantic search note: `lean_leansearch` surfaced only unrelated simplex/linear-programming
-- infrastructure, not a ready-made owner for the Sun-Yuan dual method. Nearby Chapter 9
-- precedent therefore favors reusing the canonical inequality-only owner
-- `QuadraticProgram n 0 m` together with explicit inverse-Hessian data, while keeping the
-- algorithm-run structures for the iterate, active-set, and multiplier data.
def IsDualMethodStep
    (P : DualMethodProblem n m)
    (source target : Option (DualMethodControlState n m)) : Prop :=
  match source, target with
  | none, some s =>
      DualMethodInitControlStep P s
  | some s, none =>
      DualMethodStopControlStep P s ∨
        DualMethodInfeasibleControlStep P s
  | some s, some t =>
      DualMethodSelectControlStep P s t ∨
        DualMethodDropControlStep P s t ∨
        DualMethodShortControlStep P s t ∨
        DualMethodFullControlStep P s t
  | none, none => False

Example 9.5.2

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

Source header · Attribution source

Chapter09 Example 9.5.2 (1): Algorithm 9.5.1 initializes the example at x₁ = -G⁻¹ g = (0, 3, 1)ᵀ with empty working set, zero multiplier, Ĝ₁ = G⁻¹, and A₁^* = 0.

open Matrix
local notation "Point" => EuclideanSpace ℝ (Fin 3)
local notation "Multiplier" => EuclideanSpace ℝ (Fin 2)
local notation "Matrix3" => Matrix (Fin 3) (Fin 3) ℝ
local notation "ConstraintMatrix" => Matrix (Fin 2) (Fin 3) ℝ
theorem chapter09Example952_initStep :
    DualMethodInitControlStep
      chapter09Example952Problem
      chapter09Example952InitialControlState

9.6 — Interior Ellipsoid Method

Algorithm 9.6.1

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

Source header · Attribution source

Chapter09 Algorithm 9.6.1: an interior ellipsoid method for the quadratic program P records that P is convex, starts from a strict interior point x1 of (9.6.3)-(9.6.5) with iterate 0 = x1, and stores the Step-2 subproblem data together with the exact iterate update formula (9.6.35) and the Step-3 KKT stop/continue rule.

open Matrix
variable {n me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "pointEquiv" => EuclideanSpace.equiv (Fin n) ℝ
open scoped BigOperators

-- Domain-style sampling in Chapter 9:
-- * primary domain: quadratic programming with the Chapter 8 constrained-problem/KKT owner
--   available through `QuadraticProgram.toConstrainedOptimizationProblem`;
-- * inspected owner declarations: `QuadraticProgram.toConstrainedOptimizationProblem` from
--   `Definition_9_1_extra_1`, `ConstrainedOptimizationProblem.IsKKTPoint` from
--   `Theorem_8_2_7`, `QuadraticProgram.activeSet` / `workingSetFeasibleDirections` from
--   `Algorithm_9_4_2`, and the Chapter 9 second-order/KKT bridge usage in `Theorem_9_1_1`;
-- * best owner abstraction: the canonical KKT predicate lives on
--   `P.toConstrainedOptimizationProblem`, so this file should transport iterates to that owner
--   rather than declare another quadratic-program-level KKT predicate. Within the source-facing
--   Step-2 layer, the strict interior region should be owned by a set-valued declaration, with
--   pointwise predicates and subproblem certificates derived from that owner;
-- * primitive data vs. derived API: the primitive source-facing data here are the strict
--   interior set, the barrier objective, the Step-2 datum `xHat`, and the iterate/scaling data.
--   Pointwise strict interiority, the Step-2 subproblem predicate, and the Step-3 stopping test
--   are derived logical API.
open QuadraticProgram (InteriorEllipsoidSubproblemPoint)
structure InteriorEllipsoidMethod (P : QuadraticProgram n me mi) where
  convex : P.G.PosSemidef
  x1 : Point
  active : ℕ → Prop
  iterate : ℕ → Point
  muHat : ℕ → ℝ
  xHat : ℕ → InteriorEllipsoidSubproblemPoint n
  scalingMatrix : ℕ → Matrix (Fin n) (Fin n) ℝ
  active_zero : active 0
  iterate_zero : iterate 0 = x1
  x1_strictInterior : P.IsStrictInteriorPoint x1
  subproblem_solution :
    ∀ k : ℕ, active k → P.SolvesInteriorEllipsoidSubproblem (muHat k) (xHat k)
  iterate_succ :
    ∀ k : ℕ, active k →
      iterate (k + 1) = interiorEllipsoidUpdate (scalingMatrix k) (xHat k)
  active_succ_iff :
    ∀ k : ℕ,
      active (k + 1) ↔
        active k ∧
          ¬ ∃ lamStar : Fin (me + mi) → ℝ,
            P.toConstrainedOptimizationProblem.IsKKTPoint
              (pointEquiv (iterate (k + 1))) lamStar

9.7 — Primal-Dual Interior-Point Methods

Algorithm 9.7.1

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

Source header · Attribution source

Chapter09 Algorithm 9.7.1: a primal-dual interior-point framework for the linear data (A, b, c). The sequence state k represents (xᵏ, λᵏ, sᵏ), direction k represents (Δxᵏ, Δλᵏ, Δsᵏ), sigma k ∈ [0, 1] is the centering parameter σ_k, and μ_k = (state k).xᵀ (state k).s / n is attached definitionally to the current state. The initial state lies in 𝓕ᵒ, each direction solves the Newton system with right-hand side -Xᵏ Sᵏ e + σ_k μ_k e, and the next iterate is updated by (xᵏ⁺¹, λᵏ⁺¹, sᵏ⁺¹) = (xᵏ, λᵏ, sᵏ) + α_k (Δxᵏ, Δλᵏ, Δsᵏ) with xᵏ⁺¹ and sᵏ⁺¹ remaining strictly positive.

variable {n m : ℕ}
local notation "PrimalPoint" => EuclideanSpace ℝ (Fin n)
local notation "DualPoint" => EuclideanSpace ℝ (Fin m)
local notation "ConstraintMatrix" => Matrix (Fin m) (Fin n) ℝ

-- Semantic recall: `lean_leansearch` surfaced only unrelated positivity/cone infrastructure,
-- not a reusable mathlib owner for this primal-dual interior-point framework. Following nearby
-- Chapter 9 precedent, this file therefore keeps the LP data and iteration rules explicit.
structure PrimalDualInteriorPointFramework
    (A : ConstraintMatrix) (b : DualPoint) (c : PrimalPoint) where
  state : ℕ → PrimalDualState n m
  direction : ℕ → PrimalDualDirection n m
  sigma : ℕ → ℝ
  alpha : ℕ → ℝ
  initial_mem : state 0 ∈ strictlyFeasibleSet A b c
  sigma_mem_Icc : ∀ k : ℕ, sigma k ∈ Set.Icc (0 : ℝ) 1
  newton_system :
    ∀ k : ℕ, solvesPrimalDualNewtonSystem A (state k) (sigma k) (direction k)
  update :
    ∀ k : ℕ, state (k + 1) = (state k).updated (alpha k) (direction k)
  next_strictPos :
    ∀ k : ℕ,
      IsStrictlyPositive (state (k + 1)).x ∧
        IsStrictlyPositive (state (k + 1)).s

Definition 9.7.extra.1

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

Source header · Attribution source

A triple (x, λ, s) is a τ-central-path point when it satisfies the affine primal-dual equations together with the coordinatewise complementarity condition x i * s i = τ and strict positivity of x and s.

open Matrix
variable {n m : ℕ}
local notation "PrimalPoint" => EuclideanSpace ℝ (Fin n)
local notation "DualPoint" => EuclideanSpace ℝ (Fin m)
local notation "ConstraintMatrix" => Matrix (Fin m) (Fin n) ℝ
def IsCentralPathPoint
    (A : ConstraintMatrix) (b : DualPoint) (c : PrimalPoint) (τ : ℝ)
    (point : PrimalDualState n m) : Prop :=
  point ∈ strictlyFeasibleSet A b c ∧
    ∀ i, point.x i * point.s i = τ

Definition 9.7.extra.2

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

Source header · Attribution source

A central-path state (x, y, λ) for the residual-map formulation of Definition 9.7-extra-2.

variable {n m : ℕ}
local notation "PrimalPoint" => EuclideanSpace ℝ (Fin n)
local notation "DualPoint" => EuclideanSpace ℝ (Fin m)
structure CentralPathState (n m : ℕ) where
  x : EuclideanSpace ℝ (Fin n)
  y : EuclideanSpace ℝ (Fin m)
  lam : EuclideanSpace ℝ (Fin m)