Optimization of an objective function with noise I want to estimate the parameters that minimize a multivariate function with noise based on realized observations.
As a simple example, say I have observed the univariate sample below:

The samples were generated from a quadratic function plus noise, but in general the function will be unknown and I don't want to make any assumptions about it other than it is "smooth".  In this case, the function at $x \approx 5.8$ happens to be the minimum, but I want to make a statistical argument that the function is minimized at $x=5$.
How should I approach this? Should I fit some kind of nonparametric model to the sample data, and then optimize the fitted, smoothed values? Or are there algorithms that tackle the optimization of noisy function directly?
 A: If you truly have a smooth function with noise there are many ways to fit it.  Parametric models linear and nonlinear are possibilities, but based on how you ask the question it sounds like you are looking for some sort of nonparametric regression.  I think splines and loess are options.  In the end, you are searching for a minimum though.  For parametric models, local and global minima can be estimated and confidence intervals constructed for them. In the nonparametric situation, Bill Huber described a procedure in his answer to a similar question on CV involving time series data.  I think the idea can apply to your problem as well.
But the way you pose the problem is strange and contradictory.  If you have a model for multivariate data with noise without having a way to perfectly filter out the noise you cannot know exactly where the minimum is.  No matter what fitting technique you use you can only approximate the point where the minimum occurs.  If your estimate is 5.8 the confidence interval could in a certain statistical sense rule out 5 given sufficient data but it could never prove that the minimum is at 5 and your data really seems to be telling you otherwise.  Maybe there is an assumption you are making that you haven't told us about.
Now that the picture is clear and you have edited your question,
I see that since the data is simulated you know the truth.  The true model is a quadratic function that has a U shape and hence has a unique global minimum at 5.  Even a statistical technique that assumes a quadratic model with that much noise will give you an estimate different from 5. Nonparametric models that make less restrictive assumptions will probably do worse.
For real data as I said you can't perfectly separate the signal from the noise and you will never get an 'exact right" answer.  There may be models that can estimate the minimum and be consistent in a probabilistic sense but not perfect for any finite sample size.
A: I also believe that Michael's idea about lo(w)ess smoothing might be the obvious answer. That is if you feel confident enough to make assumptions about the smoothness of your underlying function.
Nevertheless, your "smoothness with noise" optimization problem can still get tricky and send a gradient based solver in local optima even in the loess profiled function. 
If the objective function is low dimensional, you don't want to assume any smoothness properties and has a "low" evaluation cost you might want to use a Simulated Annealing (a random search practically) to get good estimates for the estimation of parameters. It is dead easy to implement anyway and you save yourself the worries of "smoothness".
(Sorry I just saw you accepted the previous answer!)
