SDDS ToolKit Programs and Libraries for C and Python
Loading...
Searching...
No Matches
Functions
gridopt.c File Reference

Detailed Description

Functions for performing grid search and random search minimization on an N-dimensional function.

This file provides several methods for locating the minimum of a function that may be expensive or complicated to evaluate. The methods include:

  • grid_search_min(): Systematically samples the parameter space at fixed intervals.
  • grid_sample_min(): Randomly samples a grid of points in the parameter space.
  • randomSampleMin(): Selects random points in the parameter space to find a suitable starting point.
  • randomWalkMin(): Performs a random walk starting from a given point, potentially refining a solution. Additionally, optimAbort() can signal an external abort condition to halt the search processes.
Copyright
  • (c) 2002 The University of Chicago, as Operator of Argonne National Laboratory.
  • (c) 2002 The Regents of the University of California, as Operator of Los Alamos National Laboratory.
License
This file is distributed under the terms of the Software License Agreement found in the file LICENSE included with this distribution.
Author
M. Borland, R. Soliday, Y. Wang

Definition in file gridopt.c.

#include "mdb.h"

Go to the source code of this file.

Functions

static void clearOptimAbort (void)
 
static long optimAbortRequested (void)
 
long optimAbort (long abort)
 Set or query the abort condition for optimization routines.
 
long grid_search_min (double *best_result, double *xReturn, double *lower, double *upper, double *step, long n_dimen, double target, double(*func)(double *x, long *invalid))
 Perform a grid search to find the minimum of a given function.
 
long grid_sample_min (double *best_result, double *xReturn, double *lower, double *upper, double *step, long n_dimen, double target, double(*func)(double *x, long *invalid), double sample_fraction, double(*random_f)(long iseed))
 Perform a partial (sampled) grid search to find the minimum of a function.
 
long randomSampleMin (double *best_result, double *xReturn, double *lower, double *upper, long n_dimen, double target, double(*func)(double *x, long *invalid), long nSamples, double(*random_f)(long iseed))
 Randomly sample the parameter space to find a minimum.
 
long randomWalkMin (double *best_result, double *xReturn, double *lower, double *upper, double *stepSize, long n_dimen, double target, double(*func)(double *x, long *invalid), long nSamples, double(*random_f)(long iseed))
 Perform a random walk starting from a given point to find a function minimum.
 

Function Documentation

◆ clearOptimAbort()

static void clearOptimAbort ( void )
static

Definition at line 30 of file gridopt.c.

30 {
31 mdb_thread_lock(&optimFlagsLock);
32 optimFlags &= ~OPTIM_ABORT;
33 mdb_thread_unlock(&optimFlagsLock);
34}

◆ grid_sample_min()

long grid_sample_min ( double * best_result,
double * xReturn,
double * lower,
double * upper,
double * step,
long n_dimen,
double target,
double(* func )(double *x, long *invalid),
double sample_fraction,
double(* random_f )(long iseed) )

Perform a partial (sampled) grid search to find the minimum of a function.

This routine performs a grid-based search similar to grid_search_min(), but only evaluates a fraction of the points, chosen randomly. It returns the best found minimum and updates xReturn with the coordinates of that minimum.

Parameters
best_resultPointer to a double that will store the best function value found.
xReturnPointer to an array that will be updated with the coordinates of the minimum.
lowerArray specifying the lower bounds of each dimension.
upperArray specifying the upper bounds of each dimension.
stepArray specifying the step sizes for each dimension.
n_dimenThe number of dimensions.
targetThe target function value to achieve or surpass.
funcThe function to minimize.
sample_fractionThe fraction or number of points to sample from the grid.
random_fOptional random function for generating samples (default random_1).
Returns
Returns 1 if a minimum was found, otherwise 0.

Definition at line 177 of file gridopt.c.

