Skip to content

GridOptimizer

core/OPT/optimizers/Grid.h        Extends: -

Template class to optimize a given ScalarField over an N-dimensional grid of equidistant nodes. 

template <unsigned int N> class GridOptimizer{ ... };

The class simulates the construction of an N-dimensional rectangle splitted along each interval according to a given grid step (the grid step can possibly differ for each dimension). The search is performed using an exhaustive search over the N-dimensional grid.

Warning

Since this optimization algorithm applies just an exhaustive search without any heuristic the resulting time complexity is exponential in the dimension of the grid N. The method can be very slow for values of N bigger than 2.

Methods

GridOptimizer(std::array<std::pair<double,double>, N> domain, std::array<double, N> steps, 
              const ScalarField<N>& objective_)

Constructor. It sets the shape of the domain where to search for the optimum of the objective as well as the grid step for each dimension.

Args Description
std::array<std::pair<double,double>,N>                         An array of exactly N pairs where pair represents infimum and superior limit of the interval along the -th dimension
std::array<double,N> steps An array of exactly N doubles where the -th element defines the grid step along the -th dimension
const ScalarField<N>& objective_ The objective function to optimize 
std::pair<SVector<N>, double> findMinimum() override;

Apply the search strategy to the objective passed as argument. Returns std::pair<SVector<N>,double> where the first element is the point in the grid where the minimum is reached while the second one is the actual minimum value reached by the objective.

Info

During the search no grid is actually stored in memory making the call at least memory efficient.

Examples

The following code finds the minimum of function over a grid of points defined in with grid step 0.01 for each dimension

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// define target to optimize: 2*x^2 - 2*y^2
std::function<double(SVector<2>)> g = [](SVector<2> x) -> double { 
       return 2*std::pow(x[0],2) - 2*std::pow(x[1],2); 
};

// create a scalar field
ScalarField<2> objective(g);

// perform a 2D grid optimization

// set optimization domain: [1,5] x [1,5]
std::array<std::pair<double, double>, 2> domain2D = {
    std::pair<double, double>(1,5), 
    std::pair<double, double>(1,5)
};

// set grid step size
std::array<double,2> step2D = {0.01, 0.01};

// create optimizer
GridOptimizer<2> opt2D(domain2D, lambda2D, objective);

// find minimum of g
std::pair<array<double, 2>,double> min_g = opt2D.findMinimum();