Globally linearly convergent nonlinear conjugate gradients without Wolfe line search

This paper introduces a measure for zigzagging strength and a minimal zigzagging direction. Based on this, a new nonlinear conjugate gradient (CG) method is proposed that works with line searches not satisfying the Wolfe condition. Global convergence to a stationary point is proved for differentiable objective functions with Lipschitz continuous gradient, and global linear convergence if this stationary point is a strong local minimizer. For approximating a stationary point, an \(\mathcal{O}(\varepsilon ^{-2})\) $\mathcal{O}({\epsilon }^{-2})$ complexity bound is derived for the number of function and gradient evaluations. This bound improves to \(\mathcal{O}(\log \varepsilon ^{-1})\) $\mathcal{O}(log{\epsilon }^{-1})$ for objective functions having a strong minimizer and no other stationary points. For strictly convex quadratic functions in n variables, the new method terminates in at most n iterations. Numerical results on the unconstrained CUTEst test problems suggest that the new method is competitive with the best nonlinear state-of-the-art CG methods proposed in the literature.