Exploiting Negative Curvature Directions
in Linesearch Methods for Unconstrained Optimization
N. I. M. Gould S. Lucidi M. Roma Ph. L. Toint
Report 97-18
In this paper we consider the definition of new efficient linesearch
algorithms for solving large scale unconstrained optimization
problems which exploit the local nonconvexity of the objective
function. Existing algorithms of this class compute, at each
iteration, two search directions: a Newton-type direction which
ensures a global and fast convergence, and a negative curvature
direction which enables the iterates to escape from the region of
local nonconvexity. A new point is then generated by performing a
movement along a curve obtained by combining these two directions.
However, the respective scaling of the directions is typically
ignored. We propose a new algorithm which aims to avoid the scaling
problem by selecting the more promising of the two directions, and
then performs a step along this direction. The selection is based on
a test on the rate of decrease of the quadratic model of the
objective function. We prove global convergence to second-order
critical points for the new algorithm, and report some preliminary
numerical results.