数学 の計算機科学 やオペレーションズリサーチ の分野における数理最適化 (すうりさいてきか、英 : mathematical optimization )または数理計画法 (英 : mathematical programming )とは、(ある条件に関して)最もよい元を、利用可能な集合から選択することをいう[1] 。
f(x , y ) = −(x ² + y ²) + 4 で与えられる放物面 のグラフ。(0, 0, 4) での最大値が赤い点で示されている。
最も簡単な最適化問題 には、ある許された集合から入力をシステマティックに選び、函数 の値を計算することによる実数函数 (英語版 ) の最大化と最小化 がある。最適化理論とその手法の、他の形式への一般化は応用数学 の広範な分野をなすものである。より一般に、最適化はある与えられた定義域(あるいは制約の集合)についてある目的函数の「利用可能な最も良い」値を見つけることも含む。そのような目的函数と定義域は多様な異なるタイプのものも含む。
最適化問題は、次のように表現される:
与えられるもの :ある集合 A から実数 への函数 f : A
→
{\displaystyle \to }
R
目的 :A 内のすべての x に対して最小化問題であれば f (x 0 ) ≤ f (x ) を満たす A 内の元 x 0 (最小点)と、あるいは最大化問題であれば f (x 0 ) ≥ f (x ) を満たす A 内の元 x 0 (最大点)を見つけること。
このような問題は最適化問題 (optimization)あるいは数理計画問題 (mathematical programming)(コンピュータプログラミング とは直接的には関係ないが、例えば線型計画法 では用いられる)と呼ばれる。多くの実世界での問題や理論的問題は、一般的な枠組みでモデル化される。物理学 やコンピュータビジョン の分野における、この手法による問題は、エネルギー最小化(energy minimization)と呼ばれることもある。この場合、函数 f の値はモデル化されるシステムのエネルギーを表す。
典型的に集合 A はユークリッド空間 R n の部分集合 であり、しばしばある制約 (英語版 ) の集合によって特徴づけられ、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 が存在して、
‖
x
−
x
∗
‖
≤
δ
;
{\displaystyle \|\mathbf {x} -\mathbf {x} ^{*}\|\leq \delta ;\,}
を満たすような任意の x に対して次が成立することをいう。
f
(
x
∗
)
≤
f
(
x
)
.
{\displaystyle f(\mathbf {x} ^{*})\leq f(\mathbf {x} ).}
すなわち、点 x* はその(十分小さな)近傍内での最小点である。局所最大解も同様に定義される。
対比して問題の可能領域A 全体における最小点のことを大域(的な)最小点ということがある。
最適化問題では、しばしば特殊な記号が用いられる。ここではそれらのいくつかを紹介する。
函数の最小値と最大値
次の記号を考える:
min
x
∈
R
(
x
2
+
1
)
.
{\displaystyle \min _{x\in \mathbb {R} }\;(x^{2}+1).}
これは x を実数 の集合
R
{\displaystyle \mathbb {R} }
から選んだときの目的函数
x
2
+
1
{\displaystyle x^{2}+1}
の最小値を意味する。この場合の最小値は
x
=
0
{\displaystyle x=0}
のときの
1
{\displaystyle 1}
である。
同様に、記号
max
x
∈
R
2
x
{\displaystyle \max _{x\in \mathbb {R} }\;2x}
は、任意の実数 x に対する目的函数 2x の最大値を意味する。この場合、目的函数は非有界なのでそのような最大値は存在せず、「無限大」あるいは「定義されない」が答えとなる。
最適入力引数
次の記号を考える。
a
r
g
m
i
n
x
∈
(
−
∞
,
−
1
]
(
x
2
+
1
)
.
{\displaystyle {\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;(x^{2}+1).}
あるいは、次の同値なものを考える。
a
r
g
m
i
n
x
(
x
2
+
1
)
,
subject to:
x
∈
(
−
∞
,
−
1
]
.
{\displaystyle {\underset {x}{\operatorname {arg\,min} }}\;(x^{2}+1),\;{\text{subject to:}}\;x\in (-\infty ,-1].}
これは、区間
(
−
∞
,
−
1
]
{\displaystyle (-\infty ,-1]}
において目的函数 x 2 + 1 を最小化する引数 x 自身の値を与える(その函数の最小値がどのような値であるかはここでは問題とされない)。この場合、x = 0 は不可能、すなわち実行可能領域 (英語版 ) に属さないため、答えは x = -1 となる。
同様に
a
r
g
m
a
x
x
∈
[
−
5
,
5
]
,
y
∈
R
x
cos
(
y
)
{\displaystyle {\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos(y)}
あるいは
a
r
g
m
a
x
x
,
y
x
cos
(
y
)
,
subject to:
x
∈
[
−
5
,
5
]
,
y
∈
R
{\displaystyle {\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos(y),\;{\text{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} }
は、x が区間
[
−
5
,
5
]
{\displaystyle [-5,5]}
に属するという制約の下で、目的函数
x
cos
(
y
)
{\displaystyle x\cos(y)}
の値を最大化する
(
x
,
y
)
{\displaystyle (x,y)}
のペアを意味する(再び、その関数の最大値については問われていない)。この場合の解は、すべての整数 k に対する (5, 2kπ ) と (−5,(2k+1)π) である。
arg min と arg max はしばしば、argmin および argmax と書かれることもあり、それらは「最小値の引数」および「最大値の引数」を意味する。
フェルマー とラグランジュ は最適解を求める上で微分積分学に基づく方法を発見した。一方でニュートン とガウス は最適解へ収束する反復法を提唱した。
ある種の最適化に関する線型計画法 という語はジョージ・ダンツィク によるものである。一方で、1939年にレオニート・カントロヴィチ によって多くの理論が構築された(この文脈における「計画法(programming)」はコンピュータ・プログラミング とは異なり、アメリカ軍隊によって訓練や物流 のスケジュールを表すために用いられていた "program" (講演会などの"プログラム"と同様の意味)が語源である。ダンツィクは当時その研究をしていた)。ダンツィクは1947年に Simplex Algorithm(シンプレックス法 )を出版し、ジョン・フォン・ノイマン は同年に双対性 の理論を発展させた。
その他の主要な数理最適化の研究者を以下に挙げる:
国内
国外
W. Erwin Diewert (2008). "cost functions," The New Palgrave Dictionary of Economics , 2nd Edition Contents .
外国語図書
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日)。
Mykel J. Kochenderfer and Tim A. Wheeler: "Algorithms for Optimization", The MIT Press, ISBN 978-0262039420 (2019). ※ 邦訳版あり。
Vladislav Bukshtynov: "Optimization: Success in Practice", CRC Press (Taylor & Francis), ISBN 978-1-032229478 (2023) .
Rosario Toscano: "Solving Optimization Problems with the Heuristic Kalman Algorithm: New Stochastic Methods", Springer,ISBN 978-3-031-52458-5 (2024年3月22日). 日本語図書