Theorem 3.2, p. 7 — for an M-matrix, xᵏ → x* from arbitrary initial data, y* ≤ yᵏ⁺¹ ≤ yᵏ (k ≥ 1), yᵏ ≤ ψ (k ≥ 2)
ProvedPDASNewton.MMatrix.theorem_3_2Let be an M-matrix (nonsingular, for , ), let and , and let be the solution of the complementarity problem (3.1),
Let be the iterates of the primal-dual active set algorithm: with and its complement, solves , on , on . Then, for arbitrary initial data ,
This is the global convergence and monotonicity theorem of the paper: for M-matrices the primal-dual active set strategy (equivalently, the semismooth Newton method) converges from any starting point, with monotonically decreasing, feasible primal iterates.
Formalization Note The solution is a hypothesis; for an M-matrix it exists and is unique (Berman–Plemmons). Convergence is in the product topology of . The paper's matrix is written and the active set ; in Lean the active set is activeSet. The algorithm's stopping option is not modelled; that a run exists from every initial pair is the separate item run_exists.
import Mathlib import Definitions.Def_PDASNewton_MMatrix_Setting open Filter Topology Matrix
namespace PDASNewton.MMatrix
theorem theorem_3_2 {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (f ψ : Fin n → ℝ) (c : ℝ)
(hc : 0 < c) (hA : IsMMatrix A) (ystar lamstar : Fin n → ℝ)
(hsol : PDASNewton.Local.IsSolution A f ψ c ystar lamstar) (y lam : ℕ → Fin n → ℝ)
(hrun : PDASNewton.Local.IsRun A f ψ c y lam) :
Tendsto (fun k => (y k, lam k)) atTop (𝓝 (ystar, lamstar)) ∧
(∀ k, 1 ≤ k → ystar ≤ y (k + 1) ∧ y (k + 1) ≤ y k) ∧
(∀ k, 2 ≤ k → y k ≤ ψ) := by sorry
end PDASNewton.MMatrix
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.