最適化問題

最適化問題（さいてきかもんだい、英: optimization problem）とは、特定の集合上で定義された実数値関数または整数値関数についてその値が最小（もしくは最大）となる状態を解析する問題である^[1]。こうした問題は総称して数理計画問題（すうりけいかくもんだい、英: mathematical programming problem, mathematical program）、数理計画とも呼ばれる^[1]。最適化問題は、自然科学、工学、社会科学などの多種多様な分野で発生する基本的な問題の一つであり、その歴史は18世紀の変分問題に遡る^[2]。1940年代に線型計画法が登場して以来、理論的な研究や数値解法の研究が非常に活発に行われ、その応用範囲はいろいろな分野に拡大されていった^[1]。実世界の現象の数理的な解析に関わる問題や抽象的な理論の多くをこの最適化問題という一般的なくくりに入れることができる。物理学やコンピュータビジョンにおける最適化問題は、考えている関数をモデル化された系のエネルギーを表すものと見なすことによって、エネルギー最小化問題と呼ばれることもある。

定義

最適化問題を数学的に記述すると、最小化問題の場合

与えられた関数

f:A\to \mathbb {R}

について、

x_{0}\in A:\forall x\in A,\ f(x_{0})\leq f(x)

なる

x_{0}

を求めよ

となる。最大化問題の場合には $\forall x\in A,f(x_{0})\geq f(x)$ となる $x_{0}$ を探すことになる。最大化問題は $\max f(x)=\min(-f(x))$ のように目的関数の符号を反転させることにより等価な最小化問題に書き直せるので、最小化用のアルゴリズムが使える^[3]。

このときの関数 $f$ を目的関数 (英: objective function, cost function) と呼び、探すべき変数 $x$ が集合 $A$ に含まれるという条件のことを制約条件、制約関数(英: constraint,constraint function)と呼ぶ^[1]。制約条件の集合 A を実行可能領域(英: feasible region)あるいは許容領域と呼び、その元(要素)を実行可能解、可能解、許容解 (英: feasible solution, candidate solution) などと呼ぶ^[4]。目的関数を最小あるいは最大にするような実行可能解を（大域的）最小解、最大解と呼び、そのときの目的関数値を最小値、最大値と呼ぶ。また最小・最大を区別しないで最適解、最適値(英: optimal solution) とも呼ばれる^[5]。なお、ここで「領域」という用語は単に「集合」と同じ意味で使っている。また「解」は「点」と同義語である。したがって実行可能集合とか実行可能点などということもある。（この分野での伝統的・慣習的表現であり、数学的な意味の「領域＝連結な開集合」，「解＝問題の(最終的つまり最適)解」ということではないので注意。）

問題の分類

最適化問題（数理計画問題）は、いろいろな観点・切り口によって多種多様に分類されるが、基本的な分類として以下がある。

まず考える集合 A の含まれる空間によって、無限次元と有限次元の問題に大別される。すなわち、A が関数空間に含まれる場合、無限次元の最適化問題となり、変分問題や最適制御問題が代表的である。A がユークリッド空間に含まれる場合は、有限次元の最適化問題となる。

また A が全空間のように実質的に制約条件がない問題は無制約問題（制約なし問題）となり、そうでない場合は有制約問題（制約付き問題）となる。

以下、それ以外の分類を有限次元の場合で説明する。

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

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

連続最適化問題

→詳細は「数理最適化」を参照

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

無制約問題を解析的に解く場合は、最適性の必要条件（偏微分を取って 0 ）を満たす点の中に最小解がある。束縛条件がある場合はラグランジュの未定乗数法が使える。

導関数が必要なアルゴリズム

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

直線探索と信頼領域 - 勾配法における2つの主要な反復法の枠組み
最急降下法 - 最も単純な勾配法
- 確率的勾配降下法 - 最急降下法のオンライン学習版（ニューラルネットワークなどで使用）
  - AdaGrad - 学習率の自動調整を行う
  - RMSProp
  - Adam
共役勾配法
- 双共役勾配法
- 非線形共役勾配法
ニュートン法
準ニュートン法
- DFP法
- BFGS法
- BHHH法
- SR1法
- 記憶制限準ニュートン法 - 大規模（高次元）問題に対応した物
  - L-BFGS
    - L-BFGS-B - L-BFGSに定義域の境界を指定できるようにした物
    - OWL-QN - L-BFGSにおいて目的関数にL1正則化項がついた形に対応できるようにした物
ガウス・ニュートン法 - 非線形最小二乗法の問題（平方和の最適化問題）を解く
- レーベンバーグ・マーカート法
内点法

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

導関数が不要なアルゴリズム

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

Nelder-Mead法
座標降下法
- 適応座標降下法
- ブロック座標降下法（block coordinate descent）
Michael J. D. Powell 開発
- Powell法
- BOBYQA - 非線形関数とパラメータの値域で制約
- LINCOA - 非線形関数と線形制約条件
- COBYLA - 非線形関数と非線形制約条件
- TOLMIN
- UOBYQA
- NEWUOA
進化戦略
- CMA-ES
- 自然進化戦略
差分進化

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

1次元用

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

線形計画問題用

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

離散最適化問題

→詳細は「組合せ最適化」を参照

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

計算理論の問題のクラス

歴史

最適化問題としての手法の最も古い登場はカール・フリードリッヒ・ガウスまでさかのぼることができる最急降下法 (steepest descent) である。歴史的に始めに導入された用語は1940年代にジョージ・ダンツィクによって作られた「線型計画法」(linear programming) である。この（「計画法」と訳される）programmingという語の由来は、コンピュータなどのプログラムを書く、機器を設定する、といった意味の「プログラミング」とは別で、軍などにおける（特に、この分野では先行していた米国において、アメリカ軍の用語としての）訓練・補給の予定、という語のprogramからきている。最適化問題の発展に貢献した数学者として

ジョン・フォン・ノイマン
レオニート・カントロヴィチ
Naum Shor
Leonid Khachian
Boris Polyak
ユーリー・ネステロフ
Arkadii Nemirovskii
Michael J. Todd
リチャード・ベルマン
ホアン・トゥイ (数学者)

らがあげられる。

脚注

出典

参考文献

矢部博『工学基礎最適化とその応用』（初版）数理工学社、2006年3月25日。ISBN 4-901683-34-9。