Downhill Simplex Method (Nelder Mead) for WP-34S
Message #1 Posted by Marcel Samek on 7 July 2013, 3:05 a.m.
Over the years I have found the Downhill Simplex method very useful in all sorts of very varied applications. It may have its flaws and quirks, but with a little bit of massaging, I have found it an extremely reliable tool.
So, for the first time, instead of writing application specific C code, I decided to put a version on my WP-34S.
The code supports 8 dimensions but no more.
You will need to write a function called 'FUN'. As it is implemented, you cannot pass the name of the function to the routine.
The tolerance that needs to be met is hardcoded into the code and should probably be passed in, but I don't feel like making that change right now.
The maximum number of iterations is also in the code and should also be changed to be a parameter. And, I don't feel like doing that either.
This code is based on the Amoeba routines found in Numerical Recipes. I have not documented the code particularly well, however I am including a link to a version of the code that has corresponding C code inline as documentation.
Nelder Mead (Downhill Simplex) User Program
Nelder Mead (Downhill Simplex) Assember File (with comments)
------------- User Program ------------------
/*
Nelder Mead (Downhill Simplex) Method
Multi-dimensional Minimization
Limitations: The code supports up to 8 dimensions, but you will
probably not be able to use that many because of
memory restrictions. It depends on the size of your
evaluation function, register allocations, etc.
Global Register required: N^2 + N + 20
Stack: Requires a stack size of 8
Local Registers: (20 at deepest point) + (your eval function)
Prerequisite: You need to have a global function called 'FUN'
which evaluates your function. The parameters to FUN
are all passed on the stack. FUN needs to return
one value (the evaluated function) in X.
Input: (X) Number of dimensions
Output: R03: F(x1, x2, x3....) at minimum
R04: x1
R05: x2
R06: X3
...
Configuration: This algorithm is known for getting stuck, especially
if the function has lots of local minima or
discontinuities. There is a configuration value that
defines the maximum number of times it shall adjust
the simplex before giving up. It defaults to 10000.
If you wish to adjust this value, it is assigned to
local register .06 right at the beginning of NMS.
The initial guess is aribrarily picked to be between
0 and 1 on all dimensions. If you wish to change the
initial values, simply change the initValues function
at LBL 31. Make sure that when that function returns
it has valid values in the Y array for the
simplex vertices you have chosen as the starting point.
Algorithm: This is a direct derivative of the Downhill Simplex
method as described and implemented in Numerical
Recipes. Please see that text for a description
of how the algorithm works.
*/
0001 LBL'NMS'
0002 LocR 007
0003 REGS 100
0004 SSIZE8
0005 CLREGS
0006 STO 00
0007 1
0008 SDL 004
0009 STO .06
0010 XEQ 31
0011 XEQ 30
0012 0
0013 STO .02
0014 0
0015 XEQ 20
0016 1
0017 XEQ 20
0018 x<? Y
0019 SKIP 005
0020 0
0021 STO .03
0022 1
0023 STO 02
0024 SKIP 004
0025 1
0026 STO .03
0027 0
0028 STO 02
0029 RCL 00
0030 STO .00
0031 RCL .00
0032 XEQ 20
0033 RCL .02
0034 XEQ 20
0035 x<? Y
0036 SKIP 002
0037 RCL .00
0038 STO .02
0039 RCL .00
0040 XEQ 20
0041 RCL 02
0042 XEQ 20
0043 x[>=]? Y
0044 SKIP 005
0045 RCL 02
0046 STO .03
0047 RCL .00
0048 STO 02
0049 SKIP 011
0050 RCL .00
0051 XEQ 20
0052 RCL .03
0053 XEQ 20
0054 x[>=]? Y
0055 SKIP 005
0056 RCL 02
0057 RCL .00
0058 x=? Y
0059 SKIP 001
0060 STO .03
0061 DSL .00
0062 BACK 031
0063 RCL 02
0064 XEQ 20
0065 RCL .02
0066 XEQ 20
0067 -
0068 ABS
0069 RCL 02
0070 XEQ 20
0071 ABS
0072 RCL .02
0073 XEQ 20
0074 ABS
0075 +
0076 1
0077 SDR 010
0078 +
0079 /
0080 2
0081 [times]
0082 1
0083 SDR 003
0084 x[<=]? Y
0085 SKIP 016
0086 RCL .02
0087 XEQ 20
0088 STO 03
0089 RCL 00
0090 STO .00
0091 DEC .00
0092 RCL .02
0093 RCL .00
0094 XEQ 24
0095 4
0096 RCL+ .00
0097 x[<->] Y
0098 STO[->]Y
0099 DSL .00
0100 BACK 008
0101 GTO 99
0102 RCL 01
0103 x<? .06
0104 SKIP 007
0105 CL[alpha]
0106 [alpha]'Loo'
0107 [alpha]'p[space]M'
0108 [alpha] a
0109 [alpha] x
0110 VIEW[alpha]
0111 GTO 99
0112 INC 01
0113 INC 01
0114 1
0115 +/-
0116 XEQ 26
0117 STO .05
0118 RCL .02
0119 XEQ 20
0120 x<? Y
0121 SKIP 004
0122 2
0123 XEQ 26
0124 STO .05
0125 SKIP 053
0126 RCL .03
0127 XEQ 20
0128 RCL .05
0129 x<? Y
0130 SKIP 047
0131 RCL 02
0132 XEQ 20
0133 STO .04
0134 # 1/2
0135 XEQ 26
0136 STO .05
0137 RCL .04
0138 x>? Y
0139 SKIP 039
0140 RCL 00
0141 STO .00
0142 RCL .00
0143 x=? .02
0144 SKIP 027
0145 RCL 00
0146 STO .01
0147 DEC .01
0148 RCL .00
0149 RCL .01
0150 XEQ 24
0151 RCL .02
0152 RCL .01
0153 XEQ 24
0154 +
0155 2
0156 /
0157 RCL .01
0158 x[<->] Y
0159 XEQ 23
0160 RCL .00
0161 RCL .01
0162 RCL .01
0163 XEQ 22
0164 XEQ 25
0165 DSL .01
0166 BACK 018
0167 RCLS 12
0168 XEQ'FUN'
0169 RCL .00
0170 x[<->] Y
0171 XEQ 21
0172 DSL .00
0173 BACK 031
0174 RCL 00
0175 STO+ 01
0176 XEQ 30
0177 SKIP 001
0178 DEC 01
0179 BACK 167
0180 LBL 99
0181 STOP
0182 RTN
0183 LBL 00
0184 RCL[->]X
0185 x[<->] Y
0186 DROP
0187 RTN
0188 LBL 20
0189 3
0190 +
0191 XEQ 00
0192 RTN
0193 LBL 21
0194 x[<->] Y
0195 3
0196 +
0197 x[<->] Y
0198 STO[->]Y
0199 RTN
0200 LBL 22
0201 # 012
0202 +
0203 XEQ 00
0204 RTN
0205 LBL 23
0206 x[<->] Y
0207 # 012
0208 +
0209 x[<->] Y
0210 STO[->]Y
0211 RTN
0212 LBL 24
0213 x[<->] Y
0214 RCL[times] 00
0215 +
0216 # 020
0217 +
0218 XEQ 00
0219 RTN
0220 LBL 25
0221 [<->] ZYXT
0222 RCL[times] 00
0223 +
0224 # 020
0225 +
0226 x[<->] Y
0227 STO[->]Y
0228 RTN
0229 LBL 26
0230 LocR 013
0231 STO .04
0232 +/-
0233 1
0234 +
0235 RCL 00
0236 /
0237 STO .01
0238 RCL .04
0239 -
0240 STO .02
0241 RCL 00
0242 STO .00
0243 DEC .00
0244 RCL .00
0245 XEQ 22
0246 RCL .01
0247 [times]
0248 RCL 02
0249 RCL .00
0250 XEQ 24
0251 RCL .02
0252 [times]
0253 -
0254 RCL .00
0255 # 117
0256 +
0257 x[<->] Y
0258 STO[->]Y
0259 DSL .00
0260 BACK 016
0261 RCLS .05
0262 XEQ'FUN'
0263 STO .03
0264 RCL 02
0265 XEQ 20
0266 RCL .03
0267 x[>=]? Y
0268 SKIP 026
0269 RCL 02
0270 RCL .03
0271 XEQ 21
0272 RCL 00
0273 STO .00
0274 DEC .00
0275 RCL .00
0276 ENTER[^]
0277 XEQ 22
0278 # 117
0279 RCL+ .00
0280 XEQ 00
0281 +
0282 RCL 02
0283 RCL .00
0284 XEQ 24
0285 -
0286 XEQ 23
0287 RCL 02
0288 RCL .00
0289 # 117
0290 RCL+ .00
0291 XEQ 00
0292 XEQ 25
0293 DSL .00
0294 BACK 019
0295 RCL .03
0296 RTN
0297 LBL 30
0298 LocR 003
0299 RCL 00
0300 STO .01
0301 DEC .01
0302 0
0303 STO .02
0304 RCL 00
0305 STO .00
0306 RCL .00
0307 RCL .01
0308 XEQ 24
0309 STO+ .02
0310 DSL .00
0311 BACK 005
0312 RCL .01
0313 RCL .02
0314 XEQ 23
0315 DSL .01
0316 BACK 014
0317 RTN
0318 LBL 31
0319 LocR 010
0320 RCL 00
0321 STO .00
0322 RCL 00
0323 STO .01
0324 DEC .01
0325 RCL .01
0326 1
0327 +
0328 RCL .00
0329 0
0330 x[<->] Y
0331 x=? Z
0332 INC Y
0333 DROP
0334 RCL .01
0335 # 114
0336 +
0337 x[<->] Y
0338 STO[->]Y
0339 RCL .00
0340 RCL .01
0341 [<->] ZXYT
0342 XEQ 25
0343 DSL .01
0344 BACK 019
0345 RCLS .02
0346 XEQ'FUN'
0347 RCL .00
0348 x[<->] Y
0349 XEQ 21
0350 DSL .00
0351 BACK 029
0352 RTN
0353 END
| 
Go back to the main exhibit hall