最適化問題

数学、工学、コンピュータサイエンス、経済学において、最適化問題とは、すべての実行可能な解の中から最善の解を見つける問題です。

最適化問題は、変数が連続か離散かによって 2 つのカテゴリに分けられます。

• 離散変数を持つ最適化問題は離散最適化と呼ばれ、整数、順列、グラフなどのオブジェクトを可算集合から見つける必要があります。
• 連続変数の問題は連続最適化と呼ばれ、連続関数から最適値を見つける必要があります。これには制約問題やマルチモーダル問題が含まれます。

連続最適化問題の標準形は^[1] で あり、 $${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {最小化} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{j}(x)=0,\quad j=1,\dots ,p\end{aligned}}}$$

• f  : ℝ ⁿ → ℝはn変数ベクトルx上で最小化される目的関数であり、
• g _i ( x ) ≤ 0は不等式制約と呼ばれる
• h _j ( x ) = 0は等式制約と呼ばれ、
• m ≥ 0かつp ≥ 0。

m = p = 0の場合、問題は制約のない最適化問題です。慣例により、標準形式は最小化問題を定義します。最大化問題は、目的関数を 否定することで扱うことができます。

正式には、組合せ最適化問題Aは4重項^[要出典] （I、f、m、g）であり、ここで

• I はインスタンスの集合です。
• インスタンスx∈Iが与えられた場合、f ( x )は実行可能解の集合である。
• インスタンスxとxの実行可能解yが与えられた場合、m ( x , y )はyの測度を表します。これは通常、正の実数です。
• g は目標関数であり、minまたはmax のいずれかです。

目標は、あるインスタンスxに対して最適解、つまり実現可能な解yを 見つけることです。$${\displaystyle m(x,y)=g\left\{m(x,y'):y'\in f(x)\right\}.}$$

各組み合わせ最適化問題には、特定の測度m ₀に対して実行可能なソリューションが存在するかどうかを問う、対応する決定問題があります。たとえば、頂点uとv を含むグラフGがある場合、最適化問題は「最も少ないエッジを使用するuからvへのパスを見つける」などです。この問題の答えは、たとえば 4 である可能性があります。対応する決定問題は、「10 個以下のエッジを使用するuからvへのパスが存在するか」などです。この問題は、単純に「はい」または「いいえ」で答えることができます。

近似アルゴリズムの分野では、アルゴリズムは難しい問題に対して最適に近い解を見つけるために設計されています。通常の決定バージョンは、許容可能な解のみを指定するため、問題の不十分な定義となります。適切な決定問題を導入することはできますが、この問題は最適化問題として特徴付けられる方が自然です。^[2]

• 計数問題（複雑性）  – 計算問題の種類
• 設計の最適化
• エケランドの変分原理 – いくつかの最適化問題にはほぼ最適な解が存在すると主張する定理フォールバックとしてウィキデータの説明を表示するページ
• 関数問題 – 計算問題の種類
• 手袋の問題
• オペレーションズリサーチ – 高度な分析手法の応用に関する分野
• 満足度 – 受け入れ可能な決定を探す認知ヒューリスティック。最適なものを見つける必要はなく、「十分に良い」解決策を見つけるだけで十分です。
• 探索問題 – 二項関係で表される計算問題の種類フォールバックとしてウィキデータの説明を表示するページ
• 半無限計画法 - 有限個の変数と無限個の制約を持つ最適化問題、または無限個の変数と有限個の制約を持つ最適化問題フォールバックとしてウィキデータの説明を表示するページ

• 「トラフィックシェーピングがネットワーク帯域幅を最適化する仕組み」IPC 2016 年 7 月 12 日2017 年2 月 13 日閲覧。