Downhill Simplex Method for the HP-41

Overview
 

"DHS" employs the downhill simplex method to minimize a function of n variables  f ( x₁ , x₂ , ...... , x_n )     1 < n < 16
This program is very slow and a good emulator like V41 in turbo mode is recommended !
 

Program Listing
 

-The method is described, for example, in references [1] & [2]

-Before executing "DHS", store the function name in R00 and the initial guesses in R01 thru Rnn
-The accuracy is controlled by the display setting.
-Avoid FIX 9 which could lead to an infinite loop
 
 

Data Registers:           •  R00 = function name                                           ( R00 and R01 to Rnn  are to be initialized before executing "DHS" )

                                      •  R01 = x₁  •  R02 = x₂  ...........   •  Rnn = x_n             R21 = f ( x₁ , x₂ , ...... , x_n )          Rn+1 to R21+4n+n^2: temp
Flags: /
Subroutine:   A program which computes f ( x₁ , x₂ , ...... , x_n ) assuming x₁ is in R01 , x₂ is in R02 , ............ , x_n is in Rnn
 
 
 
 

01 LBL "DHS"  02 X<>Y  03 STO 20  04 X<>Y  05 STO 16  06 STO 17  07 ST+ X  08 22  09 +  10 RCL 16  11  E3  12 /  13 STO 18  14 +  15  E3  16 /  17 1  18 +  19 ISG 17  20 LBL 01  21 REGMOVE  22 RCL 18  23 +  24 DSE 17  25 GTO 01  26 RCL 16  27 X^2  28 LASTX  29 3  30 *  31 STO 18  32 +  33 21  34 +  35 STO 17  36 .1  37 %  38 22  39 +  40 RCL 18  41 +  42 RCL 16  43 1  44 +  45  E5  46 /  47 +  48 SIGN  49 CLX  50 RCL 20  51 LBL 18  52 ST+ IND L  53 ISG L  54 GTO 18  55 LBL 41  56 RCL 16  57 STO 18  58 21.02  59 +  60 STO 19  61 RCL 17  62 STO 20  63 LBL 02  64 RCL IND 20  65 STO IND 18  66 DSE 20

67 DSE 18  68 GTO 02  69 XEQ IND 00  70 STO IND 19  71 RCL 16  72 STO 18  73 DSE 19  74 GTO 02  75 LBL 16  76 RCL 16  77 21.02  78 +  79 STO L  80 RCL IND X  81 ENTER  82 DSE L  83 LBL 04  84 CLX  85 RCL IND L  86 X>Y?  87 GTO 04  88 X<>Y  89 CLX  90 LASTX  91 STO Z  92 LBL 04  93 DSE L  94 GTO 04  95 RCL 21  96 X<> IND T  97 STO 21  98 R^  99 INT 100 19 101 - 102 RCL 16 103 * 104 22 105 + 106 .1 107 % 108 RCL 16 109 ST+ X 110 + 111 22 112 + 113 RCL 16 114  E6 115 / 116 + 117 REGSWAP 118 RCL 16 119 21.02 120 + 121 STO L 122 RCL IND X 123 ENTER 124 DSE L 125 LBL 05 126 CLX 127 RCL IND L 128 X<Y? 129 GTO 05 130 X<>Y 131 CLX 132 LASTX

133 STO Z 134 LBL 05 135 DSE L 136 GTO 05 137 X<> Z 138 RCL 16 139 21 140 + 141 RCL IND Y 142 X<> IND Y 143 STO IND Z 144 X<> Z 145 INT 146 19 147 - 148 RCL 16 149 * 150 22 151 + 152 .1 153 % 154 RCL 16 155 ST+ Y 156 ST+ Y 157 X^2 158 + 159 22 160 + 161 RCL 16 162  E6 163 / 164 + 165 REGSWAP 166 RCL 16 167 20.02 168 + 169 STO L 170 RCL IND X 171 ENTER 172 DSE L 173 LBL 06 174 CLX 175 RCL IND L 176 X<Y? 177 GTO 06 178 X<>Y 179 CLX 180 LASTX 181 STO Z 182 LBL 06 183 DSE L 184 GTO 06 185 X<> Z 186 RCL 16 187 20 188 + 189 RCL IND Y 190 X<> IND Y 191 STO IND Z 192 X<> Z 193 INT 194 19 195 - 196 RCL 16 197 * 198 22

199 + 200 .1 201 % 202 RCL 16 203 ST+ Y 204 X^2 205 + 206 22 207 + 208 RCL 16 209  E6 210 / 211 + 212 REGSWAP 213 VIEW 21 214 RCL 16 215 ST+ X 216 21 217 + 218 .1 219 % 220 + 221 RCL 16 222 + 223 RCL 17 224 STO 18 225 CLX 226 LBL 13 227 RCL IND Y 228 RCL IND 18 229 - 230 ABS 231 X>Y? 232 X<>Y 233 RDN 234 DSE 18 235 DSE Y 236 GTO 13 237 RND 238 X=0? 239 GTO 99 240 22 241 RCL 16 242 ST+ Y 243 ST+ X 244 21 245 + 246  E3 247 / 248 + 249 STO 18 250 LBL 08 251 RCL 18 252 INT 253 .1 254 % 255 + 256 RCL 16 257 X^2 258 + 259 RCL 16 260  E5 261 / 262 + 263 ENTER 264 CLX

