最適化問題

最適化問題（さいてきかもんだい、）とは、特定の集合上で定義された実数値関数または整数値関数についてその値が最小（もしくは最大）となる状態を解析する問題である。こうした問題は総称して数理計画問題（すうりけいかくもんだい、, mathematical program）、数理計画とも呼ばれる。最適化問題は、自然科学、工学、社会科学などの多種多様な分野で発生する基本的な問題の一つであり、その歴史は18世紀の変分問題に遡る。1940年代に線型計画法が登場して以来、理論的な研究や数値解法の研究が非常に活発に行われ、その応用範囲はいろいろな分野に拡大されていった。実世界の現象の数理的な解析に関わる問題や抽象的な理論の多くをこの最適化問題という一般的なくくりに入れることができる。物理学やコンピュータビジョンにおける最適化問題は、考えている関数をモデル化された系のエネルギーを表すものと見なすことによって、エネルギー最小化問題と呼ばれることもある。
定義.
最適化問題を数学的に記述すると、最小化問題の場合
となる。最大化問題の場合には formula_4 となる formula_3 を探すことになる。最大化問題はformula_6のように目的関数の符号を反転させることにより等価な最小化問題に書き直せるので、最小化用のアルゴリズムが使える。
このときの関数 formula_7を目的関数 () と呼び、探すべき変数 formula_8 が集合 formula_9 に含まれるという条件のことを制約条件、制約関数()と呼ぶ。制約条件の集合 A を実行可能領域()あるいは許容領域と呼び、その元(要素)を実行可能解、可能解、許容解 () などと呼ぶ。目的関数を最小あるいは最大にするような実行可能解を（大域的）最小解、最大解と呼び、そのときの目的関数値を最小値、最大値と呼ぶ。また最小・最大を区別しないで最適解、最適値() とも呼ばれる。なお、ここで「領域」という用語は単に「集合」と同じ意味で使っている。また「解」は「点」と同義語である。したがって実行可能集合とか実行可能点などということもある。（この分野での伝統的・慣習的表現であり、数学的な意味の「領域＝連結な開集合」，「解＝問題の(最終的つまり最適)解」ということではないので注意。）
問題の分類.
最適化問題（数理計画問題）は、いろいろな観点・切り口によって多種多様に分類されるが、基本的な分類として以下がある。
まず考える集合 A の含まれる空間によって、無限次元と有限次元の問題に大別される。すなわち、A が関数空間に含まれる場合、無限次元の最適化問題となり、変分問題や最適制御問題が代表的である。A がユークリッド空間に含まれる場合は、有限次元の最適化問題となる。
また A が全空間のように実質的に制約条件がない問題は無制約問題（制約なし問題）となり、そうでない場合は有制約問題（制約付き問題）となる。
以下、それ以外の分類を有限次元の場合で説明する。
最適化問題は目的関数や制約条件の種類によっていくつかの問題クラスに分けることができる。
連続最適化問題.
連続最適化問題（）とは、制約条件の集合 A がユークリッド空間 formula_10 の部分集合の物。
無制約問題を解析的に解く場合は、最適性の必要条件（偏微分を取って 0 ）を満たす点の中に最小解がある。束縛条件がある場合はラグランジュの未定乗数法が使える。
導関数が必要なアルゴリズム.
導関数が必要なアルゴリズムを勾配法という。以下は、勾配法のアルゴリズム。
MathematicaのFindMinimumのデフォルトの設定は、制約条件付きは内点法、目的関数が平方和の場合はレーベンバーグ・マーカート法を使い、そうで無い場合はBFGS法を使い、250次元以上の場合L-BFGS法を使う。
導関数が不要なアルゴリズム.
以下は、導関数が不要（）なアルゴリズム。
MathematicaのNMinimumのデフォルトの設定は、線形計画問題ならば単体法を使い、整数パラメータがある場合などは差分進化を使い、それ以外はNelder-Mead法を使う。
1次元用.
2次元以上に対応している連続最適化問題のアルゴリズムでも内部で1次元用のアルゴリズムを使用している場合も多い。以下は、1次元用のアルゴリズム。
線形計画問題用.
以下は線形計画問題用のアルゴリズム。
離散最適化問題.
離散最適化問題（）とは、制約条件の集合 A が formula_11 の部分集合の物。詳細は組合せ最適化を参照。
歴史.
最適化問題としての手法の最も古い登場はカール・フリードリッヒ・ガウスまでさかのぼることができる最急降下法 (steepest descent) である。歴史的に始めに導入された用語は1940年代にジョージ・ダンツィクによって作られた「線型計画法」(linear programming) である。この（「計画法」と訳される）"programming"という語の由来は、コンピュータなどのプログラムを書く、機器を設定する、といった意味の「プログラミング」とは別で、軍などにおける（特に、この分野では先行していた米国において、アメリカ軍の用語としての）訓練・補給の予定、という語の"program"からきている。最適化問題の発展に貢献した数学者として
らがあげられる。