How to solve local minimum issue when using fminsearch in Matlab?

I am using 'fminsearch' in Matlab to solve the value function iteration problem.

parfor i_a = 1:Na                  %Loop over state variable a
    for i_d = 1:Nd                  %Loop over state variable d
        for i_y = 1:Ny                  %Loop over state variable y
            for i_t = 1:Nt                  %Loop over state variable y

                [adj_sol, adjval] = fminsearchbnd(@(x) ...
                -adjvalue_model1(x,i_a,i_d,i_y,i_t,Utility,A,D,Y,T,R,delta,fixed,Interpol_1,Na,Nd), ...
                [x0(i_a,i_d,i_y,i_t); x1(i_a,i_d,i_y,i_t)],...
                [A(1); D(1)],[A(end); D(end)],options);

Here, [x0(i_a,i_d,i_y,i_t); x1(i_a,i_d,i_y,i_t)] are a starting points for fminsearch.

However, the result doesn't seem right because it gives me local minimum value.

So I gave four different starting points and choose the minimum value out of three and the results seem reasonable.

            [adj_sol1, adjval1] = fminsearchbnd(@(x) ...
            -adjvalue_model1(x,i_a,i_d,i_y,i_t,Utility,A,D,Y,T,R,delta,fixed,Interpol_1,Na,Nd), ...
            [x0(i_a,i_d,i_y,i_t); x1(i_a,i_d,i_y,i_t)],...
            [A(1); D(1)],[A(end); D(end)],options);

            [adj_sol2, adjval2] = fminsearchbnd(@(x) ...
            -adjvalue_model1(x,i_a,i_d,i_y,i_t,Utility,A,D,Y,T,R,delta,fixed,Interpol_1,Na,Nd), ...
            [xs1(i_a,i_d,i_y,i_t); xs2(i_a,i_d,i_y,i_t)],...
            [A(1); D(1)],[A(end); D(end)],options);
        
            [adj_sol3, adjval3] = fminsearchbnd(@(x) ...
            -adjvalue_model1(x,i_a,i_d,i_y,i_t,Utility,A,D,Y,T,R,delta,fixed,Interpol_1,Na,Nd), ...
            [xs3(i_a,i_d,i_y,i_t); xs4(i_a,i_d,i_y,i_t)],...
            [A(1); D(1)],[A(end); D(end)],options);
        
            [adj_sol4, adjval4] = fminsearchbnd(@(x) ...
            -adjvalue_model1(x,i_a,i_d,i_y,i_t,Utility,A,D,Y,T,R,delta,fixed,Interpol_1,Na,Nd), ...
            [xs5(i_a,i_d,i_y,i_t); xs6(i_a,i_d,i_y,i_t)],...
            [A(1); D(1)],[A(end); D(end)],options);
            
            adjval = min([adjval1, adjval2, adjval3, adjval4]);
            if adjval == adjval1
            adj_sol = adj_sol1;
            elseif adjval == adjval2
            adj_sol = adj_sol2;        
            elseif adjval == adjval3
            adj_sol = adj_sol3;
            elseif adjval == adjval4
            adj_sol = adj_sol4;    
            end

However, using four different starting points is quite time-consuming so I was wondering whether there is another way I could deal with this local minimum issue and more efficient(in terms of speed) than just using multiple starting points.

Thanks in advance.

Solution

Multiple startpoints is a well known practice for local optimization algorithms. Perhaps you can try a different algorithm like simumated annealing.

Another way is to use global optimization algorithms like DIRECT (Dividing Rectangles) or Baysian Optimization if you do not know the gradient of the function