📂最適化理論

パレートフロント

定義

多目的最適化問題の目的関数 $\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がすべての面で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) $$