Interval Hessian-based Optimization Algorithm for Unconstrained Non-convex Problems

Second-order optimization algorithms that leverage the exact Hessian or its approximation have been proven to achieve a faster convergence rate than first-order methods. However, their applications on training deep neural networks models, partial differential equations-based optimization problems, and large-scale non-convex problems, are hindered due to high computational cost associated with the Hessian evaluation, Hessian inversion to find the search direction, and ensuring its positive-definiteness. Accordingly, we propose a new search direction based on an interval Hessian and incorporate it into a line-search framework. We apply our algorithm to a set of 210 problems and show that it converges to a local minimum for 70% of the problems. We also compare our algorithm with other approaches. We illustrate that our algorithm is competitive to other methods in finding a local minimum using a smaller number of O(n3) operations.