finite difference

On the Complexity of Lower-Order Implementations of Higher-Order Methods

  • Nikita Doikov
  • Geovani Nunes Grapiglia
    • Categories Nonlinear Optimization Tags , , , ,

    In this work, we propose a method for minimizing non-convex functions with Lipschitz continuous \(p\)th-order derivatives, starting from \(p \geq 1\). The method, however, only requires derivative information up to order \((p-1)\), since the \(p\)th-order derivatives are approximated via finite differences. To ensure oracle efficiency, instead of computing finite-difference approximations at every iteration, we reuse … Read more

    Some notes on applying computational divided differencing in optimization

  • Stephen A. Vavasis
    • Categories Optimization Software Design Principles Tags , , ,

    We consider the problem of accurate computation of the finite difference $f(\x+\s)-f(\x)$ when $\Vert\s\Vert$ is very small. Direct evaluation of this difference in floating point arithmetic succumbs to cancellation error and yields 0 when $\s$ is sufficiently small. Nonetheless, accurate computation of this finite difference is required by many optimization algorithms for a “sufficient decrease” … Read more