Nelder Mead Optimization

Contributions to this software library are always welcome. Please ensure that you post program listings rather than .raw files. They give a reasonable idea of what your program does without having to load them into a DM42 and you can also include comments in your code. Check out the following link for a decoder/encoder: http://www.swissmicros.com/dm42/decoder/

You can then copy/paste the listing and post it in "code" tags.
Post Reply
rawi
Posts: 13
Joined: Sat Dec 28, 2019 3:50 am

Nelder Mead Optimization

Post by rawi » Thu Apr 30, 2020 11:28 am

(Program listing put inside code tags by moderator)

Nelder Mead Optimization of a function of 2 variables.
References: https://en.wikipedia.org/wiki/Nelder–Mead_method
Application:
Precondition: The function that is to be optimized is in the subroutine “FU”.’
Input of FU is value of variable X in the X register and of variable Y in the Y-register.
Output of FU is f(X,Y) in the X-register.
Note: NMO searches a minimum of f(X,Y). If a maximum has to be searched take the negative of f(X,Y) as output of FU.
Program uses registers 00 and 05 until 19.
Input: Termination criterion: (a small number, e.g. .0001) in register 00.
Original length of search steps (the more shallow the function is the larger, e.g. .2 to .5): Register Z
Starting point for variable Y: Register Y
Starting point of variable X: Register X

Output is on the stack:
Z-register: Function value f(X,Y) at minimum
Y-register: Y
X-register: X

Example: Use Function FU as listed below. This function is a banana-shaped function that is used in
literature as a difficult to optimize function
f(X,Y) = 100*(X²-Y)²+(1-X)²
The minimum is at X=Y=1 and f(1,1)=0.
We start with a first estimate of X=-2, Y=2 and a step width of 0.2.
The termination criterion is .0001.
Input is as follows:
.0001 STO 00
.2 ENTER
2 ENTER
-2
CATALOG – PGM – NMO
Output:
Z: 1.9662E-10  Estimate of function at minimum
Y: 1.0000  Estimate of Y at minimum
X: 1.0000  Estimate of X at minimum

Code: Select all

00 { 274-Byte Prgm }
01▸LBL "NMO"
02 STO 05
03 STO 08
04 STO 11
05 R↓
06 STO 06
07 STO 09
08 STO 12
09 R↓
10 STO+ 08
11 2
12 ÷
13 STO+ 11
14 3
15 SQRT
16 ×
17 STO+ 12
18 RCL 06
19 RCL 05
20 XEQ "FU"
21 STO 07
22 XEQ 31
23 XEQ 11
24▸LBL 01
25 RCL 05
26 RCL 08
27 +
28 2
29 ÷
30 STO 14
31 RCL 06
32 RCL 09
33 +
34 2
35 ÷
36 STO 15
37 XEQ 21
38 RCL 05
39 RCL 08
40 -
41 X↑2
42 RCL 06
43 RCL 09
44 -
45 X↑2
46 +
47 SQRT
48 RCL 05
49 RCL 11
50 -
51 X↑2
52 RCL 06
53 RCL 12
54 -
55 X↑2
56 +
57 SQRT
58 +
59 2
60 ÷
61 RCL 00
62 X<Y?
63 GTO 01
64 RCL 07
65 RCL 06
66 RCL 05
67 RTN
68▸LBL 11
69 RCL 10
70 RCL 07
71 X≤Y?
72 GTO 12
73 STO 10
74 X<>Y
75 STO 07
76 RCL 05
77 RCL 08
78 STO 05
79 X<>Y
80 STO 08
81 RCL 06
82 RCL 09
83 STO 06
84 X<>Y
85 STO 09
86▸LBL 12
87 RCL 13
88 RCL 10
89 X≤Y?
90 GTO 13
91 STO 13
92 X<>Y
93 STO 10
94 RCL 08
95 RCL 11
96 STO 08
97 X<>Y
98 STO 11
99 RCL 09
100 RCL 12
101 STO 09
102 X<>Y
103 STO 12
104 GTO 11
105▸LBL 13
106 RTN
107▸LBL 21
108 1
109 STO 19
110 XEQ 24
111 RCL 13
112 X<Y?
113 GTO 23
114 RCL 18
115 RCL 10
116 X>Y?
117 GTO 22
118 R↓
119 RCL 07
120 X≤Y?
121 GTO 22
122 2
123 STO 19
124▸LBL 22
125 RCL 16
126 STO 11
127 RCL 17
128 STO 12
129 RCL 18
130 STO 13
131 XEQ 11
132 RTN
133▸LBL 23
134 0.5
135 STO 19
136 XEQ 24
137 RCL 13
138 X>Y?
139 GTO 22
140 2
141 STO÷ 08
142 STO÷ 09
143 STO÷ 11
144 STO÷ 12
145 RCL 05
146 2
147 ÷
148 STO+ 08
149 STO+ 11
150 RCL 06
151 2
152 ÷
153 STO+ 09
154 STO+ 12
155 XEQ 31
156 XEQ 11
157 RTN
158▸LBL 24
159 RCL 15
160 RCL 12
161 -
162 RCL 19
163 ×
164 RCL 15
165 +
166 STO 17
167 RCL 14
168 RCL 11
169 -
170 RCL 19
171 ×
172 RCL 14
173 +
174 STO 16
175 XEQ "FU"
176 STO 18
177 RTN
178▸LBL 31
179 RCL 09
180 RCL 08
181 XEQ "FU"
182 STO 10
183 RCL 12
184 RCL 11
185 XEQ "FU"
186 STO 13
187 RTN
188 END

Code: Select all

00 { 24-Byte Prgm }
01▸LBL "FU"
02 STO 01
03 X↑2
04 X<>Y
05 STO 02
06 -
07 X↑2
08 100
09 ×
10 1
11 RCL 01
12 -
13 X↑2
14 +
15 RTN
16 END

Post Reply