MATLAB Program to Find A Function Minimum

Using a Random Drift Method

by Namir Shammas

The following program calculates the minimum point of a multi-variable function using random search method. The algorithm maintains the best point and uses a radius of search for each variable. Within the search radius, the method can locate a point that's a better candidate for the optimum. This search mechanism does not rely on a predetermined range and allows the best point to drift towards the optimum.

The function Random_Search3 has the following input parameters:

N - number of variables
X - array of initial guesses
SearchRadius - array of search radii
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:

XBest - 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 start at [0 0] with a radius vector of [1 1]. The search employs a maximum of 10000 iterations and a function tolerance of 1e-7:

>> [XBest,BestF,Iters]=Random_Search3(2, [0 0], [1 1], 1e-7, 10000, 'fx1')

XBest =

    2.0003 -5.0047

BestF =

    10.0000

Iters =

    10000

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

Here is the MATLAB listing:

function y=fx1(X, N)
  y = 10 + (X(1) - 2)^2 + (X(2) + 5)^2;
end

function [XBest,BestF,Iters]=Random_Search3(N, X, SearchRadius, Eps_Fx, MaxIter, myFx)
% Function performs multivariate optimization using the
% random 'drift' method.
%
% Input
%
% N - number of variables
% X - array of initial guesses
% SearchRaduis - array of search radius
% 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
%

XBest = X + SearchRadius * (rand(N) - 0.5);
BestF = feval(myFx, XBest, N);;
LastBestF = 100 * BestF + 100;

Iters = 0;

for k=1:MaxIter
  Iters = Iters + 1;
  X = XBest + SearchRadius * (rand(N) - 0.5);
  F = feval(myFx, X, N);
  if F < BestF
    XBest = X;
    LastBestF = BestF;
    BestF = F;
  end

  if abs(LastBestF - BestF) < Eps_Fx
    break
  end
end

BACK