0
$\begingroup$

It seems that scipy.minimize can find the minimum of an unbounded function.

>>> import numpy as np
>>> from scipy.optimize import minimize
>>> def fun(y):
...     return y
... 
>>> res = minimize(fun, np.array([0.0]), method='SLSQP')
>>> res
  status: 0
 success: True
    njev: 14
    nfev: 42
     fun: array([ -3.05175781e+08])
       x: array([ -3.05175781e+08])
 message: 'Optimization terminated successfully.'
     jac: array([ 0.,  0.])
     nit: 14

To be clear, this function is unbounded below and does not have a minimum. Anyone know why scipy.minimize with SLSQP terminates successfully? Am I supposed to interpret -3e8 as negative infinity? This doesn't inspire much confidence.

$\endgroup$
  • $\begingroup$ does 'jac: array([ 0., 0.])' mean it thinks the gradient is zero at its 'solution'? $\endgroup$ – k20 Feb 16 '15 at 0:37
  • 2
    $\begingroup$ @k20 If it uses finite differencing, it might be using a step size of $\approx 10^{-8}$ so that its finite difference estimate in double-precision arithmetic would be exactly zero at such a large value of $x$. $\endgroup$ – Kirill Feb 16 '15 at 0:42
  • $\begingroup$ @kirill I see that you are correct. (-3e8 + 1e-8) == -3e8 is True in double precision. $\endgroup$ – k20 Feb 16 '15 at 1:30
4
$\begingroup$

To be clear, this function is unbounded below and does not have a minimum.

That means it does not satisfy the preconditions of minimize, assumptions that it makes about its input, so you should not pass it to minimize.

Anyone know why scipy.minimize with SLSQP terminates successfully?

It uses some heuristics to determine what's going on and whether it's appropriate to terminate, and in this case of an invalid input the heuristics failed because the author of those heuristics did not take this input into account. All heuristics are, by nature, heuristic, and not guaranteed to be correct.

One commonly made assumption is that all interesting values of $x$ and $f(x)$ are of reasonably small magnitude (not huge, or infinite, as in this case). Not that this is ideal, but it holds (possibly after rescaling) for most interesting problems.

Am I supposed to interpret -3e8 as negative infinity?

No. Numerical algorithms only aim to be approximately correct, and rarely offer any strong guarantees on the correctness of their outputs. All you can conclude is that $-3\times 10^8$ is the algorithm's best guess at the minimum value. In this case, the result is clearly wrong, but that is because you violated the assumptions the algorithm makes about its input functions.

Either change your function so that it does have a minimum, or consider filing a bug report with scipy, so that the invalid input gets recognized and causes an explicit error.

This doesn't inspire much confidence.

Any introductory numerical analysis textbook discusses the issues involved in using floating-point arithmetic (which is by nature and by necessity approximate), so I would recommend reading some introductions to numerical analysis to understand the challenges involved here, before blaming the authors of scipy.

$\endgroup$
  • $\begingroup$ thanks. All good points. I don't think I was blaming anyone---just posting what I thought was an interesting example (without thorough study or research, to be sure). I was checking to see if there were heuristics for identifying an unbounded function, and it appears there are not---at least for this simple example. I think your point above about the default step size for a finite difference gradient is helpful, and it suggests a more careful experiment. In many practical cases, one does not know if the function satisfies the "preconditions" you mention. $\endgroup$ – Paul G. Constantine Feb 16 '15 at 4:28
  • $\begingroup$ Oh, my comment about "confidence" is about the software, not the algorithm. I'm very familiar with numerical analysis, floating point arithmetic, and optimization algorithms. $\endgroup$ – Paul G. Constantine Feb 16 '15 at 4:33
  • 1
    $\begingroup$ @PaulG.Constantine Ah, okay. But it is unreasonable for numerical software to handle every badly behaved function imaginable (imagine passing "rand()" to minimize, what should the result be?). I would argue that it is okay for minimize to make assumptions about its input (being well-behaved, being bounded below with values of reasonable magnitude, etc.), and to expect you, the caller, to have to satisfy them (en.wikipedia.org/wiki/Precondition). It can do some basic sanity checking, but not much more if it's expensive and unnecessary for valid inputs. $\endgroup$ – Kirill Feb 16 '15 at 5:03
  • 1
    $\begingroup$ @PaulG.Constantine Also, since the tone of this answer is not really suitable for you, the actual answer is probably: it found a point for which the Jacobian was exactly zero, and it computed that using finite differencing in double-precision arithmetic with a step size of $10^{-8}$. So it just gave as the answer the point at which the Jacobian vanished, which isn't such a crazy thing for it to do. $\endgroup$ – Kirill Feb 16 '15 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.