## Please implement the Nelder-Mead Simplex Direct Search Method in Foldit

Case number: | 845813-2009377 |

Topic: | Game: Tools |

Opened by: | jeff101 |

Status: | Open |

Type: | Suggestion |

Opened on: | Sunday, April 5, 2020 - 21:14 |

Last modified: | Monday, April 6, 2020 - 01:50 |

```
Would someone please implement in Foldit, as either a LUA Recipe or a built-in LUA command,
an optimization algorithm like the Nelder-Mead Simplex Direct Search Method (implemented in
Matlab as the fminsearch command and in "Numerical Recipes in C" as the amoeba recipe)?
fminsearch can find the minimum of a function f of multiple variables even when the
derivatives of f with respect to these variables are unknown. While fminsearch is not
guaranteed to give the global minimum of f, I have seen fminsearch give good solutions when
optimizing up to about 20 variables.
For more information, please see:
https://www.mathworks.com/help/matlab/ref/fminsearch.html
https://www.mathworks.com/help/matlab/math/optimizing-nonlinear-functions.html#bsgpq6p-11
https://www.grad.hr/nastava/gs/prg/NumericalRecipesinC.pdf sections 10.0 & 10.4.
The pdf above is "Numerical Recipes in C: The Art of Scientific Computing"
Second Edition by William H Press, Saul A Teukolsky, William T Vetterling,
and Brian P Flannery, Cambridge University Press, ISBN=0-521-43108-5.
It seems to be the 1992 version but reprinted with corrections in 2002.
Sections 10.0 & 10.4 are pp.394-397 & 408-412 in the text
but pp.418-421 & 432-436 in the pdf.
```

Sun, 04/05/2020 - 22:39

#1
Mon, 04/06/2020 - 01:50

#2
```
One way to find a set of A,B,p values that gives z(t) ~ y(t)
for a given list of scores y and loop #'s t is to define the
function f = sum[(z-y)^2] = sum(z^2 - 2*z*y + y^2) and minimize
f with respect to A, B, and p. In the above definition, sum
means to sum over all values of z, y, and t. Also, because f
is a sum of squares, f will always be >= 0, and the minimum
of f will also be >= 0.
To minimize f, one could use fminsearch while varying A, B,
and p. This should work, but a more efficient way is to find
the derivatives of f with respect to A, B, and p, and set
them all to zero. That is, since z=A-B*exp(-p*t), one has
dz/dA=1, dz/dB= -exp(-p*t), dz/dp=B*t*exp(-p*t),
df/dA = sum[2*(z-y)*(dz/dA)] = sum[2*(z-y)*1],
df/dB = sum[2*(z-y)*(dz/dB)] = sum[2*(z-y)*(-exp(-p*t))], and
df/dp = sum[2*(z-y)*(dz/dp)] = sum[2*(z-y)*B*t*exp(-p*t)].
If one lets x(t)=exp(-p*t), one gets z=A-B*x and the following:
df/dA = sum[2*(z-y)*1] = 2*sum[z-y] = 2*sum[A-B*x-y]
which equals 0 when A*sum(1)-B*sum(x)=sum(y).
df/dB = sum[2*(z-y)*(-exp(-p*t))] = -2*sum[(z-y)*x]
= -2*sum[(A-B*x-y)*x] = -2*sum[A*x - B*x^2 - y*x]
which equals 0 when A*sum(x)-B*sum(x^2)=sum(y*x).
df/dp = sum[2*(z-y)*B*t*exp(-p*t)] = 2*B*sum[(z-y)*t*x]
= 2*B*sum[(A-B*x-y)*t*x] = 2*B*sum[A*t*x - B*t*x^2 - t*y*x]
which equals 0 when A*sum(t*x)-B*sum(t*x^2)=sum(t*y*x)
or more trivially when B=0.
Note that sum(1) above is the # of y values found by loop # t.
The above equations can be written in matrix form as:
|sum(1) -sum(x) | |sum(y) |
|sum(x) -sum(x^2) ||A|=|sum(y*x) |
|sum(t*x) -sum(t*x^2)||B| |sum(t*y*x)|
which could be solved for A & B using linear algebra,
but while sum(1) & sum(y) are fixed, sum(x), sum(x^2),
sum(y*x), sum(t*x), sum(t*x^2), & sum(t*y*x) all depend
on x(t)=exp(-p*t), which depends on p.
To make progress, one has fminsearch vary only p to find
the minimum value of f. A and B for any p can be found
using just the equations for df/dA=0 and df/dB=0:
A*sum(1)-B*sum(x)=sum(y)
A*sum(x)-B*sum(x^2)=sum(y*x)
which in matrix form give:
|sum(1) -sum(x) ||A|=|sum(y) |
|sum(x) -sum(x^2) ||B| |sum(y*x) |
and are solved by
A=[sum(y*x)*sum(x)-sum(y)*sum(x^2)]/[sum(x)*sum(x)-sum(1)*sum(x^2)]
B=[sum(y*x)*sum(1)-sum(y)*sum(x)] / [sum(x)*sum(x)-sum(1)*sum(x^2)].
Finally, using z=A-B*x, f = sum[(z-y)^2] = sum[(A-B*x-y)^2] gives
f = sum(A^2 + B^2*x^2 + y^2 - 2*A*B*x - 2*A*y + 2*B*x*y)
= A^2*sum(1) + B^2*sum(x^2) + sum(y^2)
- 2*A*B*sum(x) - 2*A*sum(y) + 2*B*sum(x*y).
This final equation for f can be evaluated using the sums
needed to calculate A and B for a given value of p.
If anyone finds typos in the above, please e-mail me about them.
Thanks!
```