LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The convex normal-cone operator is maximal monotone and its resolvent is projection

Statement

Let $C \subseteq R^{d}$ be nonempty, closed, and convex, and let $N_{C}$ have the convention of Projected contact dynamics and explicit projection Euler step. In dimension $d = 0$ , interpret this convention directly as $C = R^{0} = {0}$ , $N_{C} (0) = {0}$ , and $P_{C} (0) = 0$ . An operator $A : R^{d} ⇉ R^{d}$ is monotone if $⟨ u - v, x - y ⟩ \geq 0$ for all $u \in A (x)$ and $v \in A (y)$ ; it is maximal monotone if its graph has no proper monotone graph extension. Then $N_{C}$ is maximal monotone. For every $τ > 0$ and $y \in R^{d}$ , there is a unique $p$ with $y - p \in τ N_{C} (p)$ , and that point is $P_{C} (y)$ . Equivalently, $(I + τ N_{C})^{- 1} = P_{C}$ .

Facts & Assumptions

Given: The set $C$ and normal-cone convention in the Statement, and a scalar $τ > 0$ .

[F1]

Scaled KKT residual and convex normal cone and Projected contact dynamics and explicit projection Euler step: for $x \in C$ , $N_{C} (x) = {n : ⟨ n, z - x ⟩ \leq 0 for every z \in C}$ ; outside $C$ , the operator is empty.

[F2]

Extended-real indicator of a set: $ι_{C}$ is $0$ on $C$ and $+ \infty$ outside $C$ .

[F3]

Subdifferentials of proper extended-real convex functions: for proper convex $g$ and $x \in dom g$ , $p \in \partial g (x)$ means $g (z) \geq g (x) + ⟨ p, z - x ⟩$ for every $z$ ; if $x \notin dom g$ , then $\partial g (x) = \emptyset$ .

[F4]

Existence, resolvent characterization, and firm nonexpansiveness of the proximal map: for proper closed convex $g$ and $τ > 0$ , $u = {prox}_{τ g} (y)$ iff $(y - u) / τ \in \partial g (u)$ .

[F5]

The proximal map of an indicator is Euclidean projection: the indicator of this nonempty closed convex set is proper, closed, and convex, and ${prox}_{τ ι_{C}} (y) = P_{C} (y)$ , the unique nearest point.

Proof

1.1F1givenalgebra

Let $n \in N_{C} (x)$ and $m \in N_{C} (y)$ . Testing the definition in [F1] with $z = y$ and $z = x$ gives $⟨ n, y - x ⟩ \leq 0$ and $⟨ m, x - y ⟩ \leq 0$ . Adding and changing signs yields $⟨ n - m, x - y ⟩ \geq 0$ . Thus $N_{C}$ is monotone.

1.2F1F2F3F5given

The indicator is proper, closed, and convex by [F5], and its domain is $C$ by [F2]. At $x \in C$ , [F2]–[F3] show $p \in \partial ι_{C} (x)$ exactly when $⟨ p, z - x ⟩ \leq 0$ for every $z \in C$ ; inequalities for $z \notin C$ are automatic because $ι_{C} (z) = + \infty$ . At $x \notin C$ , both $\partial ι_{C} (x)$ and $N_{C} (x)$ are empty. Hence $\partial ι_{C} = N_{C}$ .

2.1F4F5step 1.1step 1.2givenalgebra

Given any $y \in R^{d}$ , put $p = P_{C} (y) = {prox}_{τ ι_{C}} (y)$ by [F5]. By [F4] and step 1.2, $(y - p) / τ \in N_{C} (p)$ , so $y - p \in τ N_{C} (p)$ . If also $y - q \in τ N_{C} (q)$ , monotonicity [step 1.1] gives $0 \leq ⟨ (y - p - y + q) / τ, p - q ⟩ = - ∥ p - q ∥_{2}^{2} / τ$ , hence $p = q$ . Therefore the resolvent exists uniquely at every $y$ and equals $P_{C}$ .

3.1step 2.1givenalgebra∎

Suppose $(x, v)$ is monotonically related to the graph of $N_{C}$ , so $⟨ v - n, x - y ⟩ \geq 0$ for every $n \in N_{C} (y)$ . Apply step 2.1 to $x + τ v$ to obtain $p$ and $n = (x + τ v - p) / τ \in N_{C} (p)$ . Then $x - p = τ (n - v)$ , and the relation gives $0 \leq ⟨ v - n, x - p ⟩ = - τ ∥ v - n ∥_{2}^{2}$ . Thus $v = n$ and $x = p$ , so $(x, v)$ already lies in the graph. Every monotone extension adds no point; $N_{C}$ is maximal monotone.

Depends on

Used by

Dependency tree · two levels

38 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

David E. Stewart, Dynamics with Inequalities: Impacts and Hard Constraints (standard reference, not scraped)
Dimitri P. Bertsekas, 6.253 Convex Analysis and Optimization, Complete Lecture Notes (standard reference, not scraped)