Differentiating the Ceiling Function

Date: 10/16/2000 at 11:42:14
From: Raymond
Subject: Differentiate a ceiling

Hi Dr. Math,

I have a problem involving differentiating the ceiling function, as 
follows:

     D = ceiling(M/p) * (p+H)/b - (k-1) * (p+H)/b

where M, H, b and k are constants. What is dD/dp? 

Thanks in advance.

Date: 10/16/2000 at 11:57:39
From: Doctor Rob
Subject: Re: Differentiate a ceiling

Thanks for writing to Ask Dr. Math, Raymond.

d(ceiling(x))/dx = 0 where x is not an integer, and is undefined where 
x is an integer. (That's because the ceiling function has a jump 
discontinuity at each integer value of x, and is horizontal in 
between.) That means that wherever x is not an integer, ceiling(x) can 
be treated like a constant. Thus your dD/dp is undefined if M/p is an 
integer, and

     dD/dp = [ceiling(M/p)-k+1]/b

otherwise.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   

Date: 10/17/2000 at 07:52:29
From: Raymond Quan
Subject: Re: Differentiate a ceiling

It seems that something is missing somewhere. I can't find the answer. 
Let me put in some values:

     P = 1024
     M = 10000
     H = 256
     b = 9600
     k = 4 
   
     D = ceiling(M/P) * (P+H)/b + (k-1) * (P+H)/b
       = 1.73

Now we need to find P such that D is minimized. Using your solution,

     dD/dp = [ceiling(M/p)-k+1]/b

I can't find the right answer. Can you give me further information? 
Thanks.

Date: 10/20/2000 at 15:03:50
From: Doctor Rob
Subject: Re: Differentiate a ceiling

Thanks for writing back, Raymond.

The equation from your first message was 

     D = ceiling(M/p) * (p+H)/b - (k-1) * (p+H)/b

The equation from your second message was

     D = ceiling(M/P) * (P+H)/b + (k-1) * (P+H)/b

These are different. Which one do you need to minimize? Using the 
derivative dD/dp from the first equation will probably not work to 
minimize D from the second equation.

By the way, the question you asked is not particularly relevant to the 
problem you were trying to solve: minimizing D as a function of P. 
Differentiating will only work if the function is continuous and 
differentiable on the interval where you are seeking the minimum. 
Functions which involve the ceiling function are discontinuous every 
place that the argument of the ceiling takes an integer value. In 
cases like this, you also have to consider the limit of the function 
on each side of each discontinuity.

For your function, the discontinuities are when M/P = n, a whole 
number, that is, when P = M/n. Let's assume that P > 0. Then the 
limits are

       lim     D = (n+k)*(M/n+H)/b,
     P->(M/n)-

       lim     D = (n+k-1)*(M/n+H)/b.
     P->(M/n)+

That means that you have to find the minimum value of all these 
quantities, over all positive whole numbers n. These minima can be 
found by differentiating the expressions on the right with respect to 
n, setting the derivatives equal to zero, and solving for n. The 
result of this will not, in general, be a whole number, but the two 
closest whole numbers, one on either side, will be candidates for the 
optimum value of n. Test which of these possibilities gives you the 
smallest D, and you'll have your answer.

In this case, the two expressions above gave me, respectively,

     n = sqrt(k*M/H) = sqrt(4*10000/256) = 25/2
     n = sqrt([k-1]*M/H) = sqrt(3*10000/256) = 2525*sqrt(3)/4

so the values of n to be tested were 12 and 13, and 10 and 11, 
respectively. The minimum occurred with 

     n = 11,
     p = 10000/11 = 909.091 
     D = 1.69909....  

If p has to be a whole number, then the minimum is at p = 910, D = 
1.70042....

If p < 0 is permitted, a similar analysis will produce the minimum in 
that case, too.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/