optimize: COBYLA hangs / infinite loop #8998
Description
I've witnessed COBYLA hanging in use on multiple occassions. The minimisation problems aren't particularly nasty, mainly linear constraints, one with a min/max type kink. There is a possibility that they are infeasible / very narrow sets that satisfy all the constraints but I've also seen these kinds of problems 'solve' to completion.
The problem appears to be caused by a NaN propagating through one of the matrices internal to COBYLA. I have gotten around this issue by adding some exceptions a 'C' version I found online, building it into a .pyd and passing it to scipy as a custom minimiser.
The location of the origination of the NaN in the C port should be a good hint for someone familiar with the FORTRAN algorithm:
/* If ICON exceeds NACT, then we add the constraint with index IACT(ICON) to
the active set. Apply Givens rotations so that the last N-NACT-1 columns
of Z are orthogonal to the gradient of the new constraint, a scalar
product being set to zero if its nonzero value could be due to computer
rounding errors. The array DXNEW is used for working space. */
if (icon <= nact) goto L_260;
kk = IACT(icon);
LOOP(i,n) {
DXNEW(i) = A(i,kk);
}
tot = zero;
for (k = n; k > nact; --k) {
sp = zero;
spabs = zero;
LOOP(i,n) {
temp = Z(i,k)*DXNEW(i);
sp += temp;
spabs += ABS(temp);
}
acca = spabs + Op1*ABS(sp);
accb = spabs + Op2*ABS(sp);
if (spabs >= acca || acca >= accb) sp = zero;
if (tot == zero) {
tot = sp;
} else {
kp = k + 1;
temp = SQRT(sp*sp + tot*tot);
alpha = sp/temp;
beta = tot/temp;
if (isnan(alpha) || isnan(beta)) throw "COBYLA Exception: NaN at line 1135";
Scipy/Numpy/Python version information:
scipy 1.0.1