Constrained optimization on a finite set

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?

Answer 1

[Walter Roberson]

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]

Many thanks, but I think I need to respecify my question. What I am interested in is NOT integer values, but a finite set (e.g. a vector) that contains the possible values for optimization (like CVAL=[0.010 0.015 0.020 ... 0.995 1.0]). I'd like to order Matlab to find and select the optimum values from such a vector.

[Peter Galbacs]

I have tried, but there is no gain in running time. Quite the opposite.

[Walter Roberson]

Define lower bound 2 and upper bound 200 and multiply by 0.005 to get the values you want.

Improvements in running time are not to be expected for integer constraints: you no longer have continuous functions and so cannot reliably use gradient based methods.

[Peter Galbacs]

Thanks Walter, I got that!

[Torsten]

Why do you start with t=2 and not with t=100000 since it seems you don't use the solution of step n for step (n+1) ?

[Walter Roberson]

@Torsten

Notice there is a break though, so the task is to find the first location that satisfies the criteria.

[Torsten]

Yes, but knowing the breakthrough is quite late, approaching this point from above could be faster, I guess.

A kind of "method of nested intervals" should help here. Start with n = 100000, 100001. If V(100001)-V(100000) < maxError -> n = 50000, 50001 else n = 200000, 200001 etc.

[Walter Roberson]

I wonder if a binary search would be effective ? Though you would need to be able to adjust the upper bound.

[Peter Galbacs]

@ Torsten, that is a very interesting option! Let me see how it works.

Answer 2

[Peter Galbacs]

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:

Increase Speed by Reducing Precision - MATLAB & Simulink (mathworks.com)

But I have no idea how to apply it to the precision of the optimization toolbox. Does it make sense at all...?

[Torsten]

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