Solvers from the Global Optimization Toolbox like patternsearch or surrogateopt can be better suited for these problems compared to gradient-based solvers like fmincon.
Gradient-based solvers can step out of the feasibility region to get a gradient or gradient estimate.
Furthermore, if the problem characteristics have a high discontinuity on the feasibility bounds, they might also have some simulation effects and "noisiness" the global optimization solvers are more robust against.
If you have to use solvers like fmincon, adapt the objective function to include an early feasibility check and return NaN or Inf if not feasible. These values are treated specially in most solvers and they attempt a different iterative step then.
See:
