True BASIC Program to Find a Function Minimum

Using the Random Search Method

by Namir Shammas

The following program calculates the minimum point of a multi-variable function using a version of the random search method. This method starts with an initial point and a multi-dimensional search radius. The method updates the best point as points with lower function values are found. The algorithm does not employ ranges of values, allowing the best point to drift towards an optimum point.

The program prompts you to enter for each variable (i.e. dimension):

1. The initial value,

2. The random search radius.

The program also asks you to enter the function tolerance. The program uses this value to possible stop iterating when successive best function values are close enough.

The program displays intermediate values for the function and the variables. The program displays the following final results:

1. The coordinates of the minimum point.

2. The minimum function value.

3. The number of iterations

The current code finds the minimum for the following function:

f(x1,x2) = 10 + (x1 ^ 2 - 1) ^ 2 + (x2^2 - 2) ^ 2

Here is a sample session to solve for the optimum of the above function:

Here is the BASIC listing:

! Random Drift Optimization

OPTION TYPO
OPTION NOLET

DECLARE NUMERIC MAX_VARS, MAX_ITER
DECLARE NUMERIC N, I, J 
DECLARE NUMERIC F, XX 
DECLARE NUMERIC BestF, LastBestF, EPSF 
DECLARE NUMERIC Iter

Dim X(1), XBest(1) 
Dim Radius(1), InitVal(1) 

MAX_VARS = 2
MAX_ITER = 5000000

RANDOMIZE

SUB MyFx(X(), N, funRes) 
   LOCAL I
   
   funRes = 10
   For I = 1 To N
     funRes = funRes + (X(I) ^ 2 - I) ^ 2
   Next I
End Sub

!
! This method implements a random walk algorithm.
! The method starts with an initial point and a radius of search
! Random numbers are generated within the radius of search allowing
! for the current optimum to "drift" towards a minimum.
! THIS METHOD HAS NO PREDEFINED RANGES, making it more flexible
! to find an optimum, given enough iterations
!

MAT REDim X(MAX_VARS), XBest(MAX_VARS) 
MAT REDim Radius(MAX_VARS), InitVal(MAX_VARS) 

N = MAX_VARS
RANDOMIZE

For I = 1 To N
  PRINT "X(";I;")";
  INPUT InitVal(I)
  PRINT "Search Radius(";I;")";
  INPUT Radius(I)
  XBest(I) = InitVal(I)
Next I
INPUT PROMPT "Enter function tolerance? ": EPSF


! calculate and display function value at initial point
CALL MyFx(XBest, N, BestF)
LastBestF = SGN(B)*(100 + 100 * B)

Iter = 0
Do
  Iter = Iter + 1
  If Iter > MAX_ITER Then Exit Do 
  For I = 1 To N
    X(I) = XBest(I) + (Rnd - 0.5) * Radius(I)
    CALL MyFx(X, N, F)
    If F < BestF Then
      XBest(I) = X(I)
      LastBestF = BestF
      BestF = F
      PRINT "F = "; BestF;" ";
      For J = 1 To N
        PRINT "X(";J;")=";X(J);" ";
      Next J
      PRINT
      ! test function value convergence
      If Abs(BestF - LastBestF) < EPSF Then Exit Do
    End If
  Next I
Loop

PRINT "********FINAL RESULTS***********"
For I = 1 To N
  PRINT "X(";I;") = ";XBest(I)
Next I
PRINT "Function value =";BestF
PRINT "Number of iterations = "; Iter

END

BACK