Cubic overestimation and secant updating for unconstrained optimization of C2,1 functions

• T. Bosse, J. Fischer, and A. Griewank
• 2014
• DOI: 10.1080/10556788.2013.863308

The discrepancy between an objective function f and its local quadratic model f(x)+∇ f(x)⊤ s+s⊤ H(x) s/2 ≈ f(x+s) at the current iterate x is estimated using a cubic term q |s|3/3. Potential steps are chosen such that they minimize (or at least significantly reduce) the overestimating function ∇ f(x)⊤ s+s⊤ B s/2+q |s|3/3 with B ≈ H(x). This ensures f(x+s)0 is too small. Either one or both quantities may be updated after unsuccessful and successful steps alike. For an algorithm employing both the symmetric rank one update and a shifted version of the BFGS formula we show that either∈f |∇ f|=0 or sup |B|=∞, provided the Hessian H(x) is Lipschitz on some neighbourhood of a bounded level set. Superlinear convergence is theoretically expected and numerically observed but not yet proven.