commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Sébastien Brisard <sebastien.bris...@m4x.org>
Subject Re: [math] Testing for convergence in iterative algorithms
Date Wed, 10 Aug 2011 02:45:55 GMT
>
> The tricky bit here is a) how to encapsulate state in a generic way
> that has enough substance to it to be actually useful and b)
> similarly how to do the same for convergence.  I am probably too
> influenced by the topological connotation of the latter term which
> makes it seem basically different to me from what we have in the GA,
> where we are not really trying to engineer convergence of a sequence
> in any topological space.  But it could be they can rightly be seen
> as the same and Population in the GA should be a sublcass of
> whatever we end up calling iterative algorithm state.
>
> Another tricky bit is that in some of the examples you gave, history
> as well as current state must be available to the StoppingCondition
> - so just passing it current state is not enough.   It might
> actually be better for the StoppingCondition to be what you are
> calling a monitor - an event listener that can subscribe to the
> events carrying the information that it needs.
>
> As I said on the other thread, I think in any case a generic event
> framework to support the "monitoring" requirement would be a good
> thing to develop.
>
> Phil
Hi,
this takes us back to a discussion we had on JIRA: is a stopping
criterion a kind of monitor? Gilles argued that the two concepts
should be distinguished, and a default stopping criterion should be
hard coded in the iterative algorithm itself. I agree with that view,
since the default stopping criterion would then be highly optimized.
As for some stopping criteria requiring more than one state (e.g state
at times t and t-1), don't you think it should be the responsibility
of the convergence checker itself to store previous values of the
state. Let me explain myself. I might want to design a special
stopping criterion wich would work as follows:
  - take the last say three states of the iterative algorithm: x[n],
x[n-1], x[n-2],
  - extrapolate a "converged" state, based on these values y[n] =
extrapolate(x[n], x[n-1], x[n-2])
  - check for convergence of the extrapolated values abs(y[n]-y[n-1]) <= eps ?
As you see, each call to the checker would require the last *three*
states. This is endless! So I think the convergence checker itself
should store the previous states as needed. This way, we could have a
generic ConvergenceChecker

public interface ConvergenceChecker<State>{
  public boolean hasConverged(State s);
}

What do you think of this design? On a more tentative side, here is
what an IterativeAlgorithm could look like

public interface IterativeAlgorithm<State>{
  public boolean isIterating();

  public int getIteration();

  public State getState();

  public int getMaximumNumberOfIterations();
}


As you can see, I haven't dared to try to put Observers/Listeners into
that... BTW, GSL might be worth looking into in order to see what
design they chose. I'll look into it.
Sebastien

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


Mime
View raw message