最適化問題(さいてきかもんだい、英: optimization problem)とは、特定の集合上で定義された実数値関数または整数値関数についてその値が最小(もしくは最大)となる状態を解析する問題である[1]。こうした問題は総称して数理計画問題(すうりけいかくもんだい、英: mathematical programming problem, mathematical program)、数理計画とも呼ばれる[1]。最適化問題は、自然科学、工学、社会科学などの多種多様な分野で発生する基本的な問題の一つであり、その歴史は18世紀の変分問題に遡る[2]。1940年代に線型計画法が登場して以来、理論的な研究や数値解法の研究が非常に活発に行われ、その応用範囲はいろいろな分野に拡大されていった[1]。実世界の現象の数理的な解析に関わる問題や抽象的な理論の多くをこの最適化問題という一般的なくくりに入れることができる。物理学やコンピュータビジョンにおける最適化問題は、考えている関数をモデル化された系のエネルギーを表すものと見なすことによって、エネルギー最小化問題と呼ばれることもある。 最適化問題を数学的に記述すると、最小化問題の場合与えられた関数 f : A → R {\displaystyle f:A\to \mathbb {R} } について、 x 0 ∈ A : ∀ x ∈ A , f ( x 0 ) ≤ f ( x ) {\displaystyle x_{0}\in A:\forall x\in A,\ f(x_{0})\leq f(x)} なる x 0 {\displaystyle x_{0}} を求めよ となる。最大化問題の場合には ∀ x ∈ A , f ( x 0 ) ≥ f ( x ) {\displaystyle \forall x\in A,f(x_{0})\geq f(x)} となる x 0 {\displaystyle x_{0}} を探すことになる。最大化問題は max f ( x ) = min ( − f ( x ) ) {\displaystyle \max f(x)=\min(-f(x))} のように目的関数の符号を反転させることにより等価な最小化問題に書き直せるので、最小化用のアルゴリズムが使える[3]。 このときの関数 f {\displaystyle f} を目的関数 (英: objective function, cost function) と呼び、探すべき変数 x {\displaystyle x} が集合 A {\displaystyle A} に含まれるという条件のことを制約条件、制約関数(英: constraint,constraint function)と呼ぶ[1]。制約条件の集合 A を実行可能領域(英: feasible region)あるいは許容領域と呼び、その元(要素)を実行可能解、可能解、許容解 (英: feasible solution, candidate solution) などと呼ぶ[4]。目的関数を最小あるいは最大にするような実行可能解を(大域的)最小解、最大解と呼び、そのときの目的関数値を最小値、最大値と呼ぶ。また最小・最大を区別しないで最適解、最適値(英: optimal solution) とも呼ばれる[5]。なお、ここで「領域」という用語は単に「集合」と同じ意味で使っている。また「解」は「点」と同義語である。したがって実行可能集合とか実行可能点などということもある。(この分野での伝統的・慣習的表現であり、数学的な意味の「領域=連結な開集合」,「解=問題の(最終的つまり最適)解」ということではないので注意。) 最適化問題(数理計画問題)は、いろいろな観点・切り口によって多種多様に分類されるが、基本的な分類として以下がある。 まず考える集合 A の含まれる空間によって、無限次元と有限次元の問題に大別される。すなわち、A が関数空間に含まれる場合、無限次元の最適化問題となり、変分問題や最適制御問題が代表的である。A がユークリッド空間に含まれる場合は、有限次元の最適化問題となる。 また A が全空間のように実質的に制約条件がない問題は無制約問題(制約なし問題)となり、そうでない場合は有制約問題(制約付き問題)となる。 以下、それ以外の分類を有限次元の場合で説明する。 最適化問題は目的関数や制約条件の種類によっていくつかの問題クラスに分けることができる。 連続最適化問題(英: continuous optimization problem)とは、制約条件の集合 A がユークリッド空間 R n {\displaystyle \mathbb {R} ^{n}} の部分集合の物。 無制約問題を解析的に解く場合は、最適性の必要条件(偏微分を取って 0 )を満たす点の中に最小解がある。束縛条件がある場合はラグランジュの未定乗数法が使える。
定義
問題の分類
線型計画問題
目的関数が1次式として表され、制約条件の集合が一次方程式・一次不等式によって定義されている場合。
整数計画問題
線型計画問題のうち、各変数のとる値が整数に制限されている場合。
2次計画問題
目的関数が2次式
凸計画問題
目的関数が凸関数で、制約条件の集合も凸集合である場合。
半正定値計画問題
半正定値行列を変数とする凸計画問題。
非線型計画問題
目的関数や制約条件に非線型なものが含まれる場合。
連続最適化問題詳細は「数理最適化」を参照
導関数が必要なアルゴリズム - 勾配法における2つの主要な反復法の枠組み
最急降下法 - 最も単純な勾配法
確率的勾配降下法 - 最急降下法のオンライン学習版(ニューラルネットワークなどで使用)
AdaGrad - 学習率の自動調整を行う
RMSProp
Adam
共役勾配法
双共役勾配法
非線形共役勾配法
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]。 2次元以上に対応している連続最適化問題のアルゴリズムでも内部で1次元用のアルゴリズムを使用している場合も多い。以下は、1次元用のアルゴリズム。
1次元用
黄金分割探索