Is the perturbation a variable of the problem or a parameter that you specify beforehand?

If your function is convex a local optimum is a global optimum. There are global solvers for non convex functions ( e.g. By partitioning the space and using local solvers) but they are very computationally intensive and may not be able to guarantee optimality. A least square problem is convex though, unless you have some weird constraints.

Please let us know what code ends up working for you, and what type of problem you are solving.