2

I am using nloptr in R, however, I want to give my model more freedom since the best solution and avoid overfitting. I have described my problem earlier in this question:

nloptr(x0, eval_f, eval_grad_f = NULL, lb = NULL, ub = NULL, 
       eval_g_ineq = NULL, eval_jac_g_ineq = NULL, eval_g_eq = NULL, 
       eval_jac_g_eq = NULL, opts = list(), ... )

Basically I have a non-linear problem to solve. I have a function to minimize and some non-linear constrains. But I don't want to use the best found solution because it overfits the in sample data and gives me extreme values. Hence I want to find N best solutions and then choose ones I want.

So now I am wondering is there a way of finding N best solutions which nloptr finds during the iteration. Are there any other ways of doing this except nloptr?

3
  • What's the definition of "the second best solution"? Lowest local minimum that is not a global minimum? Or some point close to a global munimum, but not a local minimum? Anything else? Some sort of strict definition is required here. I understand your intention, though.
    – tonytonov
    Feb 27, 2014 at 12:38
  • @tonytonov in my case it doesn't really matter. it can be any set of solutions which gives more optimal solutions than starting values. As I understand nloptr goes through a number of iterations finding the optimal one, hence I was wondering if I can take N best ones (closest ones to the final solution). thanks
    – mm441
    Feb 27, 2014 at 13:20
  • 1
    Just an option: take a random start and adjust opts: limit iterations count or convergence tolerance, you will get close but (hopefully) different solutions.
    – tonytonov
    Feb 27, 2014 at 13:30

1 Answer 1

2

This is not really an answer, but rather a long comment, which I hope will be helpful.

I agree with @tonytonov that you should better define "second best" and your general needs. regardless, to get N different solutions, that are not just very near each other, I would run nloptr iteratively, each time with a slightly different target function, each time adding a penalty for being near the previous solution. here is an example:

sols = list()
evalf= list(eval_f)
for (i in 1:N) {
    sols[i] = nloptr(x0,evalf[[i]],...)
    # now creating a new evaluation function which adds a log(distance) penalty to the
    # last solution
    evalf[[i+1]] = function(x) {evalf[[i]](x)-log(sum((x-sols[i]$solution)^2))}
}

you can think of a different penalty of course, the idea is to add a big big penalty for being very close to an existing solution, but once you get relatively far from it (you should know, what does it mean to be far enough - this is context specific), the penalty is relatively flat, and hence does not affect the original minimum points. you should of course check that the last solution exists, and probably change the starting point (x0) from one iteration to another, but you get the point, I think.

More generally, as you try to avoid overfitting, I would think of adding a penalty to your eval function in the first place. For example, a sign of overfitting in regression analysis is the magnitude of the coefficients, so it is typical to try minimzing not the square root of error (the typical OLS method) in determining the regression estimation, but rather the square root of error + the sum of coefficients (normalized in some way), which create a preference for small coefficients, and hence decrease the likelihood of overfitting.

I know very little on your specific problem, but maybe you can come up with some "penalty" function that will decrease overfitting when minimized.

Another approach, if your eval_f depends on data, would be to use the same evaluation function but on bootstrap subsamples of your data. each time you get a differen minimum (because of the different sample). you get N such solutions and you can average them up or do anything you want to generate a non-overfitting solution (now the solution does not overfit the data, because each solution is based on different part of the data).

I hope it helps.

1
  • Nice idea, I have to say!
    – tonytonov
    Feb 27, 2014 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.