The POTM :: View topic

Posted: Mon Mar 27, 2006 3:07 pm

Peoples:

I'm looking for some help with a problem that I have at work. This is not for a POTM problem, unfortunately - POTM is much more fun than work.

I have a function of six variables. You can think of it as a C function. It takes six variables and returns a float. Each of the six variables can take a value between -1.1 and +1.1. I am looking for a fast (key word: fast) way of minimizing the value returned from this function. That is, I can change any or all of the six values passed into this function to get a different result. How can I quickly find the values of the 6 parameters that minimize the result.

I currently have some code that works. It is a very brain-dead approach. It runs in about 0.15 seconds (150 mili-seconds). I am hoping to reduce that by one order of magnitude (0.015 seconds (15 mili-seconds)).

If you have any ideas, please reply either here or by e-mail (PBanta@Yahoo.Com).

Thanks in advance,
Paul

Posted: Mon Mar 27, 2006 4:30 pm

It tends to depend on your function. Take a look at http://en.wikipedia.org/wiki/Optimization_%28mathematics%29
If your function is fairly smooth, you'll usually do some "guessing" to find areas that seem to be near good local minimums, and than some more sophisticated technique to refine the best guesses.

So, for instance, if I wanted to maximize Elevation(latitude, longitude), I might do an exhaustive search using a grid of about 100km on a side, and then use a gradient method to refine the best results of the exhaustive search. This wouldn't give me the coordinates of Mt Everest (unless I was pretty lucky), but it would probably get me to a respectable peak in a major mountain range.

As you gain more knowledge about the shape of your function, you may be able to find a better search function.

HTH

Posted: Tue Mar 28, 2006 1:16 am

Do you know whether there is a (single) global minimum or is it possible to have local minima ? In the latter case the method mentioned by billybob (as he already mentioned) or all the other standard methods may get stuck in a local minimum.

A nice thing to prove would be that the function is convex. Then, if the function has a minimum, this is a global one.

Standard methods in the differential case are "method of the steepest descent/spacer-step method" (f needs to be differentiable once) or the multi-dimensional variant of the Newton method (f needs to be two-times differentiable) or a combination of both. These are fairly standard, every good book about non-linear optimization should cover these algorithms.

Stefan

Posted: Tue Mar 28, 2006 1:20 pm

BillyBob, Stefan:

Thank you for your reply's.

I don't know the answer to your questions: Is ther a single minimum? Is f differentiable? But I will find out and proceed according to your suggestions.

I tell ya. I got my Computer Science degree 20 years ago and have been writing software ever since. But problems like these make me realize just how dated my CS knowledge really is. I need to go back to school. Ugh.

Thanks again,
Paul

P.S. BillyBob. Didn't you win the "Nuts" POTM a while back? I came in third or fourth in that one but haven't had time to enter since then. As I recall you had this amazingly fast algorithm that ran in a total of 12 seconds for all three boards combined. Everyone else was in the tens of thousands of second. Great job. Was that you or do I have my history wrong?

Posted: Tue Mar 28, 2006 3:11 pm

potm junkie wrote:

P.S. BillyBob. Didn't you win the "Nuts" POTM a while back? I came in third or fourth in that one but haven't had time to enter since then. As I recall you had this amazingly fast algorithm that ran in a total of 12 seconds for all three boards combined. Everyone else was in the tens of thousands of second. Great job. Was that you or do I have my history wrong?

No, I was second in SOLO, and near the bottom in MULTI. Xavier had the amazingly fast algorithm.

It is possible (not probable) that my code was faster than his on one or two of the first-round boards (it was faster on the system test) because it sometimes recognized optimal solutions and then stopped looking. I don't see times for individual boards, just for the rounds.

Posted: Tue Mar 28, 2006 9:54 pm

potm junkie wrote:

I don't know the answer to your questions: Is ther a single minimum? Is f differentiable? But I will find out and proceed according to your suggestions.

In the case of no information on the function (i.e., a black box function) I
have had good results with Particle Swarm Optimization (PSO). This is an
evolutionary algorithm which doesn't depend on known derivatives or other
niceties (although it works better if the function is somewhat continuous).

I'm not exactly sure how fast it will work, but there is always a tradeoff
between the information you have on the function, the computing time
you allow, and the quality of the result. Except for a rather restricted setting
you can't expect an optimal (as opposed to a good) solution.

There's a link to a description of PSO off the Wikipedia optimization page
mentioned above.

Sven.