187 {
188 static MDB_THREAD_LOCAL double *x = NULL, *best_x = NULL;
189 static MDB_THREAD_LOCAL long last_n_dimen = 0;
190 static MDB_THREAD_LOCAL long *index = NULL, *counter = NULL, *maxcount = NULL;
191 double result;
192 long flag, i, best_found;
193
194 clearOptimAbort();
195
196 if (random_f == NULL)
197 random_f = random_1;
198
199 if (last_n_dimen < n_dimen) {
200 if (x)
201 tfree(x);
202 if (best_x)
203 tfree(best_x);
204 if (index)
205 tfree(index);
206 if (counter)
207 tfree(counter);
208 if (maxcount)
209 tfree(maxcount);
210 x = tmalloc(sizeof(*x) * n_dimen);
211 best_x = tmalloc(sizeof(*best_x) * n_dimen);
212 index = tmalloc(sizeof(*index) * n_dimen);
213 counter = tmalloc(sizeof(*counter) * n_dimen);
214 maxcount = tmalloc(sizeof(*maxcount) * n_dimen);
215 last_n_dimen = n_dimen;
216 }
217
218 *best_result = DBL_MAX;
219 for (i = 0; i < n_dimen; i++) {
220 index[i] = i;
221 counter[i] = 0;
222 x[i] = lower[i];
223 if (lower[i] >= upper[i]) {
224 step[i] = 0;
225 maxcount[i] = 0;
226 } else {
227 maxcount[i] = (upper[i] - lower[i]) / step[i] + 1.5;
228 if (maxcount[i] <= 1)
229 maxcount[i] = 2;
230 step[i] = (upper[i] - lower[i]) / (maxcount[i] - 1);
231 }
232 }
233
234 if (sample_fraction >= 1) {
235 double npoints = 1;
236 for (i = 0; i < n_dimen; i++)
237 npoints *= maxcount[i];
238 sample_fraction /= npoints;
239 }
240
241 best_found = 0;
242 do {
243 if (sample_fraction < (*random_f)(1))
244 continue;
245 if ((result = (*func)(x, &flag)) < *best_result && flag == 0) {
246 *best_result = result;
247 for (i = 0; i < n_dimen; i++)
248 best_x[i] = x[i];
249 best_found = 1;
250 if (result < target)
251 break;
252 }
253 if (optimAbortRequested())
254 break;
255 } while (advance_values(x, index, lower, step, n_dimen, counter, maxcount, n_dimen) >= 0);
256
257 if (best_found)
258 for (i = 0; i < n_dimen; i++)
259 xReturn[i] = best_x[i];
260
261 return (best_found);
262}
tfree
int tfree(void *ptr)
Frees a memory block and records the deallocation if tracking is enabled.
Definition array.c:243
tmalloc
void * tmalloc(uint64_t size_of_block)
Allocates a memory block of the specified size with zero initialization.
Definition array.c:65
advance_values
long advance_values(double *value, long *value_index, double *initial, double *step, long n_values, long *counter, long *max_count, long n_indices)
Sequences an array of values systematically to cover an n-dimensional grid.
Definition counter.c:31
random_1
double random_1(long iseed)
Generate a uniform random double in [0,1] using a custom seed initialization.
Definition drand.c:230

◆ grid_search_min()

long grid_search_min ( double * best_result,
double * xReturn,
double * lower,
double * upper,
double * step,
long n_dimen,
double target,
double(* func )(double *x, long *invalid) )

Perform a grid search to find the minimum of a given function.

Given ranges and steps for each dimension, this function systematically evaluates the target function over a grid of points. It returns the best found minimum and updates xReturn with the coordinates of that minimum.

Parameters
best_resultPointer to a double that will store the best function value found.
xReturnPointer to an array that will be updated with the coordinates of the minimum.
lowerArray specifying the lower bounds of each dimension.
upperArray specifying the upper bounds of each dimension.
stepArray specifying the step sizes for each dimension.
n_dimenThe number of dimensions in the parameter space.
targetThe target function value to achieve or surpass.
funcA pointer to the function to minimize, taking coordinates and returning a value and validity flag.
Returns
Returns 1 if a minimum was found, otherwise 0.

Definition at line 85 of file gridopt.c.

