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

PROMPT/DISPLAY

 ENTER/PRESS
> [RUN]
FOR X(1)  
X? 0[END LINE]
S? 0.1[END LINE]
M? 0.001[END LINE]
FOR X(2)  
X? 0[END LINE]
S? 0.1[END LINE]
M? 0.001[END LINE]
PLEASE WAIT ...  
(beep)  
MINIMUM AT [CONT]
X(1)= 1 [CONT]
X(2)= -4 [CONT]
MIN FX= 0  

Here is the BASIC listing:

10 DEF FNF(X1,X2) = (X1-1)^2 + (X2+4)^2
20 N = 2
30 DIM X(N), S(N), M(N)
40 For I = 1 TO N
50 DISP "FOR X(";I;")"
60 INPUT "X? ";X(I)
70 INPUT "INIT STEP? ";S(I)
80 INPUT "MIN STEP? ";M(I)
90 NEXT I
100 F0 = FNF(X(1),X(2))
105 DISP "PLEASE WAIT..."
110 FOR I = 1 TO N
120 REM DISP X(1);" ";X(2)
130 X0 = X(I)
140 X(I) = X(I) + S(I)
150 F1 = FNF(X(1),X(2))
160 IF F1 < F0 THEN 230
170 X(I) = X0 - S(I)
180 F1 = FNF(X(1),X(2))
190 IF F1 < F0 THEN 230
200 X(I) = X0
210 IF S(I) >= M(I) THEN S(I) = S(I) / 10
220 GOTO 240
230 F0 = F1
240 NEXT I
250 S0 = 0
260 FOR I = 1 TO N
270 IF S(I) >= M(I) THEN S0 = 1
280 NEXT I
290 IF S0 > 0 THEN 110
295 BEEP
300 DISP "MINIMUM AT" @ PAUSE
310 FOR I = 1 TO N
320 DISP "X(";I;")=";X(I) @ PAUSE
330 NEXT I
340 DISP "MIN FX="; F0

If you remove the REM in line 120 you will able to watch the intermediate values during the iterations. This feature does come at the cost of slowing the program down. You can view the intermediate values to study the minimum search progress for functions that have a minimum that is difficult to find.

The program uses the variables shown in the following table:

Variable Name

Contents
N Number of variables
X() Array of minimums
S() Array of earch steps
M() Array of minimum search steps
I Iteration counter
F0 Minimum function value
F1 Function value at X
S0 Flag to determine loop iteration status
X0 Temporary value for X(I)

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