True BASIC Program to Find a Function Minimum

Using a Direct Search Method

by Namir Shammas

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

The pseudo-code for this algorithm is:

Given

1. The number of variables N
2. The array of initial values X
3. The array of initial search steps S
4. The array of minimum search steps M

Method

1. F0 = F(X)
2. For I = 1 to N
3. Let X0 = X(I)
4. X(I) = X(I) + S(I)
5. If F(X) < F0 then go to step 10
6. Let X(I) = X0 - S(I)
7. If F(X) < F0 then go to step 11
8. X(I) = X0
9. If S(I) <= M(I) then Let S(I) = S(I) / 10
10. Go to step 12
11. F0 = F(X)
12. Next I
13. Let S0 = 0
14. For I = 1 to N
15. If S(I) >= M(I) then S0 = 1
16. Next I
17. If S0 > 0 Then go to step 2
18. Display array X()

The program prompts you to enter for each variable:

1. Guess for the minimum point.

2. Initial search step value.

3. The minimum search step value.

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 initial search steps of 0.1 for both variables, and minimum search steps of 0.001 for both variables:

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, X0, F0, F1, S0, I
DIM X(1), S(1), M(1)
N = 2
MAT REDIM X(N), S(N), M(N)
FOR I = 1 TO N
  PRINT "FOR X(";I;")"
  INPUT PROMPT "X? ": X(I)
  INPUT PROMPT "INIT STEP? ": S(I)
  INPUT PROMPT "MIN STEP? ": M(I)
NEXT I
! START MAIN LOOP
DO
  F0 = FNF(X(1),X(2))
  FOR I = 1 TO N
    ! PRINT X(1);" ";X(2)
    X0 = X(I)
    ! MOVE FORWARD
    X(I) = X(I) + S(I)
    F1 = FNF(X(1),X(2))
    IF F1 >= F0 THEN
      ! MOVE BACKWARD
      X(I) = X0 - S(I)
      F1 = FNF(X(1),X(2))
      IF F1 >= F0 THEN
        ! BACK TO ANCHOR
        X(I) = X0
        IF S(I) >= M(I) THEN
          S(I) = S(I) / 10
        END IF
      ELSE
        F0 = F1
      END IF
    ELSE
      F0 = F1
    END IF
  NEXT I
  S0 = 0
  FOR I = 1 TO N
    IF S(I) >= M(I) THEN S0 = 1
  NEXT I
LOOP WHILE S0 > 0

PRINT "MINIMUM AT:"
FOR I = 1 TO N
PRINT "X(";I;")=";X(I)
NEXT I
PRINT "MIN FX="; F0
END
 

If you uncomment the PRINT statement in the first FOR loop after the DO loop, you will able to watch the intermediate values during the iterations. You can view the intermediate values to study the minimum search progress for functions that have a minimum that is difficult to find.

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 you alter the number of variables in function FNF, then you also need to change the value assigned to variable N to reflect the new number of variables.

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.