パウエル法のソースを表示

{{出典の明記|date=2009-08}}
'''パウエル法'''（パウエルほう、'''パウエルの共役方向法'''、パウエルのきょうやくほうこうほう、{{Lang-en-short|Powell's method, Powell's conjugate direction method}}）とは、関数の[[極値|局所的最小解]]を求める[[アルゴリズム]]である。関数は微分可能関数である必要はなく、導関数を必要としない。

関数は変数の数が可変でない実数値を入力とする実数値関数でなければならない。また初期点と探索ベクトル集合が入力として必要である。通常初期の探索ベクトル集合（<math display="inline">\{s_1, \dots, s_N\}</math>）は各軸に対応したN個の[[標準基底|標準ベクトル]]とすることが多い<ref name="mathews">{{cite web |last1=Mathews |first1=John H. |title=Module for Powell Search Method for a Minimum |url=http://mathfaculty.fullerton.edu/mathews/n2003/PowellMethodMod.html |website=California State University, Fullerton |access-date=2017-07-16 }}</ref>。

パウエル法は探索ベクトルを順番に[[双方向探索]]することによって関数の極小値を求める。探索ベクトルによる双方向探索では[[黄金分割探索]]や[[ブレント法]]によって実行される。各反復の双方向探索で求まる極小値は <math display="inline">\{ x_0 + \alpha_1s_1, {x}_0 + \sum_{i=1}^{2}\alpha_i{s}_i, \dots, {x}_0 +\sum_{i=1}^{N}\alpha_i{s}_i \}</math> となる。ただし、<math display="inline">{x}_0</math> は初期点を表し、<math display="inline">\alpha_i</math> は探索ベクトル <math display="inline">{s}_i</math> 方向に進む双方向探索において求まるスカラー値である。新たな点 <math display="inline">x_1</math> は探索ベクトルの線形和 <math display="inline">x_1 = x_0 + \sum_{i=1}^N \alpha_i s_i</math> によって表される。この線形和で表されるベクトル（<math display="inline">\sum_{i=1}^N \alpha_i s_i</math>）は新たな探索ベクトルとして、ベクトル集合に加えられる。その際ベクトル集合に最も前に加えられた探索ベクトル（<math display="inline">i_{d} = \arg \max_{i=1}^N |\alpha_i| \|s_i\|</math>）は削除される。新たに更新された要素数 ''N'' の探索ベクトル集合は <math display="inline">\{ s_1, \dots, s_{i_d - 1}, s_{i_d + 1}, \dots, s_N, \sum_{i=1}^N \alpha_i s_i \}</math> と表される。パウエル法は関数の値の改善がされなくまで反復が続けられる<ref name="mathews" />。

パウエル法は導関数を必要としない解法であるため、数学的に定義されていないような複雑な連続関数の局所的最小解を求めるために使用される。パウエル法の手続きは単純であるが、探索ベクトル方向の線形探索の計算が容易ではないが、これは[[ブレント法]]によって実現される。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
*{{cite journal |last=Powell |first=M. J. D. |year=1964 |title=An efficient method for finding the minimum of a function of several variables without calculating derivatives |journal=Computer Journal |volume=7 |issue=2 |pages=155–162 |doi=10.1093/comjnl/7.2.155 |hdl=10338.dmlcz/103029 |hdl-access=free }} 
*{{Cite book |last1=Press |first1=WH |last2=Teukolsky |first2=SA |last3=Vetterling |first3=WT |last4=Flannery |first4=BP | year=2007 |title=Numerical Recipes: The Art of Scientific Computing |edition=3rd |publisher=Cambridge University Press | location=New York |isbn=978-0-521-88068-8 |chapter=Section 10.7. Direction Set (Powell's) Methods in Multidimensions |chapter-url=http://apps.nrbook.com/empanel/index.html#pg=509 }}
*{{Cite book |last=Brent |first=Richard P. |year=1973 |title=Algorithms for minimization without derivatives |publisher=Prentice-Hall |location=Englewood Cliffs, N.J. |isbn=0-486-41998-3 |chapter=Section 7.3: Powell's algorithm |chapter-url=https://books.google.com/books?id=6Ay2biHG-GEC&pg=PP1 }}

{{最適化アルゴリズム}}

{{DEFAULTSORT:はうえるほう}}
[[Category:最適化アルゴリズムとメソッド]]
[[Category:数学に関する記事]]