Theorem A.4, p. 60 — 0 ∈ Ax + a + ∂ψ_C(x), C polyhedral, is strongly regular at x₀ iff its reduced form is vacuous or uniquely solvable on all of L
ProvedRobinsonSR.Reduction.theorem_A_4Let be a nonempty polyhedral convex set in , let be a real matrix and , and suppose solves
Put , let be the face of on which is maximal (it contains ), let be the tangent cone to at , the subspace parallel to , and the orthogonal projector on . The reduced form of (A.1) at is the inclusion
Then (A.1) is strongly regular at (for some Lipschitz constant ) if and only if its reduced form
- is vacuous, that is, ; or
- has an inverse which is single-valued on all of : for every there is exactly one with .
This is the paper's general criterion for strong regularity of a linear generalized equation over a polyhedral set: it reduces the question to unique solvability of a homogeneous problem on a cone, which Theorem 3.1 then settles for in terms of a Schur complement (Corollary 3.2).
Formalization Note The paper writes the reduced form in an orthonormal basis adapted to (the lineality space of ), and , as (A.3, A.5); the statement here is the coordinate-free form (A.4) on itself. Since , every solution lies in , and , so the component of the inclusion is automatic. Disjunct (i) is a special case of (ii) (for the unique solution is ); both are kept as printed. "Strongly regular" without a constant is . Nonemptiness of is the appendix's standing assumption and is implied by .
import Mathlib import Definitions.Def_RobinsonSR_Reduction_Setting open scoped Topology RealInnerProductSpace
namespace RobinsonSR.Reduction
/-- Theorem A.4 (Robinson 1980, p. 60). Let `C` be a (nonempty) polyhedral convex set in `ℝⁿ`,
`A` an `n × n` matrix and `a ∈ ℝⁿ`, and let `x₀` solve `0 ∈ A x + a + ∂ψ_C(x)` (A.1). With
`y₀ := A x₀ + a`, `F := ∂ψ*_C(-y₀)`, `T := T_F(x₀)` and `L` the subspace parallel to `F`,
(A.1) is strongly regular at `x₀` if and only if its reduced form (i) is vacuous (`L = {0}`), or
(ii) has an inverse which is single-valued on all of `L`: for every `z ∈ L` there is exactly one
`w` with `z ∈ P_L A w + ∂ψ_T(w)`. -/
theorem theorem_A_4 {n : ℕ} (C : Set (EuclideanSpace ℝ (Fin n))) (hCp : IsPolyhedral C)
(hCne : C.Nonempty) (A : Matrix (Fin n) (Fin n) ℝ) (a x0 : EuclideanSpace ℝ (Fin n))
(hsol : -(Matrix.toEuclideanLin A x0 + a) ∈ normalCone C x0) :
let y0 := Matrix.toEuclideanLin A x0 + a
let F := exposedFace C y0
let T := tangentCone F x0
let L := parallelSubspace F
(∃ lam : ℝ, StronglyRegularLin C A a x0 lam) ↔
(L = ⊥ ∨ ∀ z ∈ L, ∃! w : EuclideanSpace ℝ (Fin n),
z - L.starProjection (Matrix.toEuclideanLin A w) ∈ normalCone T w) := by sorry
end RobinsonSR.Reduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.