# Constrained optimization on a finite set

20 views (last 30 days)

Show older comments

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?

##### 0 Comments

### Accepted Answer

Walter Roberson
on 27 Sep 2022

### More Answers (1)

Peter Galbacs
on 30 Sep 2022

##### 1 Comment

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

### See Also

### Categories

### Community Treasure Hunt

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

Start Hunting!