  This paper addresses the question of whether it can be beneficial for an
optimization algorithm to follow directions of negative curvature. Although
prior work has established convergence results for algorithms that integrate
both descent and negative curvature steps, there has not yet been extensive
numerical evidence showing that such methods offer consistent performance
improvements. In this paper, we present new frameworks for combining descent
and negative curvature directions: alternating two-step approaches and dynamic
step approaches. The aspect that distinguishes our approaches from ones
previously proposed is that they make algorithmic decisions based on
(estimated) upper-bounding models of the objective function. A consequence of
this aspect is that our frameworks can, in theory, employ fixed stepsizes,
which makes the methods readily translatable from deterministic to stochastic
settings. For deterministic problems, we show that instances of our dynamic
framework yield gains in performance compared to related methods that only
follow descent steps. We also show that gains can be made in a stochastic
setting in cases when a standard stochastic-gradient-type method might make
slow progress.
