The following program calculates the minimum point of a multi-variable function using the grid search method. This method performs a multi-dimensional grid search. The grid is defined by a multiple dimensions. Each dimension has a range of values. Each range is divided into a set of equal-value intervals. The multi-dimensional grid has a centroid which locates the optimum point. The search involves multiple passes. In each pass, the method local a node (point of intersection) with the least function value. This node becomes the new centroid and builds a smaller grid around it. Successive passes end up shrinking the multidimensional grid around the optimum.

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

1. The values that define the lower and upper limits of a search range for a variable,

2. The number of divisions for a range.

3. The minimum range value, used to determine when to stop searching..

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. The first image shows the input:

The second image shows the output:

Here is the BASIC listing:

10 ! Grid Search Optimization 20 ! 30 ! Routine performs grid search. The iterations relocate the centroid to be the current optimum. 40 ! The routine srhinks the grid size in each iteration. 50 ! 60 ! 70 N = 2 80 I9 = 5000000 90 DIM N0(N) 100 DIM X(N), X9(N), X5(N) 110 DIM D(N), D0(N) 120 DIM L0(N), H1(N) 130 DISP "Grid Search Optimization" @ WAIT 3 140 For I = 1 To N 150 ! Get lower range 160 DISP "Low(";I;")"; 170 INPUT L0(I) 180 ! Get upper range 190 DISP "H1gh(";I;")"; 200 INPUT H1(I) 210 ! Calculate center 220 X5(I) = (L0(I) + H1(I)) / 2 230 ! Get number of divisions 240 DISP "Number of divisions for X(";I;")"; 250 INPUT N0(I) 260 ! Calculate initial search step 270 D(I) = (H1(I) - L0(I)) / N0(I) 280 ! Get minimum search step 290 DISP "Minimum search step for X(";I;")"; 300 INPUT D0(I) 310 X(I) = L0(I) ! set initial X 320 Next I 330 INPUT "Enter function tolerance? "; E 340 ! calculate and display function value at initial point 350 CALL MyFx(X5, N, B) 360 IF B > 0 THEN L = 100 + B ELSE L = B - 100 370 I0 = 0 380 REM DO1 390 REM DO2 400 I0 = I0 + 1 410 CALL MyFx(X, N, F) 420 If F >= B Then 480 430 L = B 440 B = F 450 For I = 1 To N 460 X9(I) = X(I) 470 Next I 480 REM ENDIF1 490 !***************************************************** 500 ! The next For loop implements a programming tricks 510 ! that simulated nested loops using just one For loop 520 !***************************************************** 530 ! search next grid node 540 For I = 1 To N 550 If X(I) < H1(I) Then 580 560 If I < N Then X(I) = L0(I) Else 650 570 GOTO 610 580 REM ELSE2 590 X(I) = X(I) + D(I) 600 GOTO 630 610 REM ENDIF2 620 Next I 630 REM FOR1 640 GOTO 390 650 REM EXITDO2 660 I0 = I0 + 1 670 DISP "Best F = "; B;" "; 680 For I = 1 To N 690 DISP "X(";I;") = ";X9(I);" "; 700 X5(I) = X9(I) 710 D(I) = D(I) / N0(I) 720 L0(I) = X5(I) - D(I) * N0(I) / 2 730 H1(I) = X5(I) + D(I) * N0(I) / 2 740 X(I) = L0(I) ! reset array X 750 Next I 760 DISP "" 770 G0 = 0 780 For I = 1 To N 790 If D(I) > D0(I) Then G0 = 1 800 Next I 810 If (Abs(B - L) <= E) OR (I0 > I9) Then G0 = 0 820 IF G0 = 1 THEN 380 830 REM EXITDO2 840 DISP "********FINAL RESULTS***********" 850 For I = 1 To N 860 DISP "X(";I;") = ";X9(I) @ PAUSE 870 Next I 880 DISP "Function value =";B @ PAUSE 890 DISP "Iterations = ";I0 900 END 910 SUB MyFx(X(), N, R0) 920 R0 = 10 930 For K = 1 To N 940 R0 = R0 + (X(K) ^ 2 - K) ^ 2 950 Next K 960 End Sub

**Copyright (c) Namir Shammas. All rights reserved.**