Effect of one special BFGS update (4)-(5) on a vector orthogonal to the stored secant pair
ProvedLimitedBFGS.SQN.bfgsStep_actionbfgslimitedbfgslinear-algebraspecialh
Let be a matrix, and let be a stored secant pair. Write the special BFGS update (4)–(5) in its product form with and .
Claim. If and then . Moreover, under just one has the explicit formula .
Why. From we get , hence . Applying (7), , so and the rank-one term vanishes. If in addition the correction disappears and the update is a no-op on .
Role. This is the algebraic fact behind the identity of the limited-storage BFGS method (17) and the preconditioned conjugate gradient method with fixed preconditioner (Nocedal 1980, p. 778): every retained correction pair older than the newest one acts trivially on the current gradient, while the newest pair reproduces exactly PCG's term.
Preamble
import Mathlib import Definitions.Def_LimitedBFGS_SQN_specialH open Matrix
Formal statement
namespace LimitedBFGS.SQN
/-- Effect of one special BFGS update on a vector that is orthogonal to both the stored
secant pair's `s` and its `y`-image. Writing `bfgsStep H s y = Vᵀ H V ρ …` for the product
form (4)–(5), with `V = I − ρ y sᵀ`: if `sᵀg = 0` and `yᵀ(Hg) = 0` then the update leaves `H *ᵥ g`
alone, since `Vg = g` and `Vᵀ(Hg) = Hg`; and in general, under just `sᵀg = 0`,
`bfgsStep H s y *ᵥ g = H *ᵥ g − (ρ · yᵀ(Hg)) • s` with `ρ = bfgsRho s y`. These are the two
identities that make the limited-storage BFGS matrix act on the current PCG gradient exactly
as the conjugate gradient recurrence does (Nocedal 1980, p. 778). -/
theorem bfgsStep_action {n : ℕ} (H : Matrix (Fin n) (Fin n) ℝ) (s y g : Fin n → ℝ)
(hs : s ⬝ᵥ g = 0) (hy : y ⬝ᵥ (H *ᵥ g) = 0) :
bfgsStep H s y *ᵥ g = H *ᵥ g ∧
bfgsStep H s y *ᵥ g = H *ᵥ g - (bfgsRho s y * (y ⬝ᵥ (H *ᵥ g))) • s := by sorry
end LimitedBFGS.SQN
Source
Nocedal, Updating Quasi-Newton Matrices with Limited Storage, Math. Comp. 35 (1980), p. 776, eq. (7) and pp. 777-778 (the product form (4)-(5) used for the step of iteration (17)).