93 {
94 static MDB_THREAD_LOCAL double *x = NULL, *best_x = NULL;
95 static MDB_THREAD_LOCAL long last_n_dimen = 0;
96 static MDB_THREAD_LOCAL long *index = NULL, *counter = NULL, *maxcount = NULL;
97 double result;
98 long flag, i, best_found;
99
100 clearOptimAbort();
101
102 if (last_n_dimen < n_dimen) {
103 if (x)
104 tfree(x);
105 if (best_x)
106 tfree(best_x);
107 if (index)
108 tfree(index);
109 if (counter)
110 tfree(counter);
111 if (maxcount)
112 tfree(maxcount);
113 x = tmalloc(sizeof(*x) * n_dimen);
114 best_x = tmalloc(sizeof(*best_x) * n_dimen);
115 index = tmalloc(sizeof(*index) * n_dimen);
116 counter = tmalloc(sizeof(*counter) * n_dimen);
117 maxcount = tmalloc(sizeof(*maxcount) * n_dimen);
118 last_n_dimen = n_dimen;
119 }
120
121 *best_result = DBL_MAX;
122 for (i = 0; i < n_dimen; i++) {
123 index[i] = i;
124 counter[i] = 0;
125 x[i] = lower[i];
126 if (lower[i] >= upper[i]) {
127 step[i] = 0;
128 maxcount[i] = 0;
129 } else {
130 maxcount[i] = (upper[i] - lower[i]) / step[i] + 1.5;
131 if (maxcount[i] <= 1)
132 maxcount[i] = 2;
133 step[i] = (upper[i] - lower[i]) / (maxcount[i] - 1);
134 }
135 }
136
137 best_found = 0;
138 do {
139 if ((result = (*func)(x, &flag)) < *best_result && flag == 0) {
140 *best_result = result;
141 for (i = 0; i < n_dimen; i++)
142 best_x[i] = x[i];
143 best_found = 1;
144 if (result < target)
145 break;
146 }
147 if (optimAbortRequested())
148 break;
149 } while (advance_values(x, index, lower, step, n_dimen, counter, maxcount, n_dimen) >= 0);
150
151 if (best_found)
152 for (i = 0; i < n_dimen; i++)
153 xReturn[i] = best_x[i];
154
155 return (best_found);
156}

◆ optimAbort()

long optimAbort ( long abort)

Set or query the abort condition for optimization routines.

When called with a non-zero parameter, this function sets an internal flag that signals the optimization routines to abort their search. When called with zero, it returns the current state of the abort flag.

Parameters
abortIf non-zero, sets the abort condition. If zero, simply queries it.
Returns
Returns 1 if the abort flag is set, otherwise 0.

Definition at line 55 of file gridopt.c.

55 {
56 long requested;
57
58 mdb_thread_lock(&optimFlagsLock);
59 if (abort) {
60 /* if zero, then operation is a query */
61 optimFlags |= OPTIM_ABORT;
62 }
63 requested = (optimFlags & OPTIM_ABORT) ? 1 : 0;
64 mdb_thread_unlock(&optimFlagsLock);
65 return requested;
66}

◆ optimAbortRequested()

static long optimAbortRequested ( void )
static

Definition at line 36 of file gridopt.c.

36 {
37 long requested;
38
39 mdb_thread_lock(&optimFlagsLock);
40 requested = (optimFlags & OPTIM_ABORT) ? 1 : 0;
41 mdb_thread_unlock(&optimFlagsLock);
42 return requested;
43}

◆ randomSampleMin()

long randomSampleMin ( double * best_result,
double * xReturn,
double * lower,
double * upper,
long n_dimen,
double target,
double(* func )(double *x, long *invalid),
long nSamples,
double(* random_f )(long iseed) )

Randomly sample the parameter space to find a minimum.

This routine randomly samples points in the given parameter space (defined by lower and upper bounds) for a specified number of samples. It returns the best found minimum and updates xReturn with its coordinates.

