HP-71B Program to Find 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 minimum 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.

PROMPT/DISPLAY

 ENTER/PRESS
> [RUN]
FOR X(1)  
XLO? -10[END LINE]
XHI? 10[END LINE]
FOR X(2)  
XLO? -10[END LINE]
XHI? 10[END LINE]
MAX ITERS? 100[END LINE]
WAIT ...  
(beep)  
MINIMUM AT [CONT]
X(1)= 0.89541 [CONT]
X(2)= -4.30338 [CONT]
MIN FX= 0.102977  

Here is the BASIC listing:

10 DEF FNF(X1,X2) = (X1-1)^2 + (X2+4)^2
20 N = 2
30 DIM X0(N), X9(N), X(N), Y(N)
40 For I = 1 TO N
50 DISP "FOR X(";I;")"
60 INPUT "XLO? ";X0(I)
70 INPUT "XHI? ";X9(I)
80 NEXT I
90 INPUT "MAX ITERS? ";M
100 FOR I = 1 TO N @ GOSUB 320 @ NEXT I
110 F0 = FNF(X(1),X(2))
120 GOSUB 340
130 DISP "WAIT..."
140 C = 0
150 FOR I = 1 TO N
160 FOR J = 1 TO M
170 GOSUB 320
180 F1 = FNF(X(1),X(2))
190 IF F1 > F0 THEN 230
200 F0 = F1
210 GOSUB 340
220 C = 1
230 NEXT J
240 NEXT I
250 IF C = 1 THEN 140
260 BEEP
270 DISP "MINIMUM AT" @ PAUSE
280 FOR I = 1 TO N
290 DISP "X(";I;")=";Y(I) @ PAUSE
300 NEXT I
310 DISP "MIN FX="; F0
315 END
319 REM GENERATE RANDOM VALUES
320 X(I)= (X9(I) - X0(I) * RND + X0(I)
330 RETURN
339 REM COPY ARRAY X INTO ARRAY Y
340 FOR K = 1 TO N @ Y(K) = X(K) @ NEXT K
350 RETURN
 

The program uses the variables shown in the following table:

Variable Name

Contents
N Number of variables
X() Array of variables
Y() Array of optimum values
X0() Array of minimum values
X9() Array of maximum values
I Iteration counter
J Iteration counter
K Iteration counter
F0 Minimum function value
F1 Function value at X
C Flag to determine loop iteration status

You can customize the above listing by changing the definition of function FNF in line 10. 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 in line 30. Make sure that the value of N does not exceed the array sizes in the DIM statement in line 20. If need be, increase the array dimensions to at least match 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.