Chapter 09 — Quadratic Programming
Proofs omitted. Hover over highlighted terms to see their Lean types.
Exercise 9.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
Chapter09 Exercise 9.4 (1): the explicit dual problem max chapter09Exercise94DualObjective λ subject to λ ∈ chapter09Exercise94DualFeasibleSet is solved by chapter09Exercise94DualOptimizer = 1.
theorem chapter09Exercise94DualIsMaxOn :
IsMaxOn
chapter09Exercise94DualObjective
chapter09Exercise94DualFeasibleSet
chapter09Exercise94DualOptimizerExercise 9.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
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
chapter09Exercise96PrimalOptimizerExercise 9.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
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.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
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
chapter09Example931SolutionTheorem 9.3.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
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)