MATLAB Program to Find A Function Minimum

Using a Grid Search Method

by Namir Shammas

The following program calculates the minimum point of a multi-variable function using the grid search method. This method performs a multi-dimensional grid search. The grid is defined by a multiple dimensions. Each dimension has a range of values. Each range is divided into a set of equal-value intervals. The multi-dimensional grid has a centroid which locates the optimum point. The search involves multiple passes. In each pass, the method local a node (point of intersection) with the least function value. This node becomes the new centroid and builds a smaller grid around it. Successive passes end up shrinking the multidimensional grid around the optimum.

The function Grid_Search has the following input parameters:

N - number of variables
XLo - array of lower values
XHi - array of higher values
NumDiv - array of number of divisions for each range
MinDeltaX - array of minimum ranges
Eps_Fx - tolerance for difference in successive function values
MaxIter - maximum number of iterations
myFx - name of the optimized function

The function generates the following output:

X - array of optimized variables
BestF - function value at optimum
Iters - number of iterations

Here is a sample session to find the optimum for the following function:

y = 10 + (X(1) - 2)^2 + (X(2) + 5)^2

The above function resides in file fx1.m. The search for the optimum 2 variables has the search range of [-10 -10] and [10 10] with a divisions vector of [4 5] and a minimum range vector of [1e-5 1e-5]. The search employs a maximum of 10000 iterations and a function tolerance of 1e-7:

>> [XBest,BestF,Iters]=Grid_Search(2, [-10 -10], [10 10], [4 4], [1e-5 1e-5], 1e-7, 10000, 'fx1')

XBest =

2.0001 -5.0000

BestF =

10.0000

Iters =

200

Notice how close the located optimum is to the actual one [-2 5]..

Here is the MATLAB listing:

function [XBest,BestF,Iters]=Grid_Search(N, XLo, XHi, NumDiv, MinDeltaX, Eps_Fx, MaxIter, myFx)
% Function performs multivariate optimization using the
% grid search.
%
% Input
%
% N - number of variables
% XLo - array of lower values
% XHi - array of higher values
% NumDiv - array of number of divisions along each dimension
% MinDeltaX - array of minimum search values for each variable
% Eps_Fx - tolerance for difference in successive function values
% MaxIter - maximum number of iterations
% myFx - name of the optimized function
%
% Output
%
% XBest - array of optimized variables
% BestF - function value at optimum
% Iters - number of iterations
%
Xcenter = (XHi + XLo) / 2;
XBest = Xcenter;
DeltaX = (XHi - XLo) ./ NumDiv;
BestF = feval(myFx, XBest, N);;
if BestF >= 0 
  LastBestF = BestF + 100;
else
  LastBestF = 100 - BestF;
end
X = XLo; % initial search value

Iters = 0;
bGoOn = 1;

while (bGoOn > 0) && (abs(BestF - LastBestF) > Eps_Fx) && (Iters <= MaxIter)

  bGoOn2 = 1;
  
  while bGoOn2 > 0 
  
    Iters = Iters + 1;
  
    F = feval(myFx, X, N);
    if F < BestF 
      LastBestF = BestF;
      BestF = F;
      XBest = X;
    end
    
    %*****************************************************
    % The next For loop implements a programming tricks
    % that simulated nested loops using just one For loop
    %*****************************************************
    % search next grid node
    for i = 1:N
      if X(i) >= XHi(i)
        if i < N
          X(i) = XLo(i);
        else
          bGoOn2 = 0;
          break
        end
      else
        X(i) = X(i) + DeltaX(i);
        break
      end
    end

  end % while bGoOn2 > 0 


  XCenter = XBest;
  DeltaX = DeltaX ./ NumDiv;  
  XLo = XCenter - DeltaX .* NumDiv / 2;
  XHi = XCenter + DeltaX .* NumDiv / 2;
  X = XLo; % set initial X

  bGoOn = 0;
  for i=1:N
    if DeltaX(i) > MinDeltaX(i)
      bGoOn = 1;
    end 
  end  
    
end % while bGoOn > 0 && () && ()

BACK