最適化問題

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

離散変数を用いた最適化問題は離散最適化と呼ばれ、整数、順列、グラフなどの対象を可算集合から見つけ出す必要がある。
連続変数を含む問題は連続最適化問題と呼ばれ、連続関数から最適値を求める必要がある。これには制約付き問題や多峰性問題が含まれる。

検索スペース

最適化問題の文脈では、探索空間とは、問題の制約、目標、または目的を満たすすべての可能な点または解の集合を指します。^{[ 1 ]}これらの点は、目的関数に従って最適な解を見つけるために評価できる実行可能な解を表します。探索空間は、多くの場合、最適化される関数の定義域によって定義され、問題の要件を満たすすべての有効な入力を含みます。^{[ 2 ]}

探索空間は、問題によって大きさや複雑さが大きく異なります。例えば、連続最適化問題では、探索空間は境界や制約によって定義される多次元の実数値領域となる場合があります。一方、組み合わせ最適化などの離散最適化問題では、探索空間は有限個の順列、組み合わせ、または構成から構成される可能性があります。

文脈によっては、「探索空間」という用語は、問題を定義するために最も適切な変数やパラメータのセットを決定するなど、ドメイン自体の最適化を指す場合もあります。探索空間を理解し、効果的に活用することは、効率的なアルゴリズムを設計する上で非常に重要です。なぜなら、探索空間は計算の複雑さや最適解を見つける可能性に直接影響を与えるからです。

連続最適化問題

連続最適化問題の標準形式は^[³^{]である。} ${\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&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 \to ℝ$ $は、 n$ 変数ベクトル $x$ に関して最小化される目的関数です。
$g i (x) \leq 0は$ 不等式制約と呼ばれます。
$h j (x) = 0は$ 等式制約と呼ばれ、
$m \geq 0$ かつ $p \geq 0$ 。

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

組み合わせ最適化問題

形式的には、組み合わせ最適化問題 $Aは$ $($ $I$ $、$ $f$ $、$ $m$ $、$ $g$ $)$ の四つ組であり、

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

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

組み合わせ最適化問題ごとに、特定の尺度 $m$ $0$ に対して実行可能な解が存在するかどうかを問う対応する決定問題があります。たとえば、頂点 $u$ と $v$ を含むグラフ $Gがある場合、最適化問題は「$ $uから$ $v$ への経路で、使用する辺の数が最小のものを見つける」かもしれません。この問題の答えは、例えば 4 かもしれません。対応する決定問題は、「 $uから$ $v$ への経路で、使用する辺の数が 10 以下であるものは存在するか」です。この問題には、「はい」または「いいえ」で簡単に答えることができます。

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

参考文献

↑ 「検索スペース」 . courses.cs.washington.edu . 2025年5月10日取得。
↑ 「Search Space - LessWrong」。www.lesswrong.com。2020年9月22日。 2025年5月10日取得。
↑ Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf) . Cambridge University Press. p. 129. ISBN 978-0-521-83378-3。
↑ Ausiello, Giorgio; et al. (2003), Complexity and Approximation (Corrected ed.), Springer, ISBN 978-3-540-65431-5

外部リンク

「トラフィックシェーピングがネットワーク帯域幅を最適化する方法」。IPC 。 2016年7月12日。 2017年2月13日取得。

[1] 「検索スペース」 . courses.cs.washington.edu . 2025年5月10日取得。

[2] 「Search Space - LessWrong」。www.lesswrong.com。2020年9月22日。 2025年5月10日取得。

[3] Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf) . Cambridge University Press. p. 129. ISBN 978-0-521-83378-3。

[Ausiello03-4] Ausiello, Giorgio; et al. (2003), Complexity and Approximation (Corrected ed.), Springer, ISBN 978-3-540-65431-5

[ 1 ]

[ 2 ]

[

[ 4 ]

最適化問題

検索スペース

連続最適化問題

組み合わせ最適化問題

関連項目

参考文献

外部リンク

関連するトピック

数学

工学

コンピュータ科学

経済学