optimize.minimize infinite loop with Newton-CG

[Chris7]

I am currently trying to use Newton-CG but am running into a problem where I encounter an infinite loop in the minimization routine. Code to replicate this may be found here:

https://gist.github.com/Chris7/51ed3a8f8cec011ce3342615675195b7

I am using Ubuntu 14.04 64 bit, and here is my pip freeze:

coverage==4.0.3
coveralls==1.1
Cython==0.23.4
docopt==0.6.2
line-profiler==1.0
lxml==3.5.0
memory-profiler==0.41
nose==1.3.7
numpy==1.10.1
pandas==0.17.1
patsy==0.4.1
plotly==1.9.6
pluggy==0.3.1
profilestats==2.0
py==1.4.31
pyprof2calltree==1.3.2
python-dateutil==2.4.2
pytz==2015.7
requests==2.8.1
scikit-learn==0.17
scipy==0.17.1
six==1.10.0
tox==2.2.1
virtualenv==13.1.2

The code which runs infinitely is in optimize.optimize, lines 1412-1440 and are:

while numpy.add.reduce(numpy.abs(ri)) > termcond:
    if fhess is None:
        if fhess_p is None:
            Ap = approx_fhess_p(xk, psupi, fprime, epsilon)
        else:
            Ap = fhess_p(xk, psupi, *args)
            hcalls = hcalls + 1
    else:
        Ap = numpy.dot(A, psupi)
    # check curvature
    Ap = asarray(Ap).squeeze()  # get rid of matrices...
    curv = numpy.dot(psupi, Ap)
    if 0 <= curv <= 3 * float64eps:
        break
    elif curv < 0:
        if (i > 0):
            break
        else:
            # fall back to steepest descent direction
            xsupi = dri0 / (-curv) * b
            break
    alphai = dri0 / curv
    xsupi = xsupi + alphai * psupi
    ri = ri + alphai * Ap
    dri1 = numpy.dot(ri, ri)
    betai = dri1 / dri0
    psupi = -ri + betai * psupi
    i = i + 1
    dri0 = dri1          #

I would try to patch this myself, but I do not know enough about the Newton-CG method (yet). The issue appears to be that xsupi never increments and the curvature keeps increasing so it never breaks.

[rgommers]

Example reproduces for me. The while loop never terminates if curv remains > 3*eps, which is the case here (it continuously increases).

IIRC we decided quite a while ago to never have such while loops but always include a loop counter and maxiter value. So even if the issue here is some malformed input, we should modify that loop.

[Chris7]

Thanks @rgommers! One fix for this is to evaluate whether xsupi changes after the adjustment and if not, break out. That works for me locally, but I wasn't sure if that was too much of a hack versus a more proper way to address this

[pv]

The safest fix is probably to add maxiter. I'm not sure what the curvature termination condition for the algorithm exactly is, so unless this is made clear, the algorithm should terminate with failure in this case.

[ev-br]

gh-6229 adds a (mechanical) fix: it simply caps the number of iterations in this inner loop.

[Chris7]

Thanks for addressing this @ev-br

[ev-br]

@Chris7 I hesitated to convert your gist into a test. If you can contribute a test (ideally, something smaller), that would be very welcome.

[Chris7]

The test would be a function that doesn't converge -- so I guess you can use anything without a minimum? The hessian I posted was actually wrong, and this helped me track it down. Though the behavior with this curvature wasn't desired (it just kept iterating vs halting)