📂最適化理論

パレートフロント

定義

多目的最適化問題の目的関数 $\mathbf{f} : \mathbb{R}^{n} \to \mathbb{R}^{m}$ が $f_{k} : \mathbb{R}^{n} \to \mathbb{R}$ に対して次のようにベクトル関数で表せるとしよう.
$$ \mathbf{f} \left( \mathbf{x} \right) = \left( f_{1} \left( \mathbf{x} \right) , f_{2} \left( \mathbf{x} \right) , \cdots , f_{m} \left( \mathbf{x} \right) \right) $$

簡単な定義

上位互換が存在しない解の集合を パレートフロント^{Pareto front} と呼ぶ. 言い換えれば、パレートフロント以外の解を使う理由がまったくない解の集合として定義される.

厳密な定義

最適化の目的が各成分ごとに $f_{k}$ を最大化する方向だとする. $\mathbf{f}$ の値域において関数値ベクトル $\mathbf{y} = \left( y_{1} , \cdots , y_{m} \right) = \mathbf{f} \left( \mathbf{x} \right)$ は次のように大小関係を持ち得る.
$$ \mathbf{y} ' \prec \mathbf{y} '' \iff y_{k} ' < y_{k} '' , \forall k \in \left\{ 1, \cdots , m \right\} $$
このようにすべての成分で $\mathbf{y} ''$ が $\mathbf{y} '$ より大きければ、$\mathbf{y} ''$ は $\mathbf{y} '$ を 支配する^dominate と言う. 実行可能解の集合を $X$ とすると、$Y = \mathbf{f} (X)$ のパレートフロント $P(Y)$ は次のような集合で定義される.
$$ P(Y) = Y \setminus \left\{ \mathbf{y} \in Y : \exists \mathbf{y} ' \in Y , \mathbf{y} \prec \mathbf{y} ' \right\} $$
言い換えれば、パレートフロントは少しでも自身を支配する解が存在しない解の集合である.

説明

厳密な定義によれば、パレートフロントの解は次を満たす.
$$ \mathbf{y} ' , \mathbf{y} '' \in P(Y) \implies \mathbf{y} ' \nprec \mathbf{y} '' $$

他の解に支配されない解の集合というのは、簡単に言えば代替不可能な固有の使い道（用途）があるということだ. それがより良いかどうかは別として、少なくとも同じ使い道であれば誰にも劣らない解だけを集めたものだ.

図を見るとパレートフロントというものがはるかに理解しやすい. 次の図では各点が解を表し、$y_{1}$ と $y_{2}$ はそれぞれ大きいほど良いとする.

ここで赤色はパレートフロントに属し、それ以外はパレートフロントに属さない. フロント^frontは文字通り前線であり、解集合の中で少なくとも「無駄ではない」解が形成する線の形を成す.

• AとEはそれぞれ $y_{2}$ と $y_{1}$ において最も専門化された解だ. バランスの取れた解よりもたとえ一つの目的関数でも最適化したければ、これらを選ぶのが妥当だ.
• パレートフロントではB、C、Dは比較的バランスの取れた方に属する. これらのうちどれを選ぶかについては特に決まった答えはない. $y_{2}$ がより重要ならB、$y_{1}$ がより重要ならDを選べばよい.
• HはA、B、C、Dに支配された. これらより勝る点は一つもなく、この解を使う理由がない. せいぜいEと比べると $y_{2}$ が高いが、すぐ近くにCがありCがEより全ての面で優れているためEを選ぶのが妥当だ.
• HはGを支配してはいるが意味がない. 少なくともCがある以上、解が「どれだけ多くの他の解を支配するか」は重要ではない. どれだけ多くの解を支配していても、自分を支配する解が存在する時点で意味がなくなる.
• Jは実は $y_{1}$ だけで見ればEを除く全ての解より良いが、結局Eに支配されるため意味がない. Jを使うよりEを使う方が良い.

パレート最適

経済学では何の犠牲もなくより良い状態に変わることをパレート改善と呼び、そのような状態に既に到達していて、ある一つを改善すると別の一つが悪化する状態をパレート最適という. これはパレート最適の状態がパレートフロントに属する解であるという意味と一致し、それ自体がトレードオフを意味する.

1선과 2선, 그리고 n선

次の図は参考文献から借用したもので軸方向が逆になっているが、本質的には同じ話だ¹.

パレート分布の定義によれば、どれだけパレートフロントに近いかによって解の序列を付けることができる. 簡単には、パレートフロントを解集合から取り除きながら次のパレートフロントを見つければよい. $P_{1} (Y) = P(Y)$ を1線^{first front}と呼ぶなら、$k$ 線は次のように再帰関数として定義される.
$$ P_{k} (Y) = P \left( Y \setminus P_{k-1} (Y) \right) $$