commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gilles Sadowski <>
Subject Re: [math] Monitoring iterative algorithms
Date Sat, 10 Sep 2011 17:57:18 GMT

> Thanks to you both for your review.

Unfortunately, I didn't have the time to thoroughly read the code.

> >
> > 0) maybe incrementIterationCount in the manager should be called
> > startIteration
> >
> OK
> >
> > 1) I guess TooManyEvaluations is the only thing left to throw, but
> > MaxIterationsExceeded or even something new like IllegalIteration
> > might make sense here (bad name, but once we introduce
> > StoppingCriteria, something like that will make sense).
> >
> As I said, TooManyEvaluations was just temporary. For the time being,
> I wanted to avoid the burden of defining a new exception with
> localized messages, until we agreed on the general outline. I would
> have defined a TooManyIterationsException in the end, but I think I
> like Gilles solution much better. This would avoid defining a new
> exception which would not be very instructive in any case. Much better
> to define a particular exception for the particular type of iterative
> algorithm.

I did not mean to imply that "TooManyIterationsException" would not be
useful. The intention was only to point out that a class using the
"Incrementor" is not restricted to deal with "MaxCountExceededException".
The example is the optimizers base class were "MaxCountExceededException"
is caught just to rethrow "TooManyEvaluationsException" (which is the
exception that reflects that function evaluations are being counted).

So, in the case of an "IterationManager", it looks like the appropriate
exception is indeed "TooManyIterationsException" (if indeed that is what is
being counted).
Note that I'm not saying that it won't be better to let specific algorithms
define the best exception to be thrown; however, I wonder, then, what's the
role of the "iteration" manager... [See below, too.]
When I refactored the optimizers (and solvers), I also switched from
counting _algorithm iterations_ to counting _function evaluations_, the
main rationale being that it made it possible to compare the count across
different algorithms.
>From what you said above, I'm just worried that you are going to rediscover
the same thing about iterative algorithms...

> >
> > 2) It is tempting to go ahead and define the StoppingCondition and
> > add it as a constructor parameter for the manager.
> >
> In fact, that's the purpose of the shouldStop() method. By default, it
> returns false, but you can override it, which effectively allows you
> to define a custom stopping criterion, without having to define a
> general framework for stopping criteria, which previous discussions
> showed it would be difficult to do... So I would say that we do not
> need to add a new constructor parameter. What do you think?
> >
> > 3) Incrementor is a little crippled not exposing a constructor with
> > the max  - could be we should add that and use it in the manager.
> >
> > 4) Similarly Incrementor could expose a hasMore() or somesuch, which
> > would provide a meaningful default for shouldStop and also provide
> > the basis for an iterationsExhausted event.
> >
> I should first mention that I've tried the present framework with
> iterative linear solvers, just to check things worked properly. The
> way I see things is as follows. As Gilles mentioned in a previous
> thread, a default stopping criterion *should* be embedded into the
> iterative algorithm. The reason for this is twofold: i. simplify most
> user's life, and ii. allow for optimized implementation of these
> stopping criteria. Regarding point ii., computation of the norm of the
> residual comes as a by-product of the Conjugate Gradient method, while
> evaluation by a custom stopping criterion would require an extra
> matrix-vector product *at each iteration*.
> Having in mind this, I decided that IterationManager.shouldStop()
> should provide an *additional* stopping criterion, meaning that the
> iterations are stopped if one of these conditions are fulfilled
> 1. maximum number of iterations reached ===> throws an exception,
> already handled by the manager (nothing to do with shouldStop())
> 2. the default stopping criterion is fulfilled
> 3. manager.shouldStop() returns true (which it does not in the default
> implementation, but that can be overriden).
> It should be noted that bypassing the default stopping criterion
> should be fairly easy, by providing "impossible" tolerance
> requirements. Then only the custom criterion would be checked.
> As I said, I've implemented this into my CG, it leads to fairly easily
> readable code (but certainly improvable, too).
> So what do you think of this way of thinking of stopping criteria? It
> seems to me that it is a very general framework, since it does not
> define any framework at all. It just opens a door to let some external
> objects inform the Iterative Algorithm that it should stop. Would it
> be regarded as acceptable design, or very ugly trick?
> >
> > 5) It may be extra noise and I know we need to be careful with this,
> > but a fireIterationStarted source might be useful in some contexts.
> >
> If I understand correctly, here is what you would like to have in a
> typical iterative algorithm
> {code}
> // Do initialization work
> manager.fireInitializationEvent()
> while(true){
>     manager.fireIterationStarted()
>     // do some work
>     manager.fireIterationPerformed()
> }
> manager.fireTerminationEvent()
> // do some closing work and return
> {code}
> I have no objection to that. However, do we require that *all* these
> events are fired by *all* iterative algorithms, or only by iterative
> algorithms where it is thought meaningful/useful?

I still don't like the confusion between "managing" and "monitoring" because
I'm afraid that it could lead to code that is hard to understand.
The above code looks more like a monitor/observer while the "shouldStop"
method belongs to a manager.
It might well be that both manager and iterator work quite similarly (e.g.
actions are triggered by events) but it seems to me that maintaining a
strict separation will allow easier evolution, if need be.
In fact, we should be quite sure that it is not better that the manager part
cannot be simply handled by a base class (as for the solvers and the
optimizers hierarchies). On the other hand, your manager might be the first
step to "externalize" the "counting part" for all the algorithms in CM, e.g.
solvers and optimizers would also use it for their evaluation counting. It
should then be renamed to something like "CounterManager".
However, is it better to have an external class for this rather simple task
rather than enclosing it in the base class of each family of algorithms?

Sorry about raising so much doubt, but I think that we should really be
careful that CM code does not become like a GUI code. :-}


To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message