Parameters
best_resultPointer to a double that will store the best function value found.
xReturnPointer to an array that will be updated with the coordinates of the minimum.
lowerArray specifying the lower bounds of each dimension.
upperArray specifying the upper bounds of each dimension.
n_dimenThe number of dimensions.
targetThe target function value.
funcThe function to minimize.
nSamplesThe number of random samples to try.
random_fOptional random function for sampling (default random_1).
Returns
Returns 1 if a minimum was found, otherwise 0.

Definition at line 281 of file gridopt.c.

290 {
291 double *x, *xBest;
292 double result;
293 long flag, i, best_found = 0;
294
295 clearOptimAbort();
296 if (random_f == NULL)
297 random_f = random_1;
298
299 x = tmalloc(sizeof(*x) * n_dimen);
300 xBest = tmalloc(sizeof(*xBest) * n_dimen);
301 for (i = 0; i < n_dimen; i++)
302 xBest[i] = xReturn[i];
303 *best_result = DBL_MAX;
304 while (nSamples--) {
305 for (i = 0; i < n_dimen; i++)
306 x[i] = lower[i] + (upper[i] - lower[i]) * (*random_f)(0);
307 if ((result = (*func)(x, &flag)) < *best_result && flag == 0) {
308 *best_result = result;
309 for (i = 0; i < n_dimen; i++)
310 xBest[i] = x[i];
311 best_found = 1;
312 if (result < target)
313 break;
314 }
315 if (optimAbortRequested())
316 break;
317 }
318 if (best_found) {
319 for (i = 0; i < n_dimen; i++)
320 xReturn[i] = xBest[i];
321 }
322 free(x);
323 free(xBest);
324 return (best_found);
325}

◆ randomWalkMin()

long randomWalkMin ( double * best_result,
double * xReturn,
double * lower,
double * upper,
double * stepSize,
long n_dimen,
double target,
double(* func )(double *x, long *invalid),
long nSamples,
double(* random_f )(long iseed) )

Perform a random walk starting from a given point to find a function minimum.

This function starts at a user-supplied point and randomly perturbs it within given bounds and step sizes. It evaluates the function at each new point, seeking improvements. If a better minimum is found, xReturn is updated.

Parameters
best_resultPointer to a double that will store the best found function value.
xReturnPointer to an array with the starting coordinates, updated on success.
lowerArray specifying the lower bounds for each dimension.
upperArray specifying the upper bounds for each dimension.
stepSizeArray specifying the maximum step size for random perturbations in each dimension.
n_dimenThe number of dimensions.
targetThe target function value.
funcThe function to minimize.
nSamplesThe number of random steps to take.
random_fOptional random function (default random_1).
Returns
Returns 1 if a minimum was found, otherwise 0.

Definition at line 346 of file gridopt.c.

356 {
357 double *x, *xBest;
358 double result;
359 long flag, i, best_found = 0;
360
361 clearOptimAbort();
362
363 if (random_f == NULL)
364 random_f = random_1;
365
366 x = tmalloc(sizeof(*x) * n_dimen);
367 xBest = tmalloc(sizeof(*xBest) * n_dimen);
368 for (i = 0; i < n_dimen; i++)
369 xBest[i] = xReturn[i];
370 *best_result = DBL_MAX;
371 while (nSamples--) {
372 for (i = 0; i < n_dimen; i++) {
373 x[i] = xBest[i] + 2 * stepSize[i] * (0.5 - random_f(0));
374 if (lower && x[i] < lower[i])
375 x[i] = lower[i];
376 if (upper && x[i] > upper[i])
377 x[i] = upper[i];
378 }
379 result = (*func)(x, &flag);
380 if (flag == 0 && result < *best_result) {
381 *best_result = result;
382 for (i = 0; i < n_dimen; i++)
383 xBest[i] = x[i];
384 best_found = 1;
385 if (result < target)
386 break;
387 }
388 if (optimAbortRequested())
389 break;
390 }
391 if (best_found) {
392 for (i = 0; i < n_dimen; i++)
393 xReturn[i] = xBest[i];
394 }
395 free(x);
396 free(xBest);
397 return (best_found);
398}
Generated by doxygen 1.12.0