数理最適化

f(x, y) = −(x² + y²) + 4 で与えられる放物面のグラフ。(0, 0, 4) での最大値が赤い点で示されている。

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

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

最適化問題

詳細は「最適化問題」を参照

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

与えられるもの：ある集合 A から実数への函数 f : A $\to$ R

目的：A 内のすべての x に対して f(x₀) ≤ f(x) を満たす A 内の元 x₀（最小化）あるいは f(x₀) ≥ f(x) を満たす A 内の元 x₀（最大化）を見つけること。

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

典型的に A はユークリッド空間 Rⁿ の部分集合であり、しばしばある制約の集合によって特徴づけられ、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）と呼ばれる。目的函数を最小化（あるいは最大化）する可能解は、最適解と呼ばれる。

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

$\|\mathbf {x} -\mathbf {x} ^{*}\|\leq \delta ;\,$

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

$f(\mathbf {x} ^{*})\leq f(\mathbf {x} ).$

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

記号

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

函数の最小値と最大値

次の記号を考える：

$\min _{x\in \mathbb {R} }\;(x^{2}+1).$

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

同様に、記号

$\max _{x\in \mathbb {R} }\;2x$

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

最適入力引数

詳細は「arg max」を参照

次の記号を考える。

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

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

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

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

同様に

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

あるいは

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

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

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

歴史

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

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

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

• リチャード・E・ベルマン
• ロジャー・フレッチャー
• ロナルド・A・ハワード
• フリッツ・ジョン
• ナレンドラ・カーマーカー
• ウィリアム・カルーシュ
• レオニード・カチヤン
• バーナード・コープマン
• ハロルド・クーン
• ラースロー・ロヴァース
• アルカディ・ネミロフスキ
• ユーリ・ネステロフ
• ボリス・ポリャク
• レフ・ポントリャーギン
• ジェームス・レネガー
• R・ティレル・ロックフェラー
• コルネリス・ロース
• ナウム・Z・ショール
• ミカエル・J・トッド
• アルバート・タッカー

関連項目

• 最速降下曲線
• 曲線あてはめ
• 目標計画
• 最小二乗法
• プロセス最適化
• 変分法

雑誌

• Computational Optimization and Applications
• Journal of Computational Optimization in Economics and Finance
• Journal of Economic Dynamics and Control
• SIAM Journal on Optimization (SIOPT) and Editorial Policy
• SIAM Journal on Control and Optimization (SICON) and Editorial Policy

学習用参考図書など

外国語図書

• G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (eds.): "Optimization", Elsevier, (1989).

日本語図書

• G.L. Nemhauser (編), M.J. Todd (編), A.H.G. Rinnooy Kan (編)：「最適化ハンドブック」、朝倉書店、ISBN978-4254121025、（1995年10月1日）。
• 久保幹雄、田村明久、松井知己(編)：「応用数理ハンドブック」、朝倉書店、（2002）。
• 矢部博：「工学基礎 最適化とその応用」、数理工学社 (新・工科系の数学)、ISBN 978-4901683340、（2006年4月1日）。
• 山下信雄、福嶋雅夫：「数理計画法」、コロナ社、（2008）。
• 加藤直樹：「数理計画法」、コロナ社、（2008）。
• 福島雅夫：「数理計画入門(新版)」、朝倉書店、（2011）。
• 茨木俊秀：「最適化の数学」、共立出版、（2011）。
• 久野誉人、繁野麻衣子、後藤順哉：「数理最適化」、オーム社、（2012）。
• 山本芳嗣(編著)：「基礎数学— IV.最適化理論」、東京化学同人、（2019）。
• 梅谷俊治：「しっかり学ぶ数理最適化 モデルからアルゴリズムまで」、講談社(KS情報科学専門書)、ISBN 978-4065212707、（2020年10月26日）。

学習用の参考となる図書は数が多いため、今後もまだ追記していく予定。

外部リンク

• COIN-OR—Computational Infrastructure for Operations Research
• Decision Tree for Optimization Software Links to optimization source codes
• Global optimization
• Mathematical Programming Glossary
• Mathematical Programming Society
• NEOS Guide currently being replaced by the NEOS Wiki
• Optimization Online A repository for optimization e-prints
• Optimization Related Links
• Convex Optimization I EE364a: Course from Stanford University
• Convex Optimization – Boyd and Vandenberghe Book on Convex Optimization
• Book and Course on Optimization Methods for Engineering Design
• 梅谷俊治：「60分で学ぶ数理最適化」（スライド、2020年6月16日）