Multi-objective optimization — 다기준 최적화

다목적 최적화 (또는 다기준 프로그래밍, 영어: multi-objective optimization, multi-criteria optimization) — 두 개 이상의 목적 함수(기준)를 동시에 최적화하는 문제를 연구하는 수학적 최적화의 한 분야로, 이 목적 함수들은 일반적으로 서로 상충한다. 형식적으로 이 문제는 허용 가능한 해의 집합 위에서 벡터 목적 함수를 최소화하는 것으로 기술된다.

정의 및 용어

다목적 최적화 문제는 일반적으로 다음과 같이 기술된다: $\underset{x\in S}{\min }\{f_1(x),f_2(x),\dots ,f_k(x)\}$ 여기서 $S\subseteq {\mathbb{ℝ}}^n$ 는 공집합이 아닌 허용 가능한 해의 집합이며, $f_i:S\to \mathbb{ℝ}$ 은 목적 함수($k\ge 2$)이다. 벡터 $f(x)=(f_1(x),\dots ,f_k(x))$ 를 목적 벡터라고 한다.

스칼라 최적화와 달리, 다기준 설정에서는 일반적으로 모든 기준의 값을 동시에 개선하는 단일 해가 존재하지 않는다. 따라서 최적성의 고전적 개념은 파레토 최적성 개념을 사용하여 일반화된다.

• 파레토 해 (파레토 최적 또는 효율적 해): 다른 해 $x\in S$ 가 존재하지 않는 허용 가능한 해 $x^{*}\in S$ 로, 모든 $i=1,\dots ,k$ 에 대해 $f_i(x)\le f_i(x^{*})$ 이고, 적어도 하나의 인덱스 $j$ 에 대해 $f_j(x)<f_j(x^{*})$ 인 해를 말한다. 즉, 어떤 기준의 값도 다른 하나 이상의 기준을 악화시키지 않고는 개선할 수 없는 경우 그 해를 파레토 최적이라 한다.
• 파레토 프론트 (또는 파레토 집합): 파레토 최적 해에 대응하는 모든 목적 벡터의 집합.
• 약 파레토 최적 해: 다른 해 $x\in S$ 가 존재하지 않는 해 $x^{*}\in S$ 로, 모든 $i$ 에 대해 $f_i(x)<f_i(x^{*})$ 인 해를 말한다.

주요 성질 및 정리

• 가중 합 정리: 볼록 문제(모든 함수 $f_i(x)$ 와 집합 $S$ 이 볼록인 경우)에서 임의의 파레토 최적 해 $x^{*}$ 는 어떤 음이 아닌 가중치 집합 $w_i\ge 0$ 에 대해 기준의 가중 합 $\underset{x\in S}{\min }\sum _{i=1}^k{w}_i{f}_i(x)$ 을 최소화하는 스칼라 문제의 해가 된다. 그러나 비볼록 문제에서는 이 방법이 파레토 프론트의 일부 영역을 찾지 못할 수 있다.

• 카루시-쿤-터커(KKT) 최적성 조건: 매끄러운 문제에 대한 최적성의 필요조건은 다기준의 경우로 일반화된다. 파레토 최적점에서는 목적 함수의 기울기와 활성 제약 조건의 기울기가 선형 종속이 되는 음이 아닌 승수(가중치)의 영이 아닌 집합이 존재한다.

• 해 집합의 성질: 파레토 프론트는 여러 중요한 정성적 특성을 가진다. 그 경계는 모든 기준의 원소별 최솟값으로 구성된 이상점(ideal point) 과 프론트 위의 원소별 최댓값으로 구성된 나디르 점(nadir point) 에 의해 한정된다.

예시

• 선형 문제: $x_1+x_2\le 1$, $x_1,x_2\ge 0$ 의 제약 조건 하에서 $f_1(x)=-x_1$ 과 $f_2(x)=-x_2$ 를 최소화한다. 여기서 하나의 기준을 개선하면(예: $x_1$ 를 증가시키면) 필연적으로 다른 기준이 악화된다($x_2$ 가 감소). 파레토 최적 해의 집합은 선분 $x_1+x_2=1$ 이다.
• 비볼록 문제: 구간 $[0,2]$ 위에서 $f_1(x)=x^2$ 과 $f_2(x)=(x-2{)}^2$ 를 최소화한다. 파레토 프론트는 비볼록이다. 양의 가중치를 이용한 가중 합 방법은 이 구간의 내부 해(예: 점 $x=1$)를 찾지 못하는데, 기준의 선형 결합이 양 끝점 $x=0$ 또는 $x=2$ 에서만 최솟값에 도달하기 때문이다.

관련 개념 및 응용

다목적 최적화는 의사 결정자의 선호도를 고려하여 최선의 대안을 선택하는 것을 연구하는 다기준 의사 결정(MCDM)과 밀접하게 관련되어 있다. 다기준 문제를 스칼라 문제로 변환하는(스칼라화) 주요 방법은 다음과 같다:

• 가중 합 방법.
• $\epsilon$-제약 방법: 하나의 기준을 최적화하고 나머지는 $f_i(x)\le {\epsilon }_i$ 형태의 제약 조건으로 전환한다. 이 방법은 프론트의 비볼록 구간에서도 해를 찾을 수 있다.

다목적 최적화는 공학 설계, 경제학(예: 포트폴리오 최적화), 경영 및 환경 분야에서 폭넓게 응용된다.

같이 보기

• 파레토 최적성
• 벡터 최적화
• 의사 결정 이론
• 의사 결정 지원 시스템
• 운용 과학