Papers With

← All papers
First page of BFGS can converge to non-Clarke-stationary points with positive probability

BFGS can converge to non-Clarke-stationary points with positive probability

Lexiao Lai

math.OC Oct 25, 2026 · v1
formalization analysis
Read PDF arXiv abstract Code
TL;DR
The main result, that BFGS converges to a non-Clarke-stationary point, is formalized in Lean in an accompanying GitHub repository.
Abstract
We construct a coercive, locally Lipschitz, semialgebraic function on $\mathbb R^2$ for which BFGS with Armijo–Wolfe line search converges to a non-Clarke-stationary point from a nonempty open set of initial points and inverse-Hessian estimates. This disproves the almost-sure stationarity assertion in the 2013 challenge of Lewis and Overton. The construction and proof combine analytical arguments with computer-assisted verification of explicit inequalities.
Problem

Lewis and Overton (2013) asked whether BFGS with Armijo–Wolfe line search, on locally Lipschitz semialgebraic functions with bounded sublevel sets, has only Clarke-stationary cluster points almost surely under random initialization.

Approach

A coercive, locally Lipschitz, semialgebraic function on R^2 is constructed that is positively homogeneous near the origin, which sustains a shrinking BFGS cycle. BFGS scaling and covariance identities let the cycle repeat under linear changes of coordinates. A stability argument extends the failure to nearby initializations. Explicit inequalities are certified by rigorous computation, and the main result is formalized in Lean.

Results

BFGS converges to a non-Clarke-stationary point from a nonempty open set of initial points and inverse-Hessian estimates. This set has positive probability under Gaussian–Wishart initialization, which disproves the almost-sure stationarity assertion.