📂최적화이론

파레토 프론트

정의

다목적 최적 문제의 목적 함수 $\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) $$