MATLAB optimization: objective function with "steps"

Question

I am trying to find a minimum using fmincon in MATLAB, and I am facing a following problem:

Optimization completed because the size of the gradient at the initial point is less than the default value of the function tolerance.

My objective function's surface shows "steps", and therefore it has the same values over certain ranges of input variables (the size of the gradient is zero, if I am correct):

When moving from the initial point, the solver doesn't see any changes in the objective function's value, and finishes the optimization:

Iteration  Func-count       f(x)        Step-size       optimality

0           3          581.542                             0

Initial point is a local minimum.

Optimization completed because the size of the gradient at the initial point 
is less than the default value of the function tolerance.

Is there any way make the solver move forward when the objective function keeps its value unchanged (until the objective function starts to increase)?

Thanks for your help.

Answer 1

I post my extended comment as an answer in the hope that it will be easier for future answer seekers to find the solution:

Probably you would get reasonable results with a non-gradient based solver, e.g. ga, if the evaluation of the objective function is not costly. These are not dependent on the gradient and performing well on non-smooth functions. It is also worth to read the following guide before selecting solver algorithm: How to choose solver.