TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

Projected-gradient fixed points are normal-cone certificates

Statement

Let $n \in N$ , let $p, m \in N$ (zero allowed), and take $A \in R^{p \times n}$ , $b \in R^{p}$ , $G \in R^{m \times n}$ , and $d \in R^{m}$ . Let $C = {x \in R^{n} : A x = b, G x \leq d}$ be nonempty and let $f : R^{n} \to R$ be convex and continuously differentiable with $L$ -Lipschitz gradient, $L > 0$ . For $x \in C$ , the projected-gradient mapping of Proximal-gradient mapping and projected-gradient mapping satisfies $G_{L}^{C} (x) = 0 ⟺ - \nabla f (x) \in N_{C} (x),$ where $N_{C}$ has the outward convention of Scaled KKT residual and convex normal cone. If a feasible tuple $(x_{*}, ν, λ)$ satisfies $λ \geq 0$ , $\nabla f (x_{*}) + A^{T} ν + G^{T} λ = 0$ , and $λ_{i} ((G x_{*} - d)_{i}) = 0$ for every inequality, then $x_{*}$ is such a fixed point and is a global minimizer over $C$ . The converse to this KKT-multiplier implication is not asserted.

Facts & Assumptions

Given: The polyhedron, differentiable convex objective and, in the second claim, the feasible KKT tuple.

[F1]

The proximal map of an indicator is Euclidean projection: ${prox}_{t ι_{C}}$ equals the unique Euclidean projection $P_{C}$ .

[F2]

Metric projection onto a closed convex set satisfies the variational inequality: if $p = P_{C} (v)$ , then $⟨ v - p, z - p ⟩ \leq 0$ for all $z \in C$ .

[F3]

Scaled KKT residual and convex normal cone: $N_{C} (x) = {w : ⟨ w, z - x ⟩ \leq 0 for all z \in C}$ .

[F4]

Convex KKT conditions certify a global minimum and an outward normal: when $n \geq 1$ , for a differentiable convex objective on an open convex set, affine equalities and differentiable convex inequalities, a feasible KKT tuple with nonnegative inequality multipliers implies global minimality and $- \nabla f (x_{*}) \in N_{C} (x_{*})$ .

[F5]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : $R^{0}$ consists of its unique zero vector, and its inner product and norm vanish.

[A1]

The displayed $C$ is closed and convex as the intersection of affine equality sets and affine closed half-spaces; it is nonempty by hypothesis.

Proof

1.1A1F3F5givenalgebra

If $n = 0$ , then $R^{0} = {0}$ by [F5], and nonempty $C$ is ${0}$ . Its projection fixes $0$ , so $G_{L}^{C} (0) = 0$ ; also $N_{C} (0) = {0}$ and $\nabla f (0) = 0$ . Thus the fixed-point/normal-cone equivalence holds.

1.2A1F1F2F3givenalgebra

Now assume $n \geq 1$ . Fix $x \in C$ and put $v = x - \nabla f (x) / L$ . By [F1], $T_{L}^{C} (x) = P_{C} (v)$ . If $G_{L}^{C} (x) = 0$ , then $x = P_{C} (v)$ , so [F2] gives $⟨ - \nabla f (x) / L, z - x ⟩ \leq 0$ for every $z \in C$ . Since $L > 0$ , this is exactly $- \nabla f (x) \in N_{C} (x)$ by [F3].

1.3A1F1F3givenalgebra

Conversely suppose $n \geq 1$ and $- \nabla f (x) \in N_{C} (x)$ . Then $⟨ x - v, z - x ⟩ = ⟨ \nabla f (x) / L, z - x ⟩ \geq 0$ for every $z \in C$ . Expanding gives $∥ z - v ∥_{2}^{2} = ∥ z - x ∥_{2}^{2} + ∥ x - v ∥_{2}^{2} + 2 ⟨ x - v, z - x ⟩ \geq ∥ x - v ∥_{2}^{2} .$ Thus $x$ is the nearest point in $C$ to $v$ ; uniqueness of projection gives $x = P_{C} (v) = T_{L}^{C} (x)$ , so $G_{L}^{C} (x) = 0$ .

2.1F3F4step 1.1step 1.3given∎

If $n = 0$ , nonempty $C = R^{0} = {0}$ , so every feasible $x_{*}$ is the global minimizer and is the projected-gradient fixed point by step 1.1. If $n \geq 1$ , write the inequalities as $g_{i} (x) = G_{i} x - d_{i} \leq 0$ on the open convex set $U = R^{n}$ ; these functions are affine, differentiable and convex. The feasible tuple meets the hypotheses of [F4], which gives global minimality and $- \nabla f (x_{*}) \in N_{C} (x_{*})$ ; step 1.3 then gives the fixed point. No constraint qualification or multiplier converse is used.

Depends on

Used by

Projected gradient on the nonnegative orthant Example

Dependency tree · two levels

27 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

Amir Beck and Marc Teboulle, A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems, Remark 2.1 (standard reference, not scraped)
Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Chapter 5, §§5.1–5.2 (standard reference, not scraped)