Tag Archives: continuous

Discrete or continuous modeling ?

Tuesday, we got our conference “Insurance, Actuarial Science, Data & Models” and Dylan Possamaï gave a very interesting concluding talk. In the introduction, he came back briefly on a nice discussion we usually have in economics on the kind of model we should consider. It was about optimal control. In many applications, we start with a one period economy, then a two period economy, and pretend that we can extend it to n period economy. And then, the continuous case can also be considered. A few years ago, I was working on sports game as an optimal effort startegy (within in a game – fixed time). It was with a discrete model, I was running simulations to get an efficient frontier, where coaches might say “ok, now we have enough (positive) difference, and we get closer to the end of the game, so we can ‘lower the effort’ i.e. top players can relax a little bit” (it was on basket-ball games). I asked a good friend of mine, Romuald, to help me on some technical parts of proofs, but he did not like so much my discrete-time model, and wanted to move to continuous time. And for now six years, we keep saying that someday we should get back to that paper….

My initial thoughts were that the difference was really “cultural”: you are either a continuous-time sort of guy, or a discrete-time one (or maybe none of the two, but that’s another problem). He works with stochastic processes, I work with time series. Of course, we can find connections, but most of the time, the techniques are very different. And tuesday, Dylan mentioned a very nice illustration that it’s not necessarily a cultural difference, and sometimes, it is great to move to continuous time. So I wanted to illustrate that idea.

Consider for instance the following curve.

vu = seq(0,1,length=601)
vv = sin(vu*pi)
plot(vu,vv,type="l",lwd=2)

The goal is to find the value of the maximum, numerically. And here, there are two (very) different strategies

  • the discrete one: we see a (finite) collection of points – for instance, the graph above is a collection of 601 points (connected with a straight line) – and in that case, we need a standard algorithm (in O(n)) to get the value of the maximum
  • the continuous one: we see a function x\mapsto \sin(\pi x), and in that case, we use optimization routines

In the second case, use for instance

optim(0,function(x) -sin(pi*x))
$par
[1] 0.5
 
$value
[1] -1

For the first case, we can use the standard R function, and see how long it takes to use simulations to get an approximation of the maximum

library(microbenchmark)
max_time = function(n) median(microbenchmark(max(sin(runif(n)*pi)))$time)
vn = 10^(seq(1,6,length=21))
vt = Vectorize(max_time)(vn)
plot(vn,vt/1e9,col="blue",pch=19,type="b",log="xy")

but of course, some home-made code can also be used

c_max = function(n=100){
  x = sin(runif(n)*pi)
  y = x[1]
  for(i in 2:length(x)) { 
    if(x[i] > y) { y = x[i] }}
  return(y)}
max_time=function(n) median(microbenchmark(c_max(n))$time)
lines(vn,vt/1e9,type="b")

We can add that horizontal red line using

abline(h=median(microbenchmark(optim(.5,function(x) sin(pi*x)))$time)/1e9,lty=2,col="red")

So, indeed, it looks like computational time to find the maximum in a list of n elements is linear in n, i.e. O(n). And R code is faster than home-made code. But also, interestingly, using continus time (based on analysis techniques) can be much faster. So, sometimes, considering continuous time models can be much easier to solve, from a numerical perspective.

Optimal control, part 1

Since I had recently a request (from Benoît) about optimal control, I will start here a series of posts on that topic. But first, let us start with a simple problem, with discrete timeno randomness, and with a finite horizon. This might be a too simple framework to model complex problem, but that should be interesting to derive heuristic intuitions (I will skip here the mathematical problems, that can be found in very good books… references will come soon).

  • An introduction to backward induction

Before starting seriously, let us consider the following example: we want to reach the red city on the right from the red city on the left, as fast as possible. There are some roads, and the number is the number of hours it takes. Let us prove that the optimal way is the red one,

The first idea can be to calculate all possible trajectories, but with a large number of roads, the number of possible ways can soon be extremely large. An alternative can be to look backwards (like any students facing a question where the answer is given: start from the end, and try to find a possible way to reach it).


