commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gilles Sadowski <gil...@harfang.homelinux.org>
Subject Re: [math] 902 Optimizers should return best discovered value in case of TooManyEvaluationsException
Date Tue, 20 Nov 2012 18:30:22 GMT
On Tue, Nov 20, 2012 at 11:59:07AM -0500, Konstantin Berlin wrote:
> 
> On Nov 20, 2012, at 7:56 AM, Gilles Sadowski <gilles@harfang.homelinux.org> wrote:
> 
> > On Tue, Nov 20, 2012 at 05:08:23AM -0500, Konstantin Berlin wrote:
> >> I am ok with option 2.
> > 
> > Thanks. I'll add new constructors if nobody has objections. Please note that
> > by using "custom" checkers (even those defined in CM), you make some
> > algorithms deviate from their "standard" behaviour.
> > 
> >> 
> >> I guess my issue goes to my problem with the general API. The number
> >> of iterations is a stopping condition, as well as all the other
> >> conditions that are for some reason called convergence conditions. The
> >> number of iterations condition is singled out as "bad", hence it
> >> throws an exception, while others don't through an exception, and I
> >> guess are considered "good".
> > 
> > Reaching the maximal count is "bad" because it means that the algorithm
> > could not fulfill the (other) input requirements.
> > The "maxEval" parameters was intended as a safe-guard to prevent the
> > algorithm from _unexpectedly_ running too long. If the user knows that it
> > takes a long time to find the solution with the required accuracy, he can
> > increase "maxEval".
> 
> My point is that termination based on a criteria that you actually gave yourself is not
an exception. It is expected behavior
> and should be treated as such.

The current interpretation of "maxEval" is: If the algorithm convergence
criteria are not satisfied after "maxEval" evaluations, it is considered a
failure (and an exception is raised).
I consider this safer than always return a value without the user knowing
whether it fulfills the requirements or not.

> There are other conditions that also prevent you from converging to a correct solution
of the requested
> tolerance. Like I mentioned, one such possible event is that you are not making enough
progress. That does not imply that you are some
> requested epsilon away from the minimum, but only says that you are getting there too
slowly.

And what happens when you call CM's "optimize" method in such cases?

> All tolerance conditions in some ways are about 
> a time constraint, otherwise you would always set them to maximum precision. I think
the exception should not be thrown.

Given the _definition_ of "maxEval", the exception must be thrown.

> Alternatively an exception should 
> be thrown if the target functions gets NaNs or throws an exception.
> I don't think these conditions are checked for right now.

Did you try?
CM does not interfere with the user's function; it's up to him that his
function behaves nicely. If it returns NaN, nasty things will occur a some
point, as usual. If it throws an exception, it will abort the execution, as
usual.

> 
> I agree that for some methods you can't tell, while for convex solvers you can look at
first-order optimization condition and so on. This information should be provided to the user
on termination of the optimization and not hidden.

An example?

> 
> > 
> > As I said previously, your request introduces a conflict: It becomes
> > possible that none of the convergence requirements is met.
> > 
> >> However, a stopping condition, even if you exclude the number of
> >> iterations condition, does not imply convergence, aka that you found
> >> an min point. In a convex solver you have to look at the first and
> >> second order optimality condition in order to declare "success". A
> >> typical stop of the algorithm could be that it has not made enough
> >> progress rather than found the min, but with the current framework
> >> this is also considered "good", with the user does not have a clue
> >> that something went bad unless they take the solution and start
> >> checking themselves.
> > 
> > But that's part of the behaviour inherent to some algorithm. However it will
> > terminate as it wishes (i.e. satisfying its internal convergence criteria).
> > 
> >> 
> >> That is why if you look at matlab fminunc, it contains about 5
> >> different flags for termination.
> > 
> > That would probably require a new API.
> > Can you give some examples of usage?
> > Concrete proposals are always welcome and would hopefully open a discussion.
> 
> I think the information provided on return by the optimizers should be reworked for the
better. This would require some thinking, so I will hold off on proposing something now, due
to limited time that I have to fully dedicate to this problem. I think MATLAB should be a
good guide on how to organize optimizations, since it has a very well regarded library. I
would be happy to comment on any proposals from people who might have some time to write them.

If you are not satisfied with the API, the initiative to make it better
is on you. :-)

> 
> On this note I would like to say that the directory structure of optimizers are somewhat
of a puzzle. The "general" directory should be renamed to "convex", or something like it.
In any case non-linear least-squares methods are not general methods, but a special case of
a newton-based convex optimization. I think the library can benefit from better organization
here.

You are perfectly right; it has already been pointed out several times.
This could be done in release 4.0.  Would you open a ticket on the bug
tracking system?

> 
> Perhaps something like derivative based vs. direct vs. linear.

"derivative based" cannot be a Java package name... ;-)

> 
> > 
> >> This probably goes along with the point in the 873 bug that talks
> >> about internal vs external criteria.
> > 
> > Not sure. There, "internal" or "external" (for lack of better words) are
> > both "legitimate". The number of iterations is not (IMHO), because it's
> > sort-of "unstable": If you increase the number of evaluations (or
> > iterations), you can get another solution.
> > I think that this difference in nature is a property that could serve to
> > define an API (as was done with the current one).
> > 
> 
> There are other "unstable" termination conditions, like I mentioned above. Throwing exception
in this one case only is misleading.

Please provide a concrete example of misleading behaviour.

> But in any case, termination of the algorithm based on a stopping condition is expected
behavior.

Fortunately, it can be easily implemented as proposed. So, we keep the
current semantics of "maxEval", while providing the feature you need.


Regards,
Gilles

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message