数理最適化
数学の計算機科学やオペレーションズリサーチの分野における数理最適化(すうりさいてきか、mathematical optimization)とは、(ある条件に関して)最もよい元を、利用可能な集合から選択することをいう。
最も簡単な最適化問題には、ある許された集合から入力をシステマティックに選び、函数の値を計算することによる実数函数の最大化と最小化がある。最適化理論とその手法の、他の形式への一般化は応用数学の広範な分野をなすものである。より一般に、最適化はある与えられた定義域(あるいは制約の集合)についてある目的函数の「利用可能な最も良い」値を見つけることも含む。そのような目的函数と定義域は多様な異なるタイプのものも含む。
最適化問題は、次のように表現される:
与えられるもの:ある集合 A から実数への函数 f : A \to R
目的:A 内のすべての x に対して最小化問題であれば f(x0) ≤ f(x) を満たす A 内の元 x0(最小点)と、あるいは最大化問題であれば f(x0) ≥ f(x) を満たす A 内の元 x0(最大点)を見つけること。
このような問題は最適化問題あるいは数理計画問題(コンピュータプログラミングとは直接的には関係ないが、例えば線型計画法では用いられる)と呼ばれる。多くの実世界での問題や理論的問題は、一般的な枠組みでモデル化される。物理学やコンピュータビジョンの分野における、この手法による問題は、エネルギー最小化(energy minimization)と呼ばれることもある。この場合、函数 f の値はモデル化されるシステムのエネルギーを表す。
典型的に集合 A はユークリッド空間 Rn の部分集合であり、しばしばある制約 (数学)の集合によって特徴づけられ、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* はその(十分小さな)近傍内での最小点である。局所最大解も同様に定義される。
対比して問題の可能領域A全体における最小点のことを大域(的な)最小点ということがある。
最適化問題では、しばしば特殊な記号が用いられる。ここではそれらのいくつかを紹介する。
次の記号を考える:
\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 の最大値を意味する。この場合、目的函数は非有界なのでそのような最大値は存在せず、「無限大」あるいは「定義されない」が答えとなる。
次の記号を考える。
\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] において目的函数 x2 + 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(シンプレックス法)を出版し、ジョン・フォン・ノイマンは同年に双対性の理論を発展させた。
その他の主要な数理最適化の研究者を以下に挙げる:
G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (eds.): "Optimization", Elsevier, (1989).
R. Fletcher: "Practical Methods of Optimization", 2nd Ed.,Wiley (2000).
Jorge Nocedal and Stephen J. Wright: "Numerical Optimization", 2nd Ed., Springer (2006).
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日)。
矢部博、八巻直一:「非線形計画法」(FD付き)、朝倉書店 (応用数値計算ライブラリ)、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)。
山本芳嗣(編著):「基礎数学— IV.最適化理論」、東京化学同人、(2019)。
梅谷俊治:「しっかり学ぶ数理最適化 モデルからアルゴリズムまで」、講談社(KS情報科学専門書)、ISBN 978-4065212707、(2020年10月26日)。
Mykel J. Kochenderfer,Tim A. Wheeler:「最適化アルゴリズム」、共立出版、ISBN 978-4-320124929、(2022年12月23日)。
飯塚秀明:「連続最適化アルゴリズム」、オーム社、ISBN 978-4-274-23006-6、(2023年2月25日)。