###### tags: `Algorithm`
# Powell's Method

関数の極小値を求めるためのアルゴリズム．関数は微分可能である必要はない．

\begin{eqnarray}
f(\vec x)
\end{eqnarray}
を最小化する問題を考える．$\vec x = (x_1,\cdots,x_n)$とする．

この問題は，以下の手順(1)~(3)を繰り返すこと(iteration)で解を求めることができる．
(0) Iterationの前に，まず，探索ベクトルを$n$こ
\begin{eqnarray}
\vec {s_1},\cdots,\vec{s_n}
\end{eqnarray}
と，近似解$\vec{x_0}$を定義する．

(1) $r=(1,..,n)$に対して，
\begin{eqnarray}
\vec x_r \equiv \vec x_{r-1} + \lambda_r \vec s_r
\end{eqnarray}
とし，
\begin{eqnarray}
f(\vec x_r) = f(\vec x_0+\lambda_r \vec s_r)
\end{eqnarray}
を最小化するような$\lambda_r$を計算することで，$\vec{x_r}$を逐次的に求める．

(2)探索ベクトルの置き換えを行う．
\begin{eqnarray}
(x_1,\cdots,x_k,\cdots,x_{n-1},x_n) \to (x_2,\cdots,x_{k+1},\cdots,x_n,x_n-x_0)
\end{eqnarray}

(3)
\begin{eqnarray}
f(\vec x_0 + \lambda(\vec{x_n}-\vec{x_0}))
\end{eqnarray}
を最小化するような$\lambda$を求める．

> 探索ベクトルが変数の数$n$だけ必要なのは，非自明．
> 論文中では，この方法が二次形式を最小化する問題でうまくいくことを証明している．

> 探索ベクトルの定義の仕方は？

> Powell法を修正した方法も知られており，Wikipediaに書かれたやり方はIterationでの(2)で探索ベクトルをIterationごとに1つ削除するやり方が使われており，上記の行い方と異なる．

## 参考文献
[The Computer Journal, Volume 7, Issue 2, 1964, Pages 155–162](https://doi.org/10.1093/comjnl/7.2.155)
[scipy.optimize.minimize]([https:/](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html#rdd2e1855725e-3)/)
[Powell's conjugate direction method, Wikipedia](https://en.wikipedia.org/wiki/Powell%27s_method)