265 LBL 09 266 RCL IND Y 267 + 268 DSE Y 269 GTO 09 270 RCL 16 271 / 272 STO IND Y 273 ISG 18 274 GTO 08 275 RCL 16 276 STO 18 277 RCL 17 278 RCL 16 279 ST+ X 280 21 281 + 282 LBL 10 283 RCL IND X 284 ST+ X 285 RCL IND Z 286 - 287 STO IND 18 288 RDN 289 DSE X 290 DSE Y 291 DSE 18 292 GTO 10 293 XEQ IND 00 294 STO 18 295 RCL 21 296 X>Y? 297 GTO 11 298 CLX 299 RCL 16 300 20 301 + 302 X<>Y 303 RCL IND Y 304 X<=Y? 305 GTO 15 306 RCL 16 307 21 308 + 309 RCL 18 310 STO IND Y 311 LBL 17 312 RCL 17 313 1 314 + 315 RCL 16 316 ST- Y 317  E3 318 / 319 + 320 .1 321 % 322 1 323 + 324 REGMOVE 325 GTO 16 326 LBL 11 327 RCL 17 328 1 329 + 330 RCL 16

331  E3 332 / 333 + 334  E3 335 / 336 1 337 + 338 REGMOVE 339 RCL 16 340 ENTER 341 ST+ X 342 21 343 + 344 LBL 07 345 RCL IND Y 346 ST+ X 347 RCL IND Y 348 - 349 STO IND Z 350 RDN 351 DSE X 352 DSE Y 353 GTO 07 354 XEQ IND 00 355 STO 19 356 RCL 18 357 X>Y? 358 GTO 11 359 RCL 16 360 21 361 + 362 X<>Y 363 STO IND Y 364 RCL 17 365 1 366 + 367 STO Y 368 RCL 16 369 - 370  E3 371 / 372 + 373 RCL 16 374  E6 375 / 376 + 377 REGMOVE 378 GTO 16 379 LBL 11 380 RCL 16 381 21 382 + 383 RCL 19 384 STO IND Y 385 GTO 17 386 LBL 15 387 RCL 16 388 STO 20 389 ENTER 390 ST+ X 391 21 392 + 393 RCL 17 394 LBL 12 395 RCL IND Y 396 RCL IND Y

397 + 398 2 399 / 400 STO IND 20 401 RDN 402 DSE X 403 DSE Y 404 DSE 20 405 GTO 12 406 XEQ IND 00 407 STO 18 408 RCL 16 409 21 410 + 411 X<>Y 412 RCL IND Y 413 X<=Y? 414 GTO 11 415 X<>Y 416 STO IND Z 417 GTO 17 418 LBL 11 419 RCL 16 420 STO 18 421 RCL 17 422 STO 19 423 LBL 14 424 RCL 16 425 3 426 * 427 21 428 + 429 STO 20 430 LBL 00 431 RCL IND 20 432 RCL IND 19 433 + 434 2 435 / 436 STO IND 19 437 DSE 19 438 DSE 20 439 DSE 18 440 GTO 00 441 RCL 16 442 ST+ 18 443 RCL 19 444 RCL 20 445 X#Y? 446 GTO 14 447 GTO 41 448 LBL 99 449 RCL 16 450 .1 451 % 452 ISG X 453 LASTX 454 % 455 22 456 + 457 RCL 16 458 ST+ X 459 + 460 REGMOVE 461 RCL 21 462 END

 
      ( 767 bytes / SIZE 22+4n+n^2 )
 
 

STACK	INPUTS	OUTPUTS
Y	h	/
X	n	fmin

  Where  n = number of variables  and  h = initial increment

Example:

-Let's solve the overdetermined system:   x² + y² + z² = 4  ;  x² - y² + z = 2 ;  x + y + z² = 1 ;  x - y - z = 0
  by the least-squares method  ( the system itself has no solution )

-Let  f(x,y,z) = ( x² + y² + z² - 4 )²  + ( x² - y² + z - 2 )² + ( x + y + z² - 1 )² + ( x - y - z )²
 
 

01 LBL "T"  02 RCL 01  03 X^2  04 RCL 02  05 X^2  06 +  07 RCL 03

08 X^2  09 +  10 4  11 -  12 X^2  13 RCL 01  14 X^2

15 RCL 02  16 X^2  17 -  18 RCL 03  19 +  20 2  21 -

22 X^2  23 +  24 RCL 01  25 RCL 02  26 +  27 RCL 03  28 X^2

29 +  30 1  31 -  32 X^2  33 +  34 RCL 01  35 RCL 02

36 -  37 RCL 03  38 -  39 X^2  40 +  41 RTN  42 END

 

  "T"  ASTO 00     CLX   STO 01   STO 02    STO 03    if we choose  x = y = z = 0  as initial guesses

-SIZE 043  ( at least )

-For example  FIX 4
-If you choose  h = 1  and since there are 3 variables:

      1  ENTER^
      3  XEQ "DHS"   >>>>  the HP41 displays the successive f-approximations and finally, we get:

                       f_min = 1.4344 = R21

and we have in R01-R02-R03:   x = 1.1055    y = -0.9168    z = 1.2629

-With FIX 6, it yields:    f_min = 1.434377    x = 1.105450    y = -0.916829    z = 1.262964
 

Note:

-It may be wise to execute the program a second time to check or to improve the precision of the results...
 
 

References:

[1]  Press , Vetterling , Teukolsky , Flannery - "Numerical Recipes in C++" - Cambridge University Press - ISBN  0-521-75033-4
[2]  https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method