最適化問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

定義[編集]

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

与えられた f: A \to \mathbb{R} について、x_0 \in A: \forall x \in A,\ f(x_0) \le f(x) なる x_0 をもとめよ(最小化の問題)

という問題になる。最大化の問題の場合には \forall x \in A, f(x_0) \ge f(x) なるx_0 を探すことになる。通常は目的関数の符号を反転させれば、最小化用のアルゴリズムが使える。

このときの関数 f を目的関数 (: objective function, cost function) と呼び、fに代入されるべきものが集合 A に含まれているという条件のことを制約条件と呼ぶ。制約条件の集合 A の元は可能解 (: feasible solution, candidate solution) と呼ばれる。目的関数を最小(あるいは最大)にするような可能解は最適解と呼ばれる。

問題の分類[編集]

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

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

連続最適化問題[編集]

連続最適化問題(: continuous optimization problem)とは、制約条件の集合 A がユークリッド空間 \mathbb{R}^n の部分集合の物。

導関数が必要なアルゴリズム[編集]

導関数が必要なアルゴリズムを勾配法という。以下は、勾配法のアルゴリズム。

MathematicaのFindMinimumのデフォルトの設定は、制約条件付きは内点法[1]、目的関数が平方和の場合はレーベンバーグ・マーカート法を使い[2]、そうで無い場合はBFGS法を使い、250次元以上の場合L-BFGS法を使う[3]

導関数が不要なアルゴリズム[編集]

以下は、導関数が不要(: Derivative-free optimization)なアルゴリズム。

MathematicaのNMinimumのデフォルトの設定は、線形計画問題ならば単体法を使い、整数パラメータがある場合などは差分進化を使い、それ以外はNelder-Mead法を使う[4]

1次元用[編集]

2次元以上に対応している連続最適化問題のアルゴリズムでも内部で1次元用のアルゴリズムを使用している場合も多い。以下は、1次元用のアルゴリズム。

線形計画問題用[編集]

以下は線形計画問題用のアルゴリズム。

離散最適化問題[編集]

離散最適化問題(: discrete optimization problem)とは、制約条件の集合 A が \mathbb{Z}^n の部分集合の物。詳細は組合せ最適化を参照。

計算理論の問題のクラス[編集]

歴史[編集]

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

らがあげられる。

参照[編集]

関連項目[編集]