SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
Cuchulainn
Topic Author
Posts: 57641
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Asymptotic behaviour of ODE/PDE (large time)

December 13th, 2018, 9:46 am

In some cases you want to know the solution of a DE as [$]t \rightarrow \infty[$] Without loss of generality take the ODE in a Banach space

[$]y'(t)  = f(t, y(t))[$]

In particular, we want to find equilibrium  points where [$]y'(t) = 0[$]. We can do this in different ways. But now we take the new variable [$]\tau = t/(1+t)[$] to get  a new ODE

[$](1 - \tau)^2dy(\tau)/d\tau = F(\tau, y(\tau))[$] on the interval [$](0,1)[$]

Similar to transforming PDE to the unit interval we have an ODE on [$](0,1)[$]. So, for "big" [$]t[$] we approximate the solution at [$]\tau = 1 - \varepsilon[$].
I have tried with a number of simple and extended (nasty) scalar and system ODEs looks OK. At least, we know that the world ends at [$]\tau = 1[$]. ([$]\tau > 1[$] is the empty quarter; Picard iterates will probably blow up).

How does this approach work in theory? What are the risks, e.g. do invariants get messed up etc.?
 
User avatar
Alan
Posts: 9612
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: Asymptotic behaviour of ODE/PDE (large time)

December 14th, 2018, 3:16 pm

A point of comparison might be Mathematica's NDSolve approach. NDSolve does MOL with adaptive time stepping. I think the default  maximum t-step is T/10, where T is the final solution time. 

Consider a hypothetical parabolic PDE problem with a stationary solution, approached exponentially at large t with, let's say, a 'half-life' time of 50 (but you don't know this). 

You give this parabolic problem to NDSolve with T=1000. The solver takes, let's say, 50 time steps to do the whole computation. There will be many t-steps with, say, [$]t < 10[$] and the last several, sure enough, will use [$]\Delta t = 100[$], the max allowed. I have seen this pattern many times with NDSolve.

For your scheme, in effect you have a cutoff at [$]T \approx 1/\epsilon[$]. Suspect you would generally also have to adopt adaptive time stepping (in your case, [$]\tau[$]-stepping) to get any sort of decent run-time performance. If so, in the end, the pattern of the [$]t_i's[$] actually visited (under a good adaptive scheme) might be similar regardless of the time coordinate change: many at the start and few at the end. 

In other words, my point is that, in the end, if you adopt adaptive time-stepping to get decent performance, the choice of the time coordinate may not matter much.  Just speculating.
 
User avatar
ppauper
Posts: 69846
Joined: November 15th, 2001, 1:29 pm

Re: Asymptotic behaviour of ODE/PDE (large time)

December 15th, 2018, 7:23 am

I can vaguely remember doing a course on "nonlinear differential equations" as an undergrad and pretty sure we looked at the stability of the "point" at infinity, but long since lost the notes and can't remember how we did it
Bear in mind that your transformation maps the circle [$]|t|=\infty[$] to the point [$]\tau=1[$]

wiki has Barbalat's lemma and stability of time-varying systems for when you have [$]\frac{dy}{dt}=f(t)[$] rather than [$]f(t;y(t))[$]
 
User avatar
Cuchulainn
Topic Author
Posts: 57641
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Asymptotic behaviour of ODE/PDE (large time)

December 19th, 2018, 1:11 pm

A point of comparison might be Mathematica's NDSolve approach. NDSolve does MOL with adaptive time stepping. I think the default  maximum t-step is T/10, where T is the final solution time. 

Consider a hypothetical parabolic PDE problem with a stationary solution, approached exponentially at large t with, let's say, a 'half-life' time of 50 (but you don't know this). 

You give this parabolic problem to NDSolve with T=1000. The solver takes, let's say, 50 time steps to do the whole computation. There will be many t-steps with, say, [$]t < 10[$] and the last several, sure enough, will use [$]\Delta t = 100[$], the max allowed. I have seen this pattern many times with NDSolve.

