最適化問題 📖 Wikipedia

最適化問題（さいてきかもんだい、（英: optimization problem）は特定の集合上で定義された実数値関数または整数値関数についてその値が最小（もしくは最大）となる状態を解析する問題である^[1]。数理計画問題（すうりけいかくもんだい、（英: mathematical programming problem）^[1]、エネルギー最小化問題（エネルギーさいしょうかもんだい）^{[注 1]}とも。

数理最適化は自然科学・工学・社会科学など様々な分野で利用されるため、最適化問題は基本的な問題の一つである。実世界の現象の数理的な解析に関わる問題や抽象的な理論の多くをこの最適化問題という一般的なくくりに入れることができる。その歴史は18世紀の変分問題まで遡れ^[2]、1940年代には線型計画法で線形最適化問題（線型計画問題）が定式化され、その後も様々なサブクラスが提案・研究されている（詳細は 数理最適化#歴史）^[1]。

ここでは最小化問題をもって最適化問題を定義する（参考: #最小化と最大化が等価）。

${\displaystyle A}$ を集合、${\displaystyle \mathbb {R} }$ を実数全体の集合、${\displaystyle f:A\to \mathbb {R} }$ を関数とする。最適化問題は次の問題である：

このとき ${\displaystyle f}$ を目的関数（もくてきかんすう、（英: objective function）又は 英: cost function、${\displaystyle A}$ を実行可能領域^[3]、${\displaystyle x\in A}$ を実行可能解^[4]、${\displaystyle A}$ を規定する条件を制約^[1]、${\displaystyle x_{0}}$ を最適解（さいてきかい、（英: optimal solution）^[5]、${\displaystyle \textstyle f(x_{0})}$ を最適値（さいてきち）^[5]と呼ぶ。

つまり、最適化問題とは、制約が規定する実行可能領域 ${\displaystyle A}$ のなかから目的関数 ${\displaystyle f}$ を最小化する実行可能解 ${\displaystyle x_{0}}$ を求める問題である。

数理最適化の慣習として「解」は「点」と同義であり（言い換え例: 実行可能点）、これは「問題の（最適）解」を指す語ではない。また、最小化問題であることを強調する場合は ${\displaystyle x_{0}}$ を最小解、${\displaystyle \textstyle f(x_{0})}$ を最小値と呼ぶ。

最適化問題において最小化問題と最大化問題は等価である。

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

最大化問題あることを強調する場合、${\displaystyle x_{0}}$ を最大解、${\displaystyle \textstyle f(x_{0})}$ を最大値とも呼ぶ。

最適化問題は様々な観点から分類できる。

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

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

有限次元の場合、最適化問題は目的関数・制約（実行可能領域）に基づき分類できる：

• 線型計画問題: 目的関数が一次関数、各制約が一次方程式/不等式
  • 整数計画問題: 変数が整数
• 非線形計画問題: 目的関数・制約が非線型
  • 2次計画問題: 目的関数が二次関数、各制約が一次方程式/不等式
• 凸計画問題: 目的関数が凸関数、実行可能領域が凸集合
  • 半正定値計画問題: 変数が半正定値行列
• 二次錐計画問題: 実行可能領域が二次錐

連続最適化問題（英: continuous optimization problem）とは、制約条件の集合 A がユークリッド空間 ${\displaystyle \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のデフォルトの設定は、制約条件付きは内点法^[7]、目的関数が平方和の場合はレーベンバーグ・マーカート法を使い^[8]、そうで無い場合はBFGS法を使い、250次元以上の場合L-BFGS法を使う^[9]。

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

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

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

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

• 黄金分割探索
• ブレント法

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

• 単体法
• 楕円体法
• カーマーカー法

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

• P
• NP
• co-NP

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

• 数理最適化
• メタヒューリスティクス
• 組合せ最適化
• 双対問題