Cubic overestimation and secant updating for unconstrained optimization of C ^{2, 1} functions

Abstract:

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)<f(x) unless the approximating Hessian B=B differs significantly from H(x) or the scalar q>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 eitherf | 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. © 2014 Taylor and Francis.

Año de publicación:

2014

Keywords:

• eigenvalue decomposition
• cubic overestimation
• Quasi-Newton
• unconstrained optimization
• compromise update

Fuente:

scopus