Mailing-List: contact dev-help@commons.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Commons Developers List" <dev@commons.apache.org>
Received-SPF: pass (athena.apache.org: domain of sebastien.brisard@gmail.com
 designates 209.85.220.171 as permitted sender)
MIME-Version: 1.0
Sender: sebastien.brisard@gmail.com
In-Reply-To: <4E40ED67.6030103@gmail.com>
References: 
 <CAGRH7Hr2nbk_SfO2_vePjsaVdNApen5Tt8DE0iKkzJWxfumVag@mail.gmail.com>
	<4E40536A.5030408@gmail.com>
	<CAGRH7HrGBdrEXQNKBC-3VqtO2dxoFvY-2rxyCbDYmZ8aUmZv4A@mail.gmail.com>
	<4E40ED67.6030103@gmail.com>
Date: Wed, 10 Aug 2011 04:45:55 +0200
Message-ID: 
 <CAGRH7HpUt4+YyzFOXqQ=e9tsiX6pKG0Mf3YPLf9Yt3gmphR2JQ@mail.gmail.com>
Subject: Re: [math] Testing for convergence in iterative algorithms
From: =?ISO-8859-1?Q?S=E9bastien_Brisard?= <sebastien.brisard@m4x.org>
To: Commons Developers List <dev@commons.apache.org>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

>
> 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. =A0I 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. =A0But 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. =A0 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] =3D
extrapolate(x[n], x[n-1], x[n-2])
  - check for convergence of the extrapolated values abs(y[n]-y[n-1]) <=3D =
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