パウエル法

パウエル法（厳密にはパウエル共役方向法）は、関数の極小値を見つけるためにマイケル・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}\}}$

この方法は、導関数を取る必要がないため、特に基礎となる数学的定義のない連続的だが複雑な関数の極小値を計算するのに便利です。基本的なアルゴリズムは単純です。複雑なのは、検索ベクトルに沿った線形検索にあり、これはBrent 法で実現できます。

• 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 版)。ニューヨーク: Cambridge University Press。ISBN 978-0-521-88068-8。
• ブレント、リチャード P. (1973)。「セクション 7.3: パウエルのアルゴリズム」。導関数なしの最小化アルゴリズム。ニュージャージー州エングルウッド クリフス: プレンティス ホール。ISBN 0-486-41998-3。