From 8534c0b59bc5b1fcad2b270d4c2596708a62ba57 Mon Sep 17 00:00:00 2001 From: stevenj Date: Sun, 9 Nov 2008 13:19:16 -0500 Subject: [PATCH] fixed nelder-mead xtol/ftol stopping criteria, added diameter reduction test for subplex darcs-hash:20081109181916-c8de0-05b8623dcf3365df05997d136b849d8c02b6adc4.gz --- api/nlopt.c | 2 +- neldermead/neldermead.h | 2 +- neldermead/nldrmd.c | 29 ++++++++++++++++++++++++++--- 3 files changed, 28 insertions(+), 5 deletions(-) diff --git a/api/nlopt.c b/api/nlopt.c index ea2a438..2c08382 100644 --- a/api/nlopt.c +++ b/api/nlopt.c @@ -494,7 +494,7 @@ static nlopt_result nlopt_minimize_( if (!scale) return NLOPT_OUT_OF_MEMORY; for (i = 0; i < n; ++i) scale[i] = initial_step(1, lb+i, ub+i, x+i); - ret = nldrmd_minimize(n, f,f_data, lb,ub, x, minf, scale, &stop); + ret = nldrmd_minimize(n, f,f_data, lb,ub,x, minf,scale,&stop,0.); free(scale); return ret; } diff --git a/neldermead/neldermead.h b/neldermead/neldermead.h index 0b19d8d..9531d21 100644 --- a/neldermead/neldermead.h +++ b/neldermead/neldermead.h @@ -36,7 +36,7 @@ nlopt_result nldrmd_minimize(int n, nlopt_func f, void *f_data, double *x, /* in: initial guess, out: minimizer */ double *minf, const double *xstep, /* initial step sizes */ - nlopt_stopping *stop); + nlopt_stopping *stop, double psi); #ifdef __cplusplus } /* extern "C" */ diff --git a/neldermead/nldrmd.c b/neldermead/nldrmd.c index 2a2b5b9..b17adbf 100644 --- a/neldermead/nldrmd.c +++ b/neldermead/nldrmd.c @@ -65,12 +65,17 @@ static void pin(int n, double *x, const double *lb, const double *ub) { if (nlopt_stop_evals(stop)) { ret=NLOPT_MAXEVAL_REACHED; goto done; } \ if (nlopt_stop_time(stop)) { ret=NLOPT_MAXTIME_REACHED; goto done; } +/* if psi > 0, then it *replaces* xtol and ftol in stop with the condition + that the simplex diameter |xl - xh| must be reduced by a factor of psi + ... this is for when nldrmd is used within the subplex method; for + ordinary termination tests, set psi = 0. */ nlopt_result nldrmd_minimize(int n, nlopt_func f, void *f_data, const double *lb, const double *ub, /* bounds */ double *x, /* in: initial guess, out: minimizer */ double *minf, const double *xstep, /* initial step sizes */ - nlopt_stopping *stop) + nlopt_stopping *stop, + double psi) { double *pts; /* (n+1) x (n+1) array of n+1 points plus function val [0] */ double *c; /* centroid * n */ @@ -79,6 +84,7 @@ nlopt_result nldrmd_minimize(int n, nlopt_func f, void *f_data, int i, j; double ninv = 1.0 / n; nlopt_result ret = NLOPT_SUCCESS; + double init_diam = 0; pts = (double*) malloc(sizeof(double) * (n+1) * (n+1)); if (!pts) return NLOPT_OUT_OF_MEMORY; @@ -120,7 +126,13 @@ nlopt_result nldrmd_minimize(int n, nlopt_func f, void *f_data, double fh = high->k[0], *xh = high->k + 1; double fr; - if (nlopt_stop_f(stop, fl, fh)) ret = NLOPT_FTOL_REACHED; + if (init_diam == 0) /* initialize diam. for psi convergence test */ + for (i = 0; i < n; ++i) init_diam = fabs(xl[i] - xh[i]); + + if (psi <= 0 && nlopt_stop_f(stop, fl, fh)) { + ret = NLOPT_FTOL_REACHED; + goto done; + } /* compute centroid ... if we cared about the perfomance of this, we could do it iteratively by updating the centroid on @@ -146,7 +158,18 @@ nlopt_result nldrmd_minimize(int n, nlopt_func f, void *f_data, } } for (i = 0; i < n; ++i) xcur[i] += c[i]; - if (nlopt_stop_x(stop, c, xcur)) ret = NLOPT_XTOL_REACHED; + if (psi > 0) { + double diam = 0; + for (i = 0; i < n; ++i) diam += fabs(xl[i] - xh[i]); + if (diam < psi * init_diam) { + ret = NLOPT_XTOL_REACHED; + goto done; + } + } + else if (nlopt_stop_x(stop, c, xcur)) { + ret = NLOPT_XTOL_REACHED; + goto done; + } /* reflection */ for (i = 0; i < n; ++i) xcur[i] = c[i] + alpha * (c[i] - xh[i]); -- 2.30.2