数理最適化

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

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

最適化問題[編集]

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

与えられるもの：ある集合 A から実数への函数 f : A ${\displaystyle \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）と呼ばれる^[2]。目的函数を最小化（あるいは最大化）する可能解は、最適解と呼ばれる。

数学においてよくある最適化問題は、最小化に関するものである。最小化問題においては，「可能領域が凸領域でかつ目的函数がそこに於ける凸関数」となっていない場合には，一般に複数の局所最小解が存在しうる。ここで　x^*　が局所最小解であるとは、ある定数 δ > 0 が存在して、

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

を満たすような任意の x に対して次が成立することをいう。

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

すなわち、点 x^* はその（十分小さな）近傍内での最小点である。局所最大解も同様に定義される。

対比して問題の可能領域A全体における最小点のことを大域（的な）最小点ということがある。

記号[編集]

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

函数の最小値と最大値[編集]

次の記号を考える：

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

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

同様に、記号

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

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

最適入力引数[編集]

次の記号を考える。

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

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

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

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

同様に

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

あるいは

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

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

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

歴史[編集]

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

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

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

関連項目[編集]

脚注[編集]

雑誌[編集]

• 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

学習用参考図書など[編集]

外国語図書

• Philip E. Gill, Walter Murray and Margaret H. Wright: "Practical Optimization", Emerald group publishing, ISBN 978-0-12-283952-8 (1982).
• G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (eds.): "Optimization", Elsevier, (1989).
• Stanislav Walukiewicz："Integer Programming", Springer，ISBN 978-9048140688（1990年12月）。
• R. Fletcher: "Practical Methods of Optimization", 2nd Ed.,Wiley (2000).
• Panos M. Pardalos："Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems"，Springer，ISBN 978-1441948298（2000年7月）。
• Xiaoqi Yang (編), K. L. Teo (編), Lou Caccetta (編)："Optimization Methods and Applications"，Springer, ISBN 978-0792368663 (2001年4月1日）。
• Panos M. Pardalos (編), Mauricio G. C. Resende (編)："Handbook of Applied Optimization"、Oxford Univ Pr on Demand，ISBN 978-0195125948（2002年2月22日）。
• Boyd and Vandenberghe: "Convex Optimization", Cambridge Univ. Press (2004).
• Jorge Nocedal and Stephen J. Wright: "Numerical Optimization", 2nd Ed., Springer (2006).
• Wil Michiels, Emile Aarts, Jan Korst: "Theoretical Aspects of Local Search",　Springer, ISBN 978-3642071485（2006年11月28日）。
• Der-San Chen, Robert G. Batson, Yu Dang：”Applied Integer Programming: Modeling and Solution”，Wiley，ISBN 978-0470373064（2010年1月12日）。
• Vladislav Bukshtynov: "Optimization: Success in Practice", CRC Press (Taylor & Francis), ISBN 978-1-032229478 (2023) .

日本語図書

• 今野浩、山下浩：「非線形計画法」、日科技連出版社 (ORライブラリー 6)、ISBN: 978-4817153067、（1978年3月）。
• 茨木俊秀、福島雅夫：「最適化の手法」、共立出版(情報数学講座)、ISBN 978-4320026643、（1993年7月）。
• G.L. Nemhauser (編), M.J. Todd (編), A.H.G. Rinnooy Kan (編)：「最適化ハンドブック」、朝倉書店、ISBN978-4254121025、（1995年10月1日）。
• 矢部博、八巻直一：「非線形計画法」（ＦＤ付き）、朝倉書店 (応用数値計算ライブラリ)、ISBN 978-4254114898、（1999年6月）。
• 田村明久、村松正和：「最適化法」、共立出版 (工系数学講座 17)、ISBN 978-4320016163、（2002年4月1日）。
• 久保幹雄、田村明久、松井知己(編)：「応用数理ハンドブック」、朝倉書店、（2002）。
• 金谷健一：「これなら分かる最適化数学―基礎原理から計算手法まで」、共立出版、ISBN 978-4320017863、（2005年9月1日）。
• 矢部博：「工学基礎 最適化とその応用」、数理工学社 (新・工科系の数学)、ISBN 978-4901683340、（2006年4月1日）。
• 山下信雄、福嶋雅夫：「数理計画法」、コロナ社、（2008）。
• 加藤直樹：「数理計画法」、コロナ社、（2008）。
• 福島雅夫：「数理計画入門(新版)」、朝倉書店、（2011）。
• 茨木俊秀：「最適化の数学」、共立出版(共立講座 21世紀の数学　13)、ISBN 978-4320015654、（2011年6月23日）。
• 久野誉人、繁野麻衣子、後藤順哉：「数理最適化」、オーム社、（2012年8月）。
• 山本芳嗣(編著)：「基礎数学— IV.最適化理論」、東京化学同人、（2019）。
• 梅谷俊治：「しっかり学ぶ数理最適化 モデルからアルゴリズムまで」、講談社(KS情報科学専門書)、ISBN 978-4065212707（2020年10月26日）。
• 福田公明、田村明久：「計算による最適化入門」、共立出版（シリーズ、コンピュータが育む数学の展開）、ISBN 9784320115217（2022年7月25日）.
• Mykel J. Kochenderfer，Tim A. Wheeler：「最適化アルゴリズム」、共立出版、ISBN 978-4-320124929、（2022年12月23日）。
• 飯塚秀明：「連続最適化アルゴリズム」、オーム社、ISBN 978-4-274-23006-6、（2023年2月25日）。
• 小林和博：「Juliaによる数理最適化」、コロナ社、ISBN 978-4339029345、（2023年4月12日）。
• 佐藤寛之：「多様体上の最適化理論」、オーム社、ISBN978-4274231186(2024年1月29日）.

外部リンク[編集]

この節の外部リンクはウィキペディアの方針やガイドラインに違反しているおそれがあります。過度または不適切な外部リンクを整理し、有用なリンクを脚注で参照するよう記事の改善にご協力ください。

• 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日）
• Scipy Lecture Notes, 第2.7節. "数学的最適化: 関数の最小値を求める"
• 連続最適化および関連分野に関する夏季学校 統計数理研究所）
  • 2021年（第1回目）
  • 2022年（第2回目）
  • 2023年（第3回目）

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