On Dec 1, 2010, at 7:25 PM, Adam Openshaw wrote:
I see you have a method, nlopt_set_initial_step or
nlopt_set_initial_step1,
which you can use to set the initial step size. I'm wondering
though, is there
a way to set a fixed step size?
No, that is fundamentally not how these algorithms work.
My problem's variables are only (logically) able to be WHOLE
numbers, so all of
the optimization iterations that change my variables by very small
fractions of
a whole are a waste of time. Moreover, my problem contains a large
amount of
variables and constraints, so it would be ideal to eliminate these
wasted
iterations.
If you want an algorithm that explores only integer values of the
design parameters, that is called integer programming. Unfortunately,
integer programming is an extremely hard problem in general (in fact,
it is NP hard).
By allowing the optimization to use non-integer values, you are
solving what is called a "continuous relaxation" of your original
problem. The nice thing is that continuous-variable problems are
*much easier* than integer problems in many cases, and especially if
the function is concave. The basic advantage is that with non-integer
values you can move continuously "downhill" during minimization, and
you have a concept of a gradient (for differentiable functions),
whereas you can't do this for integer programming.
I wouldn't call the fractional steps a "waste" then---they are what
allow the algorithm to find an optimum (or at least a local optimum)
without exponential complexity.
Now, the problem with continuous relaxations is that they will in
general end up at an optimum that is not integer-valued. In this
case, you can do four things:
1) the non-integer optimum is at least an upper bound for your true
minimum (or a lower bound for the true maximum)
2) you can "round" the parameters to the nearest integers as a
heuristic solution; in some problems, this works well, although of
course it is not guaranteed
3) you can add a penalty term for non-integer values and re-optimize,
increasing the penalty each time. For example, see:
http://www.springerlink.com/content/6655218l30831538/
4) you can try to reformulate your problem so that non-integer values
are worthwhile and meaningful - this is the ideal solution.
Steven
_______________________________________________
NLopt-discuss mailing list
[email protected]
http://ab-initio.mit.edu/cgi-bin/mailman/listinfo/nlopt-discuss
