Appendix A, (A.1), p. 20 — for k ≥ 1, λᵏᵢ = 0 or yᵏᵢ = ψᵢ for all i
ProvedPDASNewton.MMatrix.complementarity_A1active-setcomplementarityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , , and let be any run of the primal-dual active set algorithm from arbitrary initial data. Then for every and every index ,
This is the complementarity property (A.1) on which the whole proof of Theorem 3.2 rests: after one iteration, every coordinate is either dual-free or primal-active.
Formalization Note No hypothesis on or on is needed and none is assumed. The bound is essential, since is arbitrary.
Preamble
import Mathlib import Definitions.Def_PDASNewton_MMatrix_Setting open Filter Topology Matrix
Formal statement
namespace PDASNewton.MMatrix
theorem complementarity_A1 {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (f ψ : Fin n → ℝ) (c : ℝ)
(y lam : ℕ → Fin n → ℝ) (hrun : PDASNewton.Local.IsRun A f ψ c y lam) :
∀ k, 1 ≤ k → ∀ i, lam k i = 0 ∨ y k i = ψ i := 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, (A.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.