Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3.1, p. 141 — exact line search ⇒ next search direction is orthogonal to y_k

Proved
NonsmoothQN.ExactNorm.prop_3_1_orthogonality

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

exact-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 f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R. Let HkH_kHk​ be symmetric positive definite, let fff be differentiable at xkx_kxk​ with gradient ∇fk\nabla f_k∇fk​, put pk=−Hk∇fkp_k = -H_k\nabla f_kpk​=−Hk​∇fk​, and let tk>0t_k>0tk​>0 and xk+1=xk+tkpkx_{k+1} = x_k + t_k p_kxk+1​=xk​+tk​pk​. Suppose that

  1. the function t↦f(xk+tpk)t \mapsto f(x_k + t p_k)t↦f(xk​+tpk​) has a local minimizer at tkt_ktk​;
  2. fff is differentiable at xk+1x_{k+1}xk+1​, with gradient ∇fk+1\nabla f_{k+1}∇fk+1​;
  3. Hk+1H_{k+1}Hk+1​ is symmetric positive definite and satisfies the secant condition Hk+1yk=tkpkH_{k+1} y_k = t_k p_kHk+1​yk​=tk​pk​, where yk=∇fk+1−∇fky_k = \nabla f_{k+1} - \nabla f_kyk​=∇fk+1​−∇fk​.

Then the next search direction pk+1=−Hk+1∇fk+1p_{k+1} = -H_{k+1}\nabla f_{k+1}pk+1​=−Hk+1​∇fk+1​ satisfies

pk+1Tyk=0.p_{k+1}^T y_k = 0 .pk+1T​yk​=0.

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 pk+1p_{k+1}pk+1​ up to sign.

Formalization Note. The statement is for general dimension nnn and general fff. The gradient ggg at xxx means: fff is differentiable at xxx and its Fréchet derivative is v↦gTvv\mapsto g^Tvv↦gTv (IsGradAt). The algorithm's standing data (positive definite HkH_kHk​, pk=−Hk∇fkp_k=-H_k\nabla f_kpk​=−Hk​∇fk​, tk>0t_k>0tk​>0, xk+1=xk+tkpkx_{k+1}=x_k+t_kp_kxk+1​=xk​+tk​pk​) are hypotheses; the symmetry of Hk+1H_{k+1}Hk+1​, 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
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

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