Each solver has what is called basins of attraction for each local solution. If you start the solver off in any point in one of the basins of attraction, then it will converge to essentially the "same" solution, i.e., that one associated with that basin of attraction. Not exactly of course, the convergence tolerance will be important, along with floating point arithmetic. This is a basic concept of optimizers.
Basins of attraction can be strangely shaped things, and they will not be nice, simply shaped regions. The set of basins in aggregate will fill the domain space of your objective, but they will not even be neatly shaped convex sets in general. They may have holes in them, with one basin entirely enclosed inside another. But if you can start at a point, and can move downhill in some way to a given solution along some path, then most optimzers will tend to arrive at the "same" solution from that point. Optimzers try to move basically downhill. (Actually, Nelder-Mead search tools try to move away from uphill. A subtle distinction, but not really that important here.)
There is no reson to assume that the basins of attraction are identical for each different solver. So if I start in the same point for each solver, I might get different answers, expecially if I start near the boundary of one of the basins. But it is probably a decent assumption that the basins are pretty similar in size and shape for most objectives, unless your objective function is something truly nasty looking.
So IF that last assumption is reasonably valid, then the same number of uniformly random start points for two different optimizers should result in ROUGHLY the same probability that you will find the global optimizer in the end.
So, no, you should not need MANY more random starts for any one method, but without extensively mapping the domain space for a specific objective, you cannot be positive what will happen. More random starts cannot hurt. And, again, the shape of that surface will be important, because that impacts the shape of the respective basins of attraction. Different optimization tool can be very different in speed of course, in the number of function evals needed to reach any given solution.
Best Answer