Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Along the PCG with fixed preconditioner H0H_0H0​, giTdj=0g_i^T d_j = 0giT​dj​=0 whenever j<ij < ij<i (eq. (16), second half)

Proved
LimitedBFGS.SQN.pcg_grad_direction_backward

by WillR · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

conjugate-gradientnumerical-linear-algebrapreconditioningquasi-newton

Along the preconditioned conjugate gradient method with a fixed positive definite preconditioner and exact line searches, the gradient at any iterate is orthogonal to every strictly earlier search direction.

Preamble
import Mathlib
import Definitions.Def_LimitedBFGS_SQN_pcgIter

open Matrix
Formal statement
namespace LimitedBFGS.SQN

/-- Along the preconditioned conjugate gradient iteration (13) of Nocedal 1980, p. 777, with the
fixed preconditioner `H0`, the gradient at a later iterate is orthogonal to every *strictly
earlier* search direction:

    g_i ᵀ d_j = 0    whenever    j < i,

where `g_k = grad A b (pcgIter A b H₀ x₀ k).x` and `d_k = (pcgIter A b H₀ x₀ k).d`.

**Proof.** The gradient of a quadratic is affine along a line, so the step from `x_k` with
length `a_k` along `d_k` moves the gradient by exactly

    g_{k+1} - g_k = a_k (A *ᵥ d_k),

and the one-step case `g_{k+1} ᵀ d_k = 0` is the defining property of the exact line search
(`exactStep_minimizes_grad`). For `j < k`, a strong induction on `i` now closes:

```lean
g_{k+1} ᵀ d_j = g_k ᵀ d_j + a_k (A *ᵥ d_k) ᵀ d_j
               = g_k ᵀ d_j   +  a_k d_j ᵀ (A *ᵥ d_k)
```

The first term is the hypothesis at the smaller index, and the second vanishes because the
search directions are `A`-conjugate, `d_j ᵀ (A *ᵥ d_k) = 0` for `j ≠ k`. Both ingredients are
independent of the gradient-orthogonality theorem `pcg_grad_orthogonality`.

**Ordering matters.** The identity holds only for `j < i`; it is *not* symmetric in the two
indices, and `g_j ᵀ d_i ≠ 0` in general for `j < i`. -/
theorem pcg_grad_direction_backward {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (hA : A.PosDef)
    (b : Fin n → ℝ) (H₀ : Matrix (Fin n) (Fin n) ℝ) (hH₀ : H₀.PosDef) (x₀ : Fin n → ℝ) :
    ∀ i j : ℕ, j < i →
      grad A b (pcgIter A b H₀ x₀ i).x ⬝ᵥ (pcgIter A b H₀ x₀ j).d = 0 := by sorry

end LimitedBFGS.SQN
Source
Nocedal, Updating Quasi-Newton Matrices with Limited Storage, Math. Comp. 35 (1980), p. 777, iteration (13) and eq. (16) second half: gradient orthogonality to earlier search directions

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me