パウエル法

パウエル法（厳密にはパウエル共役方向法）は、マイケル・J・D・パウエルによって提案された、関数の局所最小値を求めるアルゴリズムです。関数は微分可能である必要はなく、導関数も必要ありません。

この関数は、固定数の実数値入力を持つ実数値関数でなければなりません。呼び出し元は初期点を渡します。また、呼び出し元は初期探索ベクトルの集合も渡します。通常、N個の探索ベクトル（例えば）が渡されます。これらのベクトルは、各軸に沿う法線です。^[1]${\textstyle \{s_{1},\dots ,s_{N}\}}$

この方法では、各探索ベクトルに沿った双方向探索を順に行うことで、関数 を最小化します。各探索ベクトルに沿った双方向直線探索は、黄金分割探索またはブレント法によって実行できます。各双方向直線探索中に見つかった最小値を とします。ここで、は最初の開始点、 はに沿った双方向探索中に決定されるスカラーです。新しい位置 ( ) は、探索ベクトルの線形結合、つまり として表すことができます。新しい変位ベクトル ( ) は新しい探索ベクトルになり、探索ベクトルリストの末尾に追加されます。一方、新しい方向に最も貢献した探索ベクトル、つまり最も成功した探索ベクトル ( ) は、探索ベクトルリストから削除されます。新しいN 個の探索ベクトルのセットは です。アルゴリズムは、有意な改善が見られなくなるまで任意の回数反復されます。^[1]${\textstyle \{x_{0}+\alpha _{1}s_{1},{x}_{0}+\sum _{i=1}^{2}\alpha _{i}{s}_{i},\dots ,{x}_{0}+\sum _{i=1}^{N}\alpha _{i}{s}_{i}\}}$ ${\textstyle {x}_{0}}$ ${\textstyle \alpha _{i}}$ ${\textstyle {s}_{i}}$ ${\textstyle x_{1}}$ ${\textstyle x_{1}=x_{0}+\sum _{i=1}^{N}\alpha _{i}s_{i}}$ ${\textstyle \sum _{i=1}^{N}\alpha _{i}s_{i}}$ ${\textstyle i_{d}=\arg \max _{i=1}^{N}|\alpha _{i}|\|s_{i}\|}$ ${\textstyle \{s_{1},\dots ,s_{i_{d}-1},s_{i_{d}+1},\dots ,s_{N},\sum _{i=1}^{N}\alpha _{i}s_{i}\}}$

この手法は、連続的だが複雑な関数、特に数学的な定義を持たない関数の局所最小値を計算するのに有用です。なぜなら、導関数を取る必要がないからです。基本的なアルゴリズムは単純で、複雑なのは探索ベクトルに沿った線形探索であり、これはブレント法によって実現できます。

参考文献

1. Mathews, John H. 「Powell Search Method for a Minimum（最小値を求めるパウエル探索法）モジュール」カリフォルニア州立大学フラートン校。 2017年6月16日閲覧。

• Powell, MJD (1964). 「導関数を計算せずに多変数関数の最小値を求める効率的な方法」. Computer Journal . 7 (2): 155– 162. doi :10.1093/comjnl/7.2.155. hdl : 10338.dmlcz/103029 .
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). 「第10.7節 多次元における方向集合法（Powell法）」.数値計算レシピ集：科学計算の芸術（第3版）. ニューヨーク：ケンブリッジ大学出版局. ISBN 978-0-521-88068-8。
• ブレント、リチャード・P. (1973). 「第7.3節：パウエルのアルゴリズム」.導関数を使わない最小化アルゴリズム. イングルウッド・クリフス、ニュージャージー州: プレンティス・ホール. ISBN 0-486-41998-3。