数理最適化

提供: miniwiki
2018/10/17/ (水) 00:12時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内、検索
ファイル:MaximumParaboloid.png
f(x, y) = −(x² + y²) + 4 で与えられる放物面のグラフ。(0, 0, 4) での最大値が赤い点で示されている。

数学の計算機科学やオペレーションズリサーチの分野における数理最適化（すうりさいてきか、英: mathematical optimization）とは、（ある条件に関して）最もよい元を、利用可能な集合から選択することをいう[1]。

最も簡単な最適化問題には、ある許された集合から入力をシステマティックに選び、函数の値を計算することによる実数函数（English版）の最大化と最小化がある。最適化理論とその手法の、他の形式への一般化は応用数学の広範な分野をなすものである。より一般に、最適化はある与えられた定義域（あるいは制約の集合）についてある目的函数の「利用可能な最も良い」値を見つけることも含む。そのような目的函数と定義域は多様な異なるタイプのものも含む。

最適化問題

"「最適化問題」"

最適化問題は、次のように表現される：

与えられるもの：ある集合 A から実数への函数 f : A [math]\to[/math] R
目的：A 内のすべての x に対して f(x0) ≤ f(x) を満たす A 内の元 x0（最小化）あるいは f(x0) ≥ f(x) を満たす A 内の元 x0（最大化）を見つけること。

このような問題は最適化問題あるいは数理計画問題（コンピュータプログラミングとは直接的には関係ないが、例えば線型計画法では用いられる）と呼ばれる。多くの実世界での問題や理論的問題は、一般的な枠組みでモデル化される。物理学やコンピュータビジョンの分野における、この手法による問題は、エネルギー最小化（energy minimization）と呼ばれることもある。この場合、函数 f の値はモデル化されるシステムのエネルギーを表す。

典型的に A はユークリッド空間 Rn の部分集合であり、しばしばある制約（English版）の集合によって特徴づけられ、A の元は求められる等式あるいは不等式を満たす必要がある。f の定義域 A は探索空間（search space）あるいは選択集合（choice set）と呼ばれ、A の元は可能解（candidate solution, feasible solution）と呼ばれる。

函数 f は、目的函数（objective function）や損失函数（loss function）、費用函数（cost function）、効用函数（utility function）、適合函数（fitness function）、エネルギー函数（energy function）あるいはエネルギー汎函数（energy functional）と呼ばれる[2]。目的函数を最小化（あるいは最大化）する可能解は、最適解と呼ばれる。

数学において慣習的な最適化問題は、通常、最小化に関するものである。一般に、最小化問題において目的函数と可能領域が両方とも凸でない限り、いくつかの局所最小解が存在しうる。ここで局所最小解 x* は、ある定数 δ > 0 が存在して、

[math]\|\mathbf{x}-\mathbf{x}^*\|\leq\delta;\,[/math]

を満たすすべての x に対して次が成立するもののことをいう。

[math]f(\mathbf{x}^*)\leq f(\mathbf{x}).[/math]

すなわち、x* のまわりのある領域における函数のすべての値は、その点での値よりも大きいか等しくなる。局所最大解も同様に定義される。

記号

最適化問題では、しばしば特殊な記号が用いられる。ここではそれらのいくつかを紹介する。

函数の最小値と最大値

次の記号を考える：

[math]\min_{x\in\mathbb R}\; (x^2 + 1).[/math]

これは x を実数の集合 [math]\mathbb R[/math] から選んだときの目的函数 [math]x^2 + 1[/math] の最小値を意味する。この場合の最小値は [math]x = 0[/math] のときの [math]1[/math] である。

同様に、記号

[math]\max_{x\in\mathbb R}\; 2x[/math]

は、任意の実数 x に対する目的函数 2x の最大値を意味する。この場合、目的函数は非有界なのでそのような最大値は存在せず、「無限大」あるいは「定義されない」が答えとなる。

最適入力引数

"「arg max」"

次の記号を考える。

[math]\underset{x\in(-\infty,-1]}{\operatorname{arg\,min}} \; x^2 + 1.[/math]

あるいは、次の同値なものを考える。

[math]\underset{x}{\operatorname{arg\,min}} \; x^2 + 1, \; \text{subject to:} \; x\in(-\infty,-1].[/math]

これは、区間 [math](-\infty,-1][/math] において目的函数 x2 + 1 を最小化する引数 x の値を与える（その函数の最小値がどのような値であるかはここでは問題とされない）。この場合、x = 0 は不可能、すなわち実行可能領域（English版）に属さないため、答えは x = -1 となる。

同様に

[math]\underset{x\in[-5,5], \; y\in\mathbb R}{\operatorname{arg\,max}} \; x\cos(y)[/math]

あるいは

[math]\underset{x, \; y}{\operatorname{arg\,max}} \; x\cos(y), \; \text{subject to:} \; x\in[-5,5], \; y\in\mathbb R[/math]

は、x が区間 [math][-5,5][/math] に属するという制約の下で、目的函数 [math]x\cos(y)[/math] の値を最大化する [math](x,y)[/math] のペアを意味する（再び、その実際の最大値は問題とされない）。この場合の解は、すべての整数 k に対する (5, 2kπ) と (−5,(2k+1)π) である。

arg min と arg max はしばしば、argmin および argmax と書かれることもあり、それらは「最小値の引数」および「最大値の引数」を意味する。

歴史

フェルマーとラグランジュは最適解を求める上で微分積分学に基づく方法を発見した。一方でニュートンとガウスは最適解へ収束する反復法を提唱した。

ある種の最適化に関する線型計画法という語はジョージ・ダンツィク（English版）によるものである。一方で、1939年にレオニート・カントロヴィチによって多くの理論が構築された（この文脈における「計画法（programming）」はコンピュータ・プログラミングとは異なり、アメリカ軍隊によって訓練や物流のスケジュールを表すために用いられていた "program" が語源である。ダンツィクは当時その研究をしていた）。ダンツィクは1947年に Simplex Algorithm（シンプレックス法）を出版し、ジョン・フォン・ノイマンは同年に双対性の理論を発展させた。

その他の主要な数理最適化の研究者は以下に挙げられる：

関連項目

脚注

  1. ↑ "The Nature of Mathematical Programming ," Mathematical Programming Glossary, INFORMS Computing Society.
  2. ↑ W. Erwin Diewert (2008). "cost functions," The New Palgrave Dictionary of Economics, 2nd Edition Contents.

雑誌

外部リンク

テンプレート:最適化アルゴリズム



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=数理最適化&oldid=257204」から取得