Minimisation algorithm for a mix of discreet and continuous parameters?

I have a minimisation problem in which the parameters are a mix of integers and scalars. Some of the integers have a small range, around 0-10 but others range in the thousands. To give some context, these are all hyper-parameters of machine learning algorithms. At each iteration for a given set of parameters a series of CV and/or bootstrap tests are done to assess the merit of the parameter set.

Currently I am doing this using standard canned minimisation algorithms (specifically Nelder-Mead simplex) and faking the integer variables as continuous by doing two iterations for each value, one with the floor and the other the ceiling of the continuous value and linearly interpolating. It's crude and inefficient but at seems to at least 'work' in that the algorithm converges, eventually.

As you can imagine, the merit function iterations are expensive, so I don't want to be as wasteful as this process requires. I don't know of a standard way to deal with this kind of problem, but I can't imagine that it hasn't been addressed. Are there well known algorithms and implementations for this kind of problem?

-
What function are you trying to minimize? If it is linear in the parameters, you should look into Mixed Integer LPs: en.wikipedia.org/wiki/Linear_programming#Integer_unknowns –  Mathias Apr 28 '12 at 17:57
As stated the parameters are hyper-parameters of machine learning algorithms, so the 'function' is completlly non-analytic, and certainly not linear. –  Bogdanovist Apr 29 '12 at 12:22
Re-reading the last comment it comes across as a bit curt. That was unintentional. To clarify in more detail, the 'function' that is being optimised is a complex process and there is no hope of using a simplifying assumptions about the response. Essentially what is needed is an algorithm that will work when the function is a black box. Nelder-Mead simplex is what I usually use in a such a situation, but that operates on continuous variables only. –  Bogdanovist Apr 30 '12 at 3:03
No offense taken, but I appreciate the courtesy! Not being familiar with machine learning, I had no idea how the objective function to be minimized looks like. –  Mathias Apr 30 '12 at 4:45

It sounds like you need a derivative free method (since it seems you can't supply a gradient for your objective function). I guess your parameter space is not bounded since you are currently using Nelder-Mead. I'm not sure what software you're using but you should check out NOMAD which is "freely distributed under the GNU Lesser General Public License." NOMAD handles nonlinear functions of integers and/or real variables. In R the crs package provides an interface, see this.

-
You are correct, although some of the parameters are bounded which I faked up by artificially imposing large increases in the objective function value as a function of how far out of bound a value was. Very inefficient, but it work(ed)(s). I'll take a look at NOMAD, thanks. –  Bogdanovist Mar 11 at 4:16