パウエル法

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "パウエル法" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2009年8月)

パウエル法（パウエルほう、パウエルの共役方向法、パウエルのきょうやくほうこうほう、英: Powell's method, Powell's conjugate direction method）とは、関数の局所的最小解を求めるアルゴリズムである。関数は微分可能関数である必要はなく、導関数を必要としない。

関数は変数の数が可変でない実数値を入力とする実数値関数でなければならない。また初期点と探索ベクトル集合が入力として必要である。通常初期の探索ベクトル集合（${\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}\|}$）は削除される。新たに更新された要素数 N の探索ベクトル集合は ${\textstyle \{s_{1},\dots ,s_{i_{d}-1},s_{i_{d}+1},\dots ,s_{N},\sum _{i=1}^{N}\alpha _{i}s_{i}\}}$ と表される。パウエル法は関数の値の改善がされなくまで反復が続けられる^[1]。

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

脚注

参考文献

• Powell, M. J. D. (1964). “An efficient method for finding the minimum of a function of several variables without calculating derivatives”. 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). “Section 10.7. Direction Set (Powell's) Methods in Multidimensions”. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. http://apps.nrbook.com/empanel/index.html#pg=509 
• Brent, Richard P. (1973). “Section 7.3: Powell's algorithm”. Algorithms for minimization without derivatives. Englewood Cliffs, N.J.: Prentice-Hall. ISBN 0-486-41998-3. https://books.google.com/books?id=6Ay2biHG-GEC&pg=PP1 

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形（無制約）	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 放物線補間 パウエル法 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS法 DFP法 対称ランクワン法（英語版） BHHH法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マーカート法 共役勾配法（非線形共役勾配法） 打ち切りニュートン法 ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法
非線形（制約付き）	一般 バリア関数 ペナルティ関数法 微分可能 ラグランジュの未定乗数法 逐次二次計画法 逐次線形計画法
凸最適化	凸縮小化 切除平面法 簡約勾配法 劣勾配法 線形 および 二次 内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法） グラフ理論 最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法 ネットワークフロー (最大流問題) ディニッツ法 エドモンズ・カープ フォード・ファルカーソン プリフロープッシュ法（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア