SERVING THE QUANTITATIVE FINANCE COMMUNITY

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

### Asymptotic behaviour of ODE/PDE (large time)

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.?

Alan
Posts: 9741
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

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

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.

ppauper
Posts: 70239
Joined: November 15th, 2001, 1:29 pm

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

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))$

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

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

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.

Alan
Posts: 9741
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

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

What's the rationale for using an ODE for that type of problem? Why not just use standard optimizers on $f(x)$?

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

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

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.

FaridMoussaoui
Posts: 370
Joined: June 20th, 2008, 10:05 am

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

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.

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

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

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?

Alan
Posts: 9741
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

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

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?

FaridMoussaoui
Posts: 370
Joined: June 20th, 2008, 10:05 am

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

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.

Alan
Posts: 9741
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

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

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.

FaridMoussaoui
Posts: 370
Joined: June 20th, 2008, 10:05 am

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

My post was deleted. So I am not allowed to show you how to bypass a paywall.

Alan
Posts: 9741
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

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

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.

ExSan
Posts: 4537
Joined: April 12th, 2003, 10:40 am

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

My post was deleted. So I am not allowed to show you how to bypass a paywall.
what do you mean?

FaridMoussaoui
Posts: 370
Joined: June 20th, 2008, 10:05 am