True BASIC Program to Find a Function Minimum

Using a Random Search Method

by Namir Shammas

The following program calculates the minimum point of a multi-variable function using random search method.

The pseudo-code for this algorithm is:

Given

1. The number of variables N
2. The array of minimum values XLo
3. The array of maximum values XHi
4. The maximum number of iterations per variable per cycle

Method

1. For I = 1 to N
2. Let X(I) = Random number in range XLo(I) and XHi(I)
3. Next I
4. F0 = F(X)
5. Copy Array X() into XBest()
6. Let flag C = 0
7. For I = 1 to N
8. For J = 1 to M
9. Let X(I) = Random number in range XLo(I) and XHi(I)
10. F1 = F(X)
11. If F1 > F0 then go to step 15
12. F0 = F1
13. Copy array X() into XBest()
14. Let flag C = 1
15. Next J
16. Next I
17. If flag C is 1 then go to step 6
18. Display array XBest() and F0

The program prompts you to enter:

1. Minimum value for each variable:.

2. Maximum value for each variable:.

3. The maximum number of iterations per cycle.

The program displays the following results:

1. The coordinates of the minimum value.

2. The minimum function value.

Here is a sample session to find the root of f(x) = (x1-1)^2 + (x2+4)^2 using ranges of [-10,10] for each variable and using 100 iterations per cycle. Remember your results are most likely to be different.

Here is the BASIC listing:

OPTION TYPO
OPTION NOLET

DEF FNF(X1,X2)
FNF=(X1-1)^2 + (X2+4)^2
END DEF

DECLARE NUMERIC N, I, J, M, F0, F1, MINSHOW
N = 2
MINSHOW = 1000
DIM XLO(1), XHI(1), X(1), X2(1)
MAT REDIM XLO(N), XHI(N), X(N), X2(N)
FOR I = 1 TO N
  PRINT "FOR X(";I;")"
  INPUT PROMPT "XLO? ": XLO(I)
  INPUT PROMPT "XHI? ": XHI(I)
NEXT I
INPUT PROMPT "MAX ITERS? ": M

! GET INITIAL VALUES
FOR I = 1 TO N
  X(I)= (XHI(I) - XLO(I)) * RND + XLO(I)
  X2(I) = X(I)
NEXT I

F0 = FNF(X(1),X(2))
FOR J = 1 TO M
  FOR I = 1 TO N
    X(I)= (XHI(I) - XLO(I)) * RND + XLO(I)
  NEXT I
  F1 = FNF(X(1),X(2))
  IF F1 < F0 THEN
    F0 = F1
    FOR I = 1 TO N
      X2(I) = X(I)
      IF M > MINSHOW THEN PRINT "X(";I;")=";X2(I);" ";
    NEXT I
    IF M > MINSHOW THEN PRINT
  END IF
NEXT J

! SHOW RESULTS
PRINT "MINIMUM AT"
FOR I = 1 TO N
  PRINT "X(";I;")=";X2(I)
NEXT I
PRINT "MIN FX="; F0
PRINT "END OF PROGRAM"
END

You can customize the above listing by changing the definition of function FNF. The current listing is set to solve the following equation:

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

The above function has a minimum at x1=1 and x2=-4.

If the number of variables in function FNF changes, then you need to change the value assigned to variable N.

An interesting function to test is Rosenbrook's function:

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

BACK

Copyright (c) Namir Shammas. All rights reserved.