Global optimization of non-smooth function I have a number of functions (see for example two of them down below), and I need to find their global optimum for each of them. They are non-smooth, but they are always funnel-shaped, exhibiting a large minimum. If you zoom out, (e.g. when the x range is 0-100), the function "looks" smooth, so a convex optimization algorithm (golden section search) finds an approximate position for the global minimum quite easily and quickly. The problems arise when I need to refine that prediction, and zoom in (as shown). Theory shows these functions are, in fact, piecewise linear. What algorithm can I use to refine this prediction in a minimum amount of evaluations of the objective function, and with no gradient information?
 

I'd fit a spline, and find its minimum. Finding-inflection-points-in-spline-fitted-1d-data on SO has a link to nice python code to do this:
https://gist.github.com/pv/5504366 .
Added: why spline fit ? Splines can trade off conflicting goals:


*

*fit the data

*smooth out noise

*find (local) minimum points 


Splines fit a smooth curve to data, 
given either a number $N$ intermediate points ("knots")
or a desired degree of fit.
Either way, minima are easily found.
Splines are usually piecewise cubic, but in your case
you might try piecewise-linear splines.
