Constrained optimization on a finite set

20 views (last 30 days)
Peter Galbacs on 27 Sep 2022
Edited: Torsten on 30 Sep 2022
Hi all,
I am trying to write a code for the famous cake-eating problem popular in dynamic optimization. The idea is simple: solve for the optimum (i.e. utility-maximizing) consumption path on every t (time horizon), then increasing t by 1, and then solve for the optimum path in the now extended problem. This process goes on until the maximum utility realized on a given t does not increase 'substantially' the utility realized on the previous (t-1) problem. According to contraction mapping theorem when t goes to infinity, maximum utilities on every t approaches the maximum utility (that is, value function) of the infinite problem. The maximum utility of the infinite problem is what we are looking for.
I have set up the code below. It works properly, but I have a question - placed under the code.
% Determinsitic problem
clear
n=100000 % maximum number of iterations
W0=1 % cake size
beta=0.95 % discount factor
gamma=1 % parameter in the utility function
B=[1] % first element of the discounting vector
maxError=0.0001
if gamma==1
V(1)=log(W0) % value function at T=1, there is no problem as the agent consumes the whole cake at once. Now we can start iteration at t=2.
else V(1)=((W0).^(1-gamma)-1)/(1-gamma) % value function at T=1, there is no problem as the agent consumes the whole cake at once. Now we can start iteration at t=2.
end
for t=2:n
prob=optimproblem("Description","Optimum cake eating t->infinity","ObjectiveSense","max")
c=optimvar("c",t,"LowerBound",0)
B=[B beta^(t-1)] % updating discount vector B
if gamma==1
utility=B*log(c)
else utility=B*((c).^(1-gamma)-1)/(1-gamma)
end
prob.Objective=utility
totalc=sum(c)
prob.Constraints.totalconsumption=totalc==W0
initialGuess.c=W0/t*ones(t,1)
[sol,VF]=solve(prob,initialGuess)
V(t)=VF
optPath=sol.c
if abs(V(t)-V(t-1))<maxError
break
end
end
Running time is rather long (for gamma=1, the logarithmic utility function, it is around 20 minutes). As you can see, optimvar is c, a vector, whose dimensionality is t in every loop (we have an optimum consumption path for every t). My question: is there a way to force Matlab to work on a finite set of an optimization variables? This is called a grid. I mean, for instance, defining an n=1000 vector of possible consumptions [something like this: CVAL=linspace(0,1,1000)] in order that Matlab could look for and select the optimum values from vector CVAL only. Is it possible?

Walter Roberson on 27 Sep 2022
https://www.mathworks.com/help/optim/ug/optimvar.html#mw_cedf0526-03c6-46b9-aba3-a694d89d1003 shows how to constrain a optimvar to a range of integer values.
Peter Galbacs on 27 Sep 2022
@ Torsten, that is a very interesting option! Let me see how it works.

Peter Galbacs on 30 Sep 2022
Guys, is there any way to speed up computation by decreasing numerical accuracy? I know that in symbolic math toolbox something can be done about it:
But I have no idea how to apply it to the precision of the optimization toolbox. Does it make sense at all...?
Torsten on 30 Sep 2022
Edited: Torsten on 30 Sep 2022
There are several numerical parameters in the options-structure of fmincon you could play with, e.g.
OptimalityTolerance
StepTolerance
FunctionTolerance
But running your code, it seems that the problems for a fixed value of n are solved quite fast. So I'm in doubt whether setting the above parameters to higher values will really speed up the overall performance.
In my opinion, only saving optimizations for many values of n could substantially reduce computation time (e.g. by following my suggestion from above).

Categories

Find more on Nonlinear Optimization in Help Center and File Exchange

R2022b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!