wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Calculus of Variations problem
        
(Message started by: amangupta on Feb 12^th, 2008, 12:54pm)

Title: Calculus of Variations problem
Post by amangupta on Feb 12^th, 2008, 12:54pm

I am a computer science researcher, and is facing the following problem:

Given a real number D > 0, minimize

Integrate[(f(x+1)/f(x)) dx] from 0 to f^-1(D).

over all differentiable functions f: R⁺ union {0} --> R⁺, such that f^-1(D) >= 1.

Note that the limits mean the range of f includes D.

Using f as the exponential function, I get this as O(log D). I want to know if this can be bettered.

Thanks in advance

Title: Re: Calculus of Variations problem
Post by Icarus on Feb 12^th, 2008, 4:23pm

The minimum value of the integral is 0, obtained by any function f for which f(0) = D, for example f(x) = D + x.

Title: Re: Calculus of Variations problem
Post by amangupta on Feb 13^th, 2008, 12:37am

Oh...I didnt notice that. Can it be solved under the assumption that f^-1(D) >= 1? My actual situation requires this; I am sorry I forgot to mention before.

Title: Re: Calculus of Variations problem
Post by Eigenray on Feb 13^th, 2008, 2:42am

One can still make the integral as small as you want. Just pick f so that f(x) > D for x < 1, f(1)=D, f(x) < D for x>1, and f(x) < http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif for x > 1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif. Then

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gif₀¹ f(x+1)/f(x) dx < http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gif₀^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif} 1 dx + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gif_{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif}¹ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif/D dx = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif(1 + (1-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif)/D).

Title: Re: Calculus of Variations problem
Post by amangupta on Feb 13^th, 2008, 5:15am

Looks like f increasing is also a condition :-[

Think of it as this way:if I use f(x) = x^k, I get it to be O(D^1/k), worse than O(log D)

if I use f(x) = 2^x, I get it to be O(log D)

if I use f(x) = Gamma(x) (i.e. generalization of n factorial), then I get O(log^k D), for some k such that 1 < k < 2. This is because 2^x < x! < 2^{x^2}.

So, as I am increasing the rate of change of f, I first decrease its value, then it starts increasing back again. So there is a minima lying somewhere in between - I want to find that.

Title: Re: Calculus of Variations problem
Post by Grimbal on Feb 13^th, 2008, 6:57am

It looks like on the large scale, the rate of change must be well distributed. So I guess an exponential would be a good choice.

The idea is that for a and c fixed, min(b/a+c/b) is at b=sqrt(ac), where a, b, c follow a geometric progression. You want exactly that condition on f if you take a=f(x), b=f(x+1), c=f(x+2). An exponential f(x)=a^x satisfies that condition nicely.

Maybe e^int(x) could be better on a small scale.

Title: Re: Calculus of Variations problem
Post by Eigenray on Feb 13^th, 2008, 9:34am

I think I am still missing something. You could do f(x) = D + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif(x-1), and then

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gif₀¹ f(x+1)/f(x) dx = 1 + log[D/(D-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif)],

which can be made arbitrarily close to 1.

Should we also be assuming f(0) is fixed, say f(0) = 1?

Title: Re: Calculus of Variations problem
Post by amangupta on Feb 13^th, 2008, 9:47am

f(0) = 1 was needed, but I assumed we can just scale the function by 1/f(0) for that, since f(0) was strictly positive. Though it seems how scaling changes f^-1(D) is affecting.

So f(0) = 1 is another constraint.

Title: Re: Calculus of Variations problem
Post by Eigenray on Feb 13^th, 2008, 3:16pm

We can still get arbitrarily close to 1. For 0 < p < 1, let f(x) = 1 + (D-1)*x^p. Then for 0<x<1, f(x) > D*x^p, and f(x+1) < D*2^p. So

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gif₀¹ f(x+1)/f(x) dx < http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gif₀¹ D*2^p/(D*x^p) dx = 2^p/(1-p).

But this can be made arbitrarily close to 1 by picking p small enough. Is there another condition you'd like to add? ::)