For your scheme, in effect you have a cutoff at [$]T \approx 1/\epsilon[$]. Suspect you would generally also have to adopt adaptive time stepping (in your case, [$]\tau[$]-stepping) to get any sort of decent run-time performance. If so, in the end, the pattern of the [$]t_i's[$] actually visited (under a good adaptive scheme) might be similar regardless of the time coordinate change: many at the start and few at the end. 

In other words, my point is that, in the end, if you adopt adaptive time-stepping to get decent performance, the choice of the time coordinate may not matter much.  Just speculating.
I did a few (diverse) tests related to optimisation via ODE gradient systems (using complex step method) (I have a post on the yugely popular [$]e^5[$]  thread).

[$]dx/dt = - grad f(x) = -\nabla f(x)[$] where [$]f[$] is the function to be minimised.

1. MLE examples with normal and exponential distributions. Transformed ODE takes [2,5] less function calls than untransformed ODE for the same accuracy. The half-life [$]\tau = 1/2[$] seems like a good heuristic. 

2. Other, multidimensional, unimodal functions give similar results as in 1.

In general, convergence does not severely depend on the initial value (guess). I am using C++ Boost odeint with adaptive time-stepping, probably not unlike the NDSolve approach. Using odeint with [$]\tau = 0.9999[$] takes forever (probably a yuge boundary layer at [$]\tau = 1[$]..). On the other hand, since we use complex step method (no catastrophic subrtraction) we have accuracy like [$]10^{-290}[$].

3. For multimodal functions asymptotic stability is visible, but to a local minimum as for Ackley's function, for example. If you start near the global minimum then the solver will converge to it. Not enough energy to go back uphill. It cannot get out of a rut as it were.

Image
 
User avatar
Alan
Posts: 9612
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: Asymptotic behaviour of ODE/PDE (large time)

December 19th, 2018, 8:23 pm

What's the rationale for using an ODE for that type of problem? Why not just use standard optimizers on [$]f(x)[$]? 
 
User avatar
Cuchulainn
Topic Author
Posts: 57641
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Asymptotic behaviour of ODE/PDE (large time)

December 20th, 2018, 10:03 am

What's the rationale for using an ODE for that type of problem? Why not just use standard optimizers on [$]f(x)[$]? 
We do as well use them.
The objective is to compare the two approaches with regard to robustness (less tweaking of parameters, for example) and that several optimisers are essentially Euler's method applied to certain kinds of ODEs.

The 'starting point' is not discrete space but continuous space.
 
User avatar
FaridMoussaoui
Posts: 300
Joined: June 20th, 2008, 10:05 am

Re: Asymptotic behaviour of ODE/PDE (large time)

December 20th, 2018, 2:04 pm

On the other hand, since we use complex step method (no catastrophic subrtraction) we have accuracy like [$]10^{-290}[$].
I suppose that you are using some multi-precision package to deal with that number magnitude. What is the usefulness of that precision?
and even, you are solving some "toy" problems.
 
User avatar
Cuchulainn
Topic Author
Posts: 57641
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: Asymptotic behaviour of ODE/PDE (large time)

December 20th, 2018, 2:10 pm

On the other hand, since we use complex step method (no catastrophic subrtraction) we have accuracy like [$]10^{-290}[$].
I suppose that you are using some multi-precision package to deal with that number magnitude. What is the usefulness of that precision?
and even, you are solving some "toy" problems.
That precision is not needed, indeed. 
I am trying to see how far it gets. If it breaks I will stop. I want to try it then for a larger 'actual' test case. 
Question: What's a good stress test case? Number of variables (thousands, millions) and/or function complexity?
 
User avatar
Alan
Posts: 9612
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: Asymptotic behaviour of ODE/PDE (large time)

December 20th, 2018, 6:00 pm

