Método de Nelder-Mead (\(n\) dimensões) - Downhill Simplex

Considere \(f(x_{1},x_{2},\ldots,x_{n})\) a função a ser minimizada. Define-se avaliar um ponto como calcular o valor da função nesse ponto.

1 - Defina \(n+1\) pontos iniciais com \(n\) dimensões. \(x_{i}=\left(x_{i1},x_{i2},\ldots,x_{in}\right)\), em que \(1\leq i\leq n+1\). Ordene e renomeie de forma que \(f(x_{1})<f(x_{2})<\ldots<f(x_{n+1})\).

2 - Calcule o centróide \(x_{g}=\left(x_{g1},x_{g2},\ldots,x_{gn}\right)\) dos \(n\) pontos com menor avaliação: \(\displaystyle x_{gj}\leftarrow\frac{1}{n}\sum_{i=1}^{n+1}x_{ij}\), \(1\leq j\leq n\).

3 - Calcule o ponto de reflexão \(x_{r}=\left(x_{r1},x_{r2},\ldots,x_{rn}\right)\): \(r_{ri}\leftarrow x_{gi}+\alpha\left(x_{gi}-x_{(n+1)i}\right)\), \(1\leq i\leq n\). Avalie esse ponto: \(f(x_{r})\).

4 - Se \(f(x_{1})<f(x_{r})\leq f(x_{n})\), então faça \(x_{(n+1)j}\leftarrow x_{rj}\), \(1\leq j\leq n\). Ordene os pontos por ordem crescente de avaliação e vá para o passo 2.

5 - Se \(f(x_{r})\leq f(x_{1})\), então calcule o ponto de expansão \(x_{e}=\left(x_{e1},x_{e2},\ldots,x_{en}\right)\): \(x_{ej}\leftarrow x_{rj}+\beta\left(x_{rj}-x_{gj}\right)\), \(1\leq j\leq n\). Avalie esse ponto: \(f(x_{e})\).

6 - Se \(f(x_{e})\leq f(x_{r})\), então faça \(x_{1j}\leftarrow x_{ej}\) e \(x_{ij}\leftarrow x_{(i-1)j}\), \(1\leq j\leq n+1\), e vá para o passo 2. Senão, faça \(x_{1j}\leftarrow x_{rj}\) e \(x_{ij}\leftarrow x_{(i-1)j}\), \(1\leq j\leq n+1\), e vá para o passo 2.

7 - Se \(f(x_{r})>f(x_{n})\), então calcule o ponto de contração \(x_{c}=\left(x_{c1},x_{c2},\ldots,x_{cn}\right)\): \(x_{cj}\leftarrow x_{gj}+\gamma\left(x_{(n+1)j-x_{gj}}\right)\), \(1\leq j\leq n\). Avalie esse ponto: \(f(x_{c})\).

8 - Se \(f(x_{c})\leq f(x_{n+1})\), então faça \(x_{(n+1)j}\leftarrow x_{cj}\), \(1\leq j\leq n\). Ordene os pontos por ordem crescente de avaliação e vá para o passo 2.

9 - Se \(f(x_{c})>f(x_{n+1})\), então realize uma contração ao longo de todas as dimensões em direção ao ponto \(x_{1}\): \(x_{ij}\leftarrow x_{ij}+\nu\left(x_{ij-x_{1j}}\right)\), \(2\leq i\leq n+1\), \(1\leq j\leq n\). Ordene os pontos por ordem crescente de avaliação e vá para o passo 2.

Valores recomendados: \(\alpha=1\), \(\beta=1\), \(\gamma=0,5\) e \(\nu=0,5\).