最適化の用語: 線形計画入門 2 - コンピュータフリーク

この章では、線形計画を定義するための準備として、最適化の用語を紹介します。

最適化の用語集

最適化の分野に特有の用語を紹介します。具体的なイメージを掴むべく、前章で紹介した金融資産を具体例として使い説明します。

決定変数

最適化の対象になる変数のことを決定変数といいます。すなわち、求めたい設定を表す変数です。決定変数は記号 $x$ で表されることが多く、ベクトル値を取ることが多いです。

たとえば、金融資産の例では、各株式の購入量を表す $(x, y)$ が決定変数に当たります。これは二次元ベクトルです。

目的関数

最適化問題において最大化または最小化される関数を目的関数といいます。これは決定変数の値を受け取り、その良さもしくは悪さの値を返す関数です。記号 $f$ で表されることが多いです。

たとえば、金融資産の例では、期待利益を表す $f$ が目的関数に当たります。

金融資産の例では最大化問題なので目的関数の値が大きいほど良い設定であることを表しますが、最小化問題の場合は値が小さいほど良いことを表すことに注意してください。

制約条件・実行可能領域

決定変数が取ることのできる値の集合を制約条件といいます。図形的なイメージをもって最適化問題を語るときには実行可能領域と呼ばれることもあります。記号 $\mathcal{C}$ で表されることが多いです。制約条件が等式 $h(x) = 0$ や不等式 $h(x) \ge 0$ で表される場合、$h$ を制約関数といいます。制約条件に含まれる値を実行可能解といいます。

例えば、金融資産の例では、予算内に収まる株式の購入量 $\mathcal{C} = \{(x, y) \mid 100 x + 300 y \le 50000\}$ が制約条件に当たります。この例では $(200, 100)$ や $(400, 0)$ は実行可能解です。

解というと最終的に求めたい答えのようなニュアンスを持ちますが、実行可能解という用語は制約さえ満たせばどのような値に対しても使われることに注意してください。

最適解

最大解問題の場合、実行可能解のうち目的関数の値が最も大きいものを最適解といいます。記号で表すと、$x \in \mathcal{C}$ は任意の $y \in \mathcal{C}$ について $f(x) \ge f(y)$ が成り立てば最適解です。最適解は記号 $x^*$ で表されることが多いです。

最小化問題であれば、実行可能解のうち目的関数の値が最も小さいものが最適解です。

すなわち、最適解とは我々が求めたいものになります。

問題によっては、最適解が複数存在する場合もあります。これは、最適値において $f(x^*) = f(x)$ となる $x^* \neq x$ が存在する場合です。そのような場合、最適解のうち一つを求めれば十分な場合もあれば、全てを列挙したい場合もあります。

また、問題によっては、最適解が存在しない場合もあります。これは、いくらでも目的関数の値を大きくできる場合と、実行可能領域が空集合である場合とがあります。最適解が存在しない場合にそのことを検出することも重要になります。

最適化問題の定式化

最適化問題は数式では $$\begin{align*}&\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad f(x) \\ &\quad \text{s.t.} \qquad h_1(x) = 0 \\ &\qquad \qquad h_2(x) = 0 \\ &\qquad \qquad h_3(x) \le 0\end{align*}$$
のように表されます。

冒頭が minimize であれば最小化問題、maximize であれば最大化問題であることを表します。その下には決定変数とその決定変数の型が記されています。この例では、決定変数は $x$ で $n$ 次元ベクトルであることを示しています。s.t. の後が制約条件を表します。この例では、制約条件は $\mathcal{C} = \{x \mid h_1(x) = 0, h_2(x) = 0, h_3(x) \le 0\}$ です。

例えば、金融資産の例は以下のように表されます。

$$\begin{align*}&\underset{(x, y) \in \mathbb{R}^2}{\text{maximize}} \quad 20x + 30y \\ &\quad \text{s.t.} \qquad 100 x + 300 y \le 50000 \\ &\qquad \qquad x \ge 0 \\ &\qquad \qquad y \ge 0\end{align*}$$