Proposition 3.1, p. 141 — exact line search ⇒ next search direction is orthogonal to y_k
ProvedNonsmoothQN.ExactNorm.prop_3_1_orthogonalityexact-line-searchp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1quasi-newtonsecant-condition
Consider one iteration of a quasi-Newton method (Algorithm 2.1) for a function . Let be symmetric positive definite, let be differentiable at with gradient , put , and let and . Suppose that
- the function has a local minimizer at ;
- is differentiable at , with gradient ;
- is symmetric positive definite and satisfies the secant condition , where .
Then the next search direction satisfies
This orthogonality is the only property of the exact line search used in the analysis of the norm in the plane: it fixes the direction of up to sign.
Formalization Note. The statement is for general dimension and general . The gradient at means: is differentiable at and its Fréchet derivative is (IsGradAt). The algorithm's standing data (positive definite , , , ) are hypotheses; the symmetry of , part of positive definiteness, is needed.
Preamble
import Mathlib import Definitions.Def_NonsmoothQN_ExactNorm_Basic open Matrix Filter Topology
Formal statement
namespace NonsmoothQN.ExactNorm
theorem prop_3_1_orthogonality {n : ℕ} (f : (Fin n → ℝ) → ℝ)
(xk pk gk xk1 gk1 : Fin n → ℝ) (Hk Hk1 : Matrix (Fin n) (Fin n) ℝ) (tk : ℝ)
(hHk : Hk.PosDef) (hHk1 : Hk1.PosDef)
(hgk : IsGradAt f gk xk) (hpk : pk = -(Hk *ᵥ gk))
(htk : 0 < tk) (hxk1 : xk1 = xk + tk • pk)
(hmin : IsLocalMin (fun τ : ℝ => f (xk + τ • pk)) tk)
(hgk1 : IsGradAt f gk1 xk1)
(hsec : Hk1 *ᵥ (gk1 - gk) = tk • pk) :
(-(Hk1 *ᵥ gk1)) ⬝ᵥ (gk1 - gk) = 0 := by sorry
end NonsmoothQN.ExactNorm
Source
Lewis, Overton, Nonsmooth optimization via quasi-Newton methods, Math. Program. Ser. A 141 (2013) 135–163, p. 141, Proposition 3.1 (with Algorithm 2.1, p. 140)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.