Thursday, September 3, 2009

Overflow in NLP

The expression log(sum(i,exp(x(i)))) can lead to numerical instability or even overflow. Sometimes it helps to “scale” this as follows:

   C+log(sum(i,exp(x(i)-C)))

for some constant C. A reasonable value for C is the largest x(i) you expect. Note that exp(.) overflows quickly. This functional form is used in many economic models, and for x > 10 approximates the max function.

As a somewhat long aside:

When using recent versions of GAMS you need to be aware that exp(.) does never overflow because it is truncated. I.e. exp will actually return min{exp(x),1e299}. This looks smart but on the whole I think this does actually more harm than good and I am not aware of any other numerical software that does such a truncation. As a result the function is no longer smooth (in theory one should use then a DNLP solver, but an exception is introduced for this case). Although f(x)=min{exp(x),1e299} is evaluated correctly, the derivative f’ is not adjusted accordingly (it should be 0 for x>log(1e299) but instead is calculated as 1e299).

Strangely an overflow message can appear in the gradient calculation:

1  scalar x /1000/;
2  scalar f, grad;
3  
4  f = exp(x);
5  grad = exp.grad(x);
6  
7  display x,f,grad;

This will give a message about line 5:

**** Exec Error at line 5: exp: FUNC OVERFLOW: x too large

I.e. GAMS issues a overflow error in the gradient evaluation but not in the function evaluation. Another example of a somewhat unexpected result is:

scalar x /1e10/;
scalar y;

set i /i1*i50/;
loop(i,
  x = x*1e6;
  y = exp(x);
  display x,y;
);

this actually does overflow. But not in the exp()! It overflows in the multiplication which is not truncated. Note also that in normal math we have exp(x)>x, but with this truncation rule there exist x such that x > exp(x) (e.g. take x=1.1e299). As you can guess I am not a fan of this redefinition of exp. Old-fashionedly, I would prefer to be alerted of an overflow so I can fix this in the model compared to truncating behind my back. I assume the truncation was introduced in order not to bother the user with trivialities like overflow; well, in this case I actually like to be bothered and would prefer a consistent application of overflow conditions.