Just had a thought. So, you can certainly maximize a (differentiable) convex [$]f(\vec{x})[$], by embedding it in an asymptotic ODE system problem -- as you did. Then, the asymptotic solution to that ODE provides an alternative to convex maximization. 

Correspondingly, if [$]f(\vec{x})[$] is not convex (and so has multiple local maxima), I wonder if embedding the problem in some sort of SDE system can work? My first thought was something like

(*) [$]d \vec{x}_t = \nabla f(\vec{x}) dt + \vec{k} \, \nabla f(\vec{x}) \cdot d \vec{W}_t[$],

where [$]\vec{k}[$] is some constant vector. In other words, my thought was perhaps solving (*) in some sense provides an alternative to Differential Evolution or other global optimizers. The idea was that the noise term would let you jump around to explore various local maxima. 

But, I can see at least two problems. First, evidently missing from the idea is some supplementary criteria that makes you jump away from some local maxima that's inferior to some other one already investigated. Second, I would like the Brownian noise term to disappear when f( ) is convex, thus reducing the SDE system to your ODE system.  

I haven't really studied Differential Evolution, but have always treated it as black box in Mathematica's optimizer suite. Maybe it is well known that DE is similar to some sort of SDE system?? 

Maybe the addition of some kind of non-local jump term could fix these issues? Just speculating. 

Anyway, some issues to ponder: 
- Is there a natural, continuous-time, generalization of what you are doing to the case of non-convex [$]f(\vec{x})[$]? 
- Failing that, is there a natural discrete-time generalization?
 
User avatar
FaridMoussaoui
Posts: 300
Joined: June 20th, 2008, 10:05 am

Re: Asymptotic behaviour of ODE/PDE (large time)

December 20th, 2018, 7:23 pm

My first thought was something like

(*) [$]d \vec{x}_t = \nabla f(\vec{x}) dt + \vec{k} \, \nabla f(\vec{x}) \cdot d \vec{W}_t[$],
That was a "standard" approch to use a global optimiser. Have a look to Aluffi and all, Journal of optimization theory and application. Vol 47, 1995.
 
User avatar
Alan
Posts: 9612
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: Asymptotic behaviour of ODE/PDE (large time)

December 20th, 2018, 8:03 pm

My first thought was something like

(*) [$]d \vec{x}_t = \nabla f(\vec{x}) dt + \vec{k} \, \nabla f(\vec{x}) \cdot d \vec{W}_t[$],
That was a "standard" approch to use a global optimiser. Have a look to Aluffi and all, Journal of optimization theory and application. Vol 47, 1995.
Excellent! It's behind a paywall but I can see from the abstract that it's spot-on.

update: Found it for download at ResearchGate.net
 
User avatar
FaridMoussaoui
Posts: 300
Joined: June 20th, 2008, 10:05 am

Re: Asymptotic behaviour of ODE/PDE (large time)

December 20th, 2018, 8:45 pm

My post was deleted. So I am not allowed to show you how to bypass a paywall.
 
User avatar
Alan
Posts: 9612
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: Asymptotic behaviour of ODE/PDE (large time)

December 20th, 2018, 9:07 pm

That's OK. I've got it. And I see from Storn and Price that the 1985 SDE method was obsoleted by DE circa 1995 because of a massive reduction in the number of function evaluations needed! (Table 3). So, while an SDE approach indeed works, it's not a good one. Well, I learned something today.
 
User avatar
ExSan
Posts: 4530
Joined: April 12th, 2003, 10:40 am

Re: Asymptotic behaviour of ODE/PDE (large time)

December 20th, 2018, 10:10 pm

My post was deleted. So I am not allowed to show you how to bypass a paywall.
what do you mean?
 
User avatar
FaridMoussaoui
Posts: 300
Joined: June 20th, 2008, 10:05 am

Re: Asymptotic behaviour of ODE/PDE (large time)

December 21st, 2018, 9:08 am

Well, I posted a link to a website where you can download "any" research paper.
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On