nmsimplex2

nmsimplex2

[Tuomo Keskitalo]

Hi,

a faster simplex mininimser gsl_multimin_fminimizer_nmsimplex2 (which is 
O(N) instead of O(N^2), according to NEWS) was added to GSL-1.12. Is 
there any reference or more information about this algorithm (besides 
the source code)?

-- 
Tuomo.Keskitalo@iki.fi
http://iki.fi/tuomo.keskitalo

Re: nmsimplex2

[Brian Gough]

At Thu, 06 Aug 2009 16:58:13 +0300,
Tuomo Keskitalo wrote:
> a faster simplex mininimser gsl_multimin_fminimizer_nmsimplex2 (which is 
> O(N) instead of O(N^2), according to NEWS) was added to GSL-1.12. Is 
> there any reference or more information about this algorithm (besides 
> the source code)?

It's the same algorithm but the implementation removes some
unnecessary computation.  The centre and size are updated from the
change in the selected vertex rather than recomputed from scratch.
Otherwise, the results should be identical.

There was a bug that was fixed a few days which did cause some
differences, but I think it should be ok now.

-- 
Brian Gough

Re: nmsimplex2

[Tuomo Keskitalo]

[-- Attachment #1: Type: text/plain, Size: 582 bytes --]

On 08/07/2009 12:18 PM, Brian Gough wrote:

> It's the same algorithm but the implementation removes some
> unnecessary computation.  The centre and size are updated from the
> change in the selected vertex rather than recomputed from scratch.
> Otherwise, the results should be identical.

Ok. I misunderstood the explanation in the manual to mean that 
nmsimplex2 would somehow need fewer optimisation steps. Perhaps the 
attached patch makes it clear? The patch was generated with command
git format-patch origin..master

-- 
Tuomo.Keskitalo@iki.fi
http://iki.fi/tuomo.keskitalo

[-- Attachment #2: 0001-Clarification-of-nmsimplex2-added-to-documentation.patch --]
[-- Type: text/x-patch, Size: 1059 bytes --]

From 19d9b6b429e1bf46596b42829184f5c4cfa6391d Mon Sep 17 00:00:00 2001
From: Tuomo Keskitalo <tkeskita@pulmunen.(none)>
Date: Fri, 7 Aug 2009 16:20:56 +0300
Subject: [PATCH] Clarification of nmsimplex2 added to documentation

---
 doc/multimin.texi |    4 +++-
 1 files changed, 3 insertions(+), 1 deletions(-)

diff --git a/doc/multimin.texi b/doc/multimin.texi
index cc2c607..c1e24ed 100644
--- a/doc/multimin.texi
+++ b/doc/multimin.texi
@@ -484,7 +484,9 @@ function @code{gsl_multimin_fminimizer_size}.
 
 The @code{nmsimplex2} version of this minimiser is a new @math{O(N)}
 implementation of the earlier @math{O(N^2)} @code{nmsimplex}
-minimiser.  It calculates the size of simplex as the @sc{rms} distance
+minimiser. The minimisation algorithm is the same, but the improved
+code makes @code{nmsimplex2} more efficient for large dimension
+problems. It calculates the size of simplex as the @sc{rms} distance
 of each vertex from the center rather than the mean distance, which
 has the advantage of allowing a linear update.
 @end deffn
-- 
1.5.6.5

Re: nmsimplex2

[Brian Gough]

At Fri, 07 Aug 2009 16:41:55 +0300,
Tuomo Keskitalo wrote:
> Ok. I misunderstood the explanation in the manual to mean that 
> nmsimplex2 would somehow need fewer optimisation steps. Perhaps the 
> attached patch makes it clear? The patch was generated with command
> git format-patch origin..master

Thanks, I will change the wording to something like that.