  We propose a computer-assisted approach to the analysis of the worst-case
convergence of nonlinear conjugate gradient methods (NCGMs). Those methods are
known for their generally good empirical performances for large-scale
optimization, while having relatively incomplete analyses. Using our
computer-assisted approach, we establish novel complexity bounds for the
Polak-Ribi\`ere-Polyak (PRP) and the Fletcher-Reeves (FR) NCGMs for smooth
strongly convex minimization. In particular, we construct mathematical proofs
that establish the first non-asymptotic convergence bound for FR (which is
historically the first developed NCGM), and a much improved non-asymptotic
convergence bound for PRP. Additionally, we provide simple adversarial examples
on which these methods do not perform better than gradient descent with exact
line search, leaving very little room for improvements on the same class of
problems.
