Step-coefficient identity for the PCG with fixed preconditioner H0: the beta of (13) equals the H0-norm ratio
ProvedLimitedBFGS.SQN.pcg_step_coefficientLet on with symmetric positive definite, let be symmetric positive definite, and let . Run the preconditioned conjugate gradient method with fixed preconditioner and exact line searches from , with iterates , directions and gradients . Then
where with is the coefficient in the direction recurrence of iteration (13) of the paper.
This is the classical conjugate-gradient step-coefficient identity, with the -inner product in place of the Euclidean one. It is the ingredient that is neither a definition nor a direct induction, and it is what drives the orthogonality relations of eq. (15) () and eq. (16) ( and for ) on p. 777.
Formalization Note The first relation is the exactness of the line search along and holds unconditionally. The second is stated for so that the ratio is defined; since is positive definite, implies , so the hypothesis is exactly the nondegeneracy of the ratio. The degenerate case needs no separate treatment: once a gradient vanishes the iteration stops, all later gradients and directions are , and the parent eq. (16) relations hold trivially from that index on.
The identity follows from two facts about the quadratic: the gradient difference along the search direction, with the exact line-search step, and the symmetry of . The -metric is essential; the corresponding Euclidean-metric norm identity is false for a preconditioner that does not commute with .
import Mathlib import Definitions.Def_LimitedBFGS_SQN_pcgIter open Matrix
namespace LimitedBFGS.SQN
/-- Step-coefficient identity for the PCG with fixed preconditioner `H₀` (Nocedal 1980, p. 777,
iteration (13) with `H₀` in place of every `H_{i−1}`). Write `gm` for the gradient at
step `m` and `dm` for the direction there, and let `ym = gm1 - gm` be the gradient
difference along the search direction.
The coefficient `beta = ymᵀ H₀ gm1 / ymᵀ dm` defining the direction recurrence
`d_{m+1} = -H₀ g_{m+1} + beta d_m` is the ratio of successive squared `H₀`-norms
of the gradients,
`beta = gm1ᵀ H₀ gm1 / gmᵀ H₀ gm`,
and, because the step along `dm` is an exact line search, the new gradient is orthogonal
to the direction just used,
`gm1ᵀ dm = 0`.
This is the classical conjugate-gradient step-coefficient identity (with the `H₀`-inner
product in place of the Euclidean one) that drives the orthogonality relations of eq. (15)
and eq. (16); it is the ingredient that is neither a definition nor a direct induction.
The hypotheses are the positive definiteness of `A` and `H₀`, so that the line search is
well posed; the identity itself is a consequence of the exact line search and of the
symmetry of `H₀`. -/
theorem pcg_step_coefficient {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 → ℝ)
(m : ℕ) :
(let gm := grad A b (pcgIter A b H₀ x₀ m).x
let dm := (pcgIter A b H₀ x₀ m).d
let gm1 := grad A b (pcgIter A b H₀ x₀ (m + 1)).x
let ym := gm1 - gm
let beta := (ym ⬝ᵥ (H₀ *ᵥ gm1)) / (ym ⬝ᵥ dm)
(gm1 ⬝ᵥ dm = 0) ∧
((gm ⬝ᵥ (H₀ *ᵥ gm)) ≠ 0 →
beta = (gm1 ⬝ᵥ (H₀ *ᵥ gm1)) / (gm ⬝ᵥ (H₀ *ᵥ gm)))) := by sorry
end LimitedBFGS.SQN