§5.1, p. 152 — and
ProvedNonsmoothQN.Secant.secant_H_and_directionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1quasi-newtonsecant-method
Run the secant method on with the inexact line search of §5.1, from any and any . For every with and , the inverse Hessian approximation given by the secant equation and the next search direction are
and the iterates alternate in sign: .
So the search direction always points back across zero with length half the distance to the previous iterate; this is what reduces the method to a bisection scheme.
Formalization Note The page assumes the setting of Algorithm 2.1, where is positive definite, i.e. ; this is the only hypothesis. The conditions are the page's ("providing "); a run with has already stopped.
Preamble
import Mathlib import Definitions.Def_NonsmoothQN_Secant_Basic import Definitions.Def_NonsmoothQN_Secant_Expansion
Formal statement
namespace NonsmoothQN.Secant
theorem secant_H_and_direction (x₀ H₀ : ℝ) (hH₀ : 0 < H₀) (k : ℕ)
(hk : secX x₀ H₀ k ≠ 0) (hk1 : secX x₀ H₀ (k + 1) ≠ 0) :
secH x₀ H₀ (k + 1) = |secX x₀ H₀ (k + 1) - secX x₀ H₀ k| / 2 ∧
secP x₀ H₀ (k + 1) =
-(|secX x₀ H₀ (k + 1) - secX x₀ H₀ k| / 2) * Real.sign (secX x₀ H₀ (k + 1)) ∧
secX x₀ H₀ k * secX x₀ H₀ (k + 1) < 0 := by sorry
end NonsmoothQN.Secant
Source
Lewis, Overton, Nonsmooth optimization via quasi-Newton methods, Math. Program. Ser. A 141 (2013) 135–163, p. 152, §5.1, first display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.