← All papers
First page of Initialization-dependent BFGS trial rates for tilted absolute values

Initialization-dependent BFGS trial rates for tilted absolute values

Qiuyu Chen

math.NA Sep 9, 2026 · v1 math.OC
The main counterexample results on BFGS trial-normalized rates are formalized in Lean, with a public GitHub repository.
Lewis and Overton conjectured in 2008 that, for BFGS applied to the one-dimensional tilted absolute value with their Armijo–Wolfe line search, every nonterminating execution converges at a trial-normalized rate determined only by the tilt parameter and independent of the initial data. We prove that this initialization-independent rate assertion is false. In fact, for every tilt parameter in an explicit open interval, we construct two nonterminating executions with different sharp trial-normalized convergence rates. The proof reduces the line search to a scale-free state consisting of the iterate sign and the zero-crossing stepsize, and verifies two periodic state cycles by elementary rational inequalities. This yields an explicit family of counterexamples and shows that the asymptotic trial-normalized behavior of nonsmooth BFGS can depend essentially on the initialization even for this canonical one-dimensional model.

Lewis and Overton conjectured in 2008 that BFGS with an Armijo–Wolfe doubling–bisection line search on the tilted absolute value f_u(x)=max{x,-ux} converges at a trial-normalized rate that depends only on u. The conjecture says this rate does not depend on the initialization.

The line search is reduced to a scale-free state made of the iterate sign and the zero-crossing stepsize. For each u in the interval (9/5, 13/6), two periodic state cycles are constructed. Each cycle is verified by elementary rational polynomial inequalities, and each contracts the full state by its own factor. The main results are formalized in Lean.

For every u in (9/5, 13/6) and every Wolfe parameter c2 in (0,1), there are two nonterminating executions with different sharp trial-normalized R-linear rates. This disproves the initialization-independence part of the Lewis–Overton conjecture and gives an infinite family of rational counterexamples.