Appendix A, p. 20 — for an M-matrix, yᵏ⁺¹ ≤ yᵏ for every k ≥ 1
ProvedPDASNewton.MMatrix.y_antitoneactive-setm-matrixmonotonicityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an M-matrix, , , and let be a run of the primal-dual active set algorithm from arbitrary initial data. Then
componentwise.
Monotonicity of the primal iterates is the first half of the global convergence argument of Theorem 3.2.
Formalization Note The inequality is not claimed for : can fail.
Preamble
import Mathlib import Definitions.Def_PDASNewton_MMatrix_Setting open Filter Topology Matrix
Formal statement
namespace PDASNewton.MMatrix
theorem y_antitone {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (f ψ : Fin n → ℝ) (c : ℝ)
(hc : 0 < c) (hA : IsMMatrix A) (y lam : ℕ → Fin n → ℝ) (hrun : PDASNewton.Local.IsRun A f ψ c y lam) :
∀ k, 1 ≤ k → y (k + 1) ≤ y k := by sorry
end PDASNewton.MMatrix
Source
Hintermüller, Ito, Kunisch, The primal-dual active set strategy as a semismooth Newton method, HAL hal-01660511v1, p. 20, Appendix A, proof of Theorem 3.2, first paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.