最適化問題

Poll without page-refresh

Article on other languages:

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

数学における最適化問題（さいてきかもんだい、optimization problem）とは、特定の集合上で定義された実数値関数または整数値関数についてその値が最大（もしくは最小）となる状態を解析する問題である。数理計画問題（すうりけいかくもんだい、mathematical programming problem）、数理計画とも呼ばれる。実世界の現象の数理的な解析に関わる問題や抽象的な理論の多くをこの最適化問題という一般的なくくりに入れることができる。物理学やコンピュータビジョンにおける最適化問題は、考えている関数をモデル化された系のエネルギーを表すものと見なすことによって、エネルギー最小化問題と呼ばれることもある。

最適化問題を数学的に記述するならば

与えられたf: A → R について、 $x_0 \in A: \forall x \in A, f(x_0) \geq f(x)$ なるx₀をもとめよ（最大化の問題）

という問題になる。最小化の問題の場合には $\forall x \in A, f(x_0) \le f(x)$ なるx₀を探すことになる。このときの関数fを目的関数 (objective function, cost -) と呼び、fに代入されるべきものが集合Aに含まれているという条件のことを制約条件と呼ぶ。制約条件の集合Aは普通ユークリッド空間Rⁿの部分集合として実現され、Aの元は可能解 (feasible solution, candidate -) と呼ばれる。目的関数を最大（あるいは最小）にするような可能解は最適解と呼ばれる。

最適化問題に属する問題

最適化問題は目的関数や制約条件の種類によっていくつかの問題のクラスに分けることができる。

線形計画問題: 目的関数が線型写像として表され、制約条件の集合が一次方程式・一次不等式によって定義されている場合。
整数計画問題: 線型計画問題のうち、各変数のとる値が整数に制限されている場合。
2次計画問題: 目的関数が2次式で定義され、制約条件の集合が一次方程式・一次不等式によって定義されている場合。
凸計画問題: 目的関数が凸関数で、制約条件の集合も凸集合である場合。
半正定値計画問題: 半正定値行列に関する凸計画問題。

計算理論の問題のクラス

歴史

最適化問題的な手法の最も古いあらわれはカール・フリードリッヒ・ガウスまでさかのぼることができる最急降下法 (steepest descent) である。歴史的に始めに導入された用語は1940年代にジョージ・ダンツィクによって作られた「線型計画法」(linear programming) である。このprogrammingは現在のコンピュータプログラミングとは別のものであり、アメリカ合衆国軍における訓練・補給の予定をさす言葉としてのprogramからきている。最適化問題の発展に貢献した数学者として