Numbers are greens are the number of hours that we still need one we’ve reached that point. Let us move again one step backward, and consider the orange points,

In the middle, we had to chose either to go up (it will still take 9 hours) or go down (and then 14 hours are necessary). Thus, the optimal strategy, once we’ve reach that point, it to take the 9 hour road. This will be idea the idea proposed by Bellman. Let us go backward again, to the purple cities. Again, we have to chose the shorter way,

From the top, the fastest road will take 13 hours, and from the bottom, it will take 16 hours. Thus, since it takes 10 hours to reach the top city, this road is necessarily faster than taking the one below (since it takes 8 hours to reach the nearest city).
Any this is it. We now have an intuitive idea of what should be done to find optimal strategies.

  • The optimization problem, discrete with finite horizon

Let us consider the following optimization problem: we want to find the optimal strategy https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-01.png that maximizes the following function

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-02.png

with simple constraints, such as https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-03.png (a state space) and https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-04.png (i.e. some dynamic constraints). Assume further that the starting point is given, i.e.
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-05.png. In economic application, note that frequently https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-06.png i.e. we consider a discounted version of the value.

  • The idea of dynamic programming

The intuitive idea of dynamic programming is that if the optimal path from A to C goes throught B, then the path is optimal from B to C. Thus, it will be natural to consider backward induction techniques.
Thus, define
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-07.png
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-08.png
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-09.png

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-10.png
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-11.png
Then Bellman’s principle can be used to link those problems: if https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-12.png is a solution of the problem https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-13.png then, for all
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-14.png, https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-15.png is a solution of problem https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-16.png.
Note that, so far, we assume that such an optimal sequence does exist. Thus, we get that for all x

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-17.png

and more generally,

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-18.png

He
nce, from a practical point of view, we solve those equation using a backward approch. I.e. first,

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-20.png

and then

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-21.png

and so on

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-22.png

… etc. It can be proved that the sequence https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-23.png is solution of https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-24.png if and only if for all https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-25.png,  https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-15.png
is solution of

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-27.png

So far, it does not look so difficult….

  • A simple example

Let  https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-30.png denote the consumption at period t, and assume consumption yields utility

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-31.png

as long as the consumer lives. Assume the consumer is impatient, or has a stronger preference for present, so that he discounts future utility by a factor https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-32.png. Let https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-33.png be capital he got at time t. Assume that his initial capital is a given amount https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-34.png, and suppose that this period’s capital and consumption determine next period’s capital as

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-35.png

where https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-36.png is a positive constant and https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-37.png. Assume further that capital cannot be negative. Then the consumer’s problem is simply

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-38.png

given https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-39.png. Bellman’s equation is then

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-40B.png

whih leads us to a simplier problem than the initial one, since only two variables are involved here https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-41.png and https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-42.png. And to solve that problem, we use backwards induction techniques.
Since https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-44.png is known, we can derive easily https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-45.png,  and so on until https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-46.png. More precisely, given https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-47.png, we can get https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-49.png which is the maximum of function

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-50.png

with https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-51.png. One can see that the following function is a possible solution

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-52.png

where each https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-53.png is a constant. Further, the optimal amount to consume at time https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-54.png is

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-55.png

i.e., if we explicit those expressions

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-60.png
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-61.png
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-62.png

…etc.

  • A reformulation of the optimisation problem

Another way of expressing the optimization problem is the following: https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-70.png was the variable of interest, https://perso.univ-rennes1.fr/arthur.charpenti<br />
er/latex/control-71.png was the control variable, and https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-72.png. Thus, the programm

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-73b.png

can be expressed as

https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-74.png

Several extension can be considered,

  • consider an infinite sum
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-80.png
  • consider a random component
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-81.png
  • consider a continuous version
https://perso.univ-rennes1.fr/arthur.charpentier/latex/control-82.png

But those items will be for posts that I still have to write down….