Not all cost surfaces are equally likely to occur in real problems...
Also depends on the constraints, linear assignment (i.e. one job to one worker with a big matrix of cost for job to worker and you minimize the sum) has a polynomial complexity solution.
We are not talking about real problems here. Reality is so far from linear, so path dependent, so temporally dependent that by the time you gather 10 data points to try and match some function to the function is already outdated and error prone.
This is infinitely truer for when you try and find absolute maxima and minima and not just local ones.
