Multi-Objective Optimum Design

Pareto Optimality, Scalarization, and Engineering Trade-Offs

Reference: Jasbir Singh Arora, Introduction to Optimum Design, 4th ed., Academic Press, 2017, Ch. 18.

이 장에서는 mass, efficiency, safety, cost처럼 서로 충돌하는 여러 objectives를 동시에 고려하는 optimum design problem을 정리한다. 하나의 numerical minimum을 찾는 대신 objective vectors 사이의 dominance와 Pareto optimality를 정의하고, attainable trade-off set을 분석한다. 이어서 objective normalization, weighted-sum method, weighted global criterion, $\epsilon$-constraint method가 Pareto solutions를 생성하는 원리와 한계를 비교한다.


Multi-Objective Problem

$k$개의 objectives를 갖는 problem을

\[\begin{aligned} \underset{x}{\operatorname{minimize}}\quad & f(x) = \begin{bmatrix} f_1(x)\\ \vdots\\ f_k(x) \end{bmatrix} \\ \text{subject to}\quad & h_j(x)=0, && j=1,\ldots,p, \\ & g_{\ell}(x)\leq0, && \ell=1,\ldots,m \end{aligned}\]

로 쓴다. Feasible design space는

\[S = \left\{ x: h_j(x)=0,\; g_{\ell}(x)\leq0 \right\}\]

이다. Maximization objective는 sign을 바꾸어 minimization form으로 통일할 수 있다. 예를 들어 efficiency $\eta(x)$를 maximize하려면 $-\eta(x)$를 minimize한다.


Design Space and Criterion Space

Design point $x\in S$는 objective map

\[f:S\to\mathbb{R}^k\]

에 의해 criterion space의 point

\[z=f(x)\]

로 변환된다. Attainable criterion set은

\[Z = f(S) = \left\{ f(x):x\in S \right\}\]

이다.

각 feasible design은 하나의 criterion point를 만들지만, 서로 다른 designs가 같은 objective vector를 가질 수 있다. 또한 criterion space의 임의의 vector가 실제 design으로 실현되는 것은 아니다. Multi-objective optimization은 $Z$에서 componentwise smaller direction의 boundary를 찾는 문제로 해석할 수 있다.


Conflicting Objectives

모든 objectives가 같은 design에서 independent minima를 갖는다면 conflict가 없다. 그러나 일반적으로

\[x_i^{\star} \in \underset{x\in S}{\operatorname{argmin}} \;f_i(x)\]

가 objective마다 다르다. 한 objective를 개선하면 다른 objective가 악화될 수 있으므로 vector $f(x)$에는 natural total ordering이 존재하지 않는다.

따라서 multi-objective solution은 모든 objectives를 동시에 최소화하는 single point가 아니라, 더 이상 한 objective를 개선하면서 나머지를 유지할 수 없는 trade-off designs의 집합으로 정의한다.


Dominance

두 feasible designs $x,y\in S$에 대하여

\[f_i(x)\leq f_i(y), \qquad i=1,\ldots,k\]

이고 적어도 하나의 index $j$에서

\[f_j(x)<f_j(y)\]

이면 $x$가 $y$를 dominate한다고 한다.

Dominated design은 모든 objectives에서 같거나 나쁘고 적어도 하나에서 strictly worse이므로 합리적인 final choice가 될 수 없다. Criterion space에서 다른 attainable vector에 dominate되지 않는 vector를 nondominated point라 한다.


Pareto Optimality

Feasible point $x^{\star}\in S$가 Pareto optimal이라는 것은

\[f(x)\leq f(x^{\star})\]

이면서 적어도 한 objective를 strict하게 개선하는 다른 $x\in S$가 존재하지 않는다는 뜻이다. Equivalent하게

\[\nexists x\in S: \quad f_i(x)\leq f_i(x^{\star}) \ \forall i, \qquad f_j(x)<f_j(x^{\star}) \ \text{for some }j.\]

Design space의 모든 Pareto optimal points를 Pareto set 또는 efficient set이라 하고, criterion space에서 대응하는 objective vectors를 Pareto front 또는 nondominated frontier라 한다.

Pareto point에서는 어떤 objective도 다른 objective의 손실 없이 개선할 수 없다. 그러나 Pareto optimality만으로 여러 efficient designs 중 하나를 자동으로 선택할 수는 없다. Final selection에는 engineering preference가 필요하다.


Weak Pareto Optimality

$x^{\star}\in S$가 weakly Pareto optimal이라는 것은 모든 objectives를 동시에 strict하게 개선하는 point가 없다는 뜻이다.

\[\nexists x\in S: \quad f_i(x)<f_i(x^{\star}), \qquad \forall i.\]

Weak Pareto point에서는 일부 objectives를 개선하면서 나머지를 unchanged로 유지하는 design이 존재할 수 있다. 따라서 Pareto optimality가 weak Pareto optimality보다 강한 condition이다.

일부 scalarization methods는 항상 weakly Pareto solution을 제공하지만 additional assumptions가 있어야 Pareto solution을 보장한다.


Utopia Point

각 objective의 independent minimum을

\[f_i^{\circ} = \underset{x\in S}{\min} \;f_i(x), \qquad i=1,\ldots,k\]

라 하자. Vector

\[f^{\circ} = \begin{bmatrix} f_1^{\circ}&\cdots&f_k^{\circ} \end{bmatrix}^{T}\]

를 utopia point 또는 ideal point라 한다.

각 $f_i^{\circ}$는 attainable하지만 서로 다른 designs에서 얻어지는 경우가 일반적이다. 따라서 $f^{\circ}$ 전체는 criterion space에서 objectives별 best values를 모은 reference point일 뿐, 대개 $Z$에 속하지 않아 unattainable하다.


Compromise Solution

Utopia point와 가까운 attainable point를 compromise solution으로 선택할 수 있다. Euclidean distance는

\[D(x) = \left\{ \sum_{i=1}^{k} \left[ f_i(x)-f_i^{\circ} \right]^2 \right\}^{1/2}\]

이다. $D(x)$를 minimize하면 criterion space에서 ideal point에 가까운 balanced solution을 얻는다.

하지만 objectives의 units와 magnitudes가 다르면 raw Euclidean distance는 특정 objective에 의해 지배된다. 따라서 distance 또는 weighted aggregation을 사용하기 전에 normalization이 필요하다.


Objective Normalization

Objective $f_i$의 upper reference value를 $f_i^{\max}$라 하면 normalized objective를

\[\bar f_i(x) = \frac{ f_i(x)-f_i^{\circ} }{ f_i^{\max}-f_i^{\circ} }\]

로 정의한다. Ideal point에서는 $\bar f_i=0$이고 upper reference에서는 $\bar f_i=1$이다.

$f_i^{\max}$는 각 objective의 individual minimizer $x_j^{\star}$를 이용하여

\[f_i^{\max} \approx \max_{1\leq j\leq k} f_i\!\left(x_j^{\star}\right)\]

로 정할 수 있다. 이 과정에서 payoff matrix를 얻고 objective conflict의 scale도 확인할 수 있다.

Normalization은 dimensionless comparison을 가능하게 하지만 reference range 자체가 preference를 포함한다. Poor estimate of $f_i^{\max}$는 weights와 distances의 실제 의미를 왜곡할 수 있다.


Scalarization

Scalarization method는 vector objective를 scalar utility function으로 바꾸어 standard single-objective optimization engine으로 푼다.

\[\underset{x\in S}{\operatorname{minimize}} \quad U\!\left(f_1(x),\ldots,f_k(x)\right).\]

Scalarization parameter를 바꾸어 여러 subproblems를 풀면 Pareto front를 sampling할 수 있다. 중요한 평가는 다음 두 가지이다.

  • 반환되는 solution이 Pareto optimal인가?
  • Parameters를 변화시킬 때 complete Pareto set을 생성할 수 있는가?

모든 Pareto points를 생성할 수 있는 method가 항상 Pareto point만 반환하는 것은 아니며, 그 반대도 가능하다.


Weighted-Sum Method

Positive weights $w_i>0$와

\[\sum_{i=1}^{k}w_i=1\]

을 사용하여

\[U_w(x) = \sum_{i=1}^{k} w_i\bar f_i(x)\]

를 minimize한다. Objectives의 scale이 이미 comparable하면 raw $f_i$를 사용할 수 있다.

모든 weights가 positive이면 weighted-sum minimizer는 Pareto optimal이다. Weight $w_i=0$을 허용하면 corresponding objective가 selection에 영향을 주지 않아 weakly Pareto point가 나올 수 있다.

Weights는 relative importance를 나타내지만 objective trade-off와 동일한 것은 아니다. Smooth two-objective Pareto front에서 interior weighted-sum solution의 tangent는

\[\frac{d\bar f_2}{d\bar f_1} = -\frac{w_1}{w_2}\]

를 만족한다. 따라서 weights는 criterion-space supporting line의 slope를 결정한다.


Limitations of Weighted Sum

Weighted sum은 간단하고 positive weights에서 Pareto optimality를 보장하지만 다음 한계가 있다.

  • A priori weight가 실제로 원하는 engineering trade-off를 만들지 않을 수 있다.
  • Uniformly spaced weights가 uniformly spaced Pareto points를 만들지 않는다.
  • Criterion space에서 nonconvex한 Pareto-front portions는 어떤 positive weight로도 얻을 수 없다.
  • Objectives를 normalize하지 않으면 numerical magnitude가 weight preference를 압도할 수 있다.

따라서 weighted sum은 convex supported Pareto points를 생성하는 데 적합하지만 complete front generator는 아니다.


Weighted Global Criterion

Utopia point에서의 weighted $p$-norm distance를

\[U_p(x) = \left\{ \sum_{i=1}^{k} \left[ w_i \left( \bar f_i(x)-\bar f_i^{\circ} \right) \right]^p \right\}^{1/p}\]

로 정의한다. Normalized formulation에서는 $\bar f_i^{\circ}=0$이므로

\[U_p(x) = \left\{ \sum_{i=1}^{k} \left[ w_i\bar f_i(x) \right]^p \right\}^{1/p}\]

이다.

  • $p=1$이면 ideal-point adjusted weighted sum과 같다.
  • $p=2$이면 weighted Euclidean compromise distance이다.
  • $p\to\infty$이면 largest weighted deviation을 minimize하는 weighted min-max method가 된다.

Utopia point와 positive weights를 사용하면 solution은 Pareto optimal이다. $p$가 커질수록 가장 나쁜 normalized deviation에 더 큰 emphasis를 두므로 balanced worst-objective performance를 추구한다.


Weighted Min-Max Limit

$p\to\infty$에서 global criterion은

\[U_{\infty}(x) = \max_{1\leq i\leq k} \left\{ w_i \left[ \bar f_i(x)-\bar f_i^{\circ} \right] \right\}\]

가 된다. Auxiliary variable $\lambda$를 사용하면

\[\begin{aligned} \underset{x,\lambda}{\operatorname{minimize}}\quad & \lambda \\ \text{subject to}\quad & w_i \left[ \bar f_i(x)-\bar f_i^{\circ} \right] \leq\lambda, && i=1,\ldots,k, \\ & x\in S \end{aligned}\]

로 쓸 수 있다.

Weighted min-max는 weight variation을 통해 nonconvex Pareto-front portions까지 찾을 수 있지만 weakly Pareto solutions를 반환할 수 있다. Unique solution이면 Pareto optimal이다.


Epsilon-Constraint Method

Primary objective $f_s$를 선택하고 나머지 objectives에 acceptable limits를 부여한다.

\[\begin{aligned} \underset{x\in S}{\operatorname{minimize}}\quad & f_s(x) \\ \text{subject to}\quad & f_i(x)\leq\epsilon_i, && i=1,\ldots,k,\quad i\neq s. \end{aligned}\]

$\epsilon$ vector를 systematic하게 변화시키면 different Pareto solutions를 얻는다. 이 method는 physical units의 limits를 직접 지정하므로 normalization이 필수는 아니다.

Feasible solution은 weakly Pareto optimal이고, solution이 unique하면 Pareto optimal이다. 또한 active $\epsilon$-constraint가 nonzero multiplier를 가지면 해당 solution은 Pareto optimal이다.

$\epsilon_i$를 지나치게 작게 설정하면 subproblem이 infeasible해지고, 너무 크게 설정하면 해당 objective가 trade-off에 영향을 주지 않는다.


Trade-Off Sensitivity

Constraint

\[f_i(x)-\epsilon_i\leq0\]

의 optimum multiplier를 $\lambda_i^{\star}\geq0$라 하면 regularity 아래에서 primary optimum value의 local sensitivity는

\[\frac{\partial f_s^{\star}}{\partial\epsilon_i} = -\lambda_i^{\star}\]

이다. 즉 allowable limit $\epsilon_i$를 tightening하면 primary objective의 optimum value가 증가하며, multiplier는 그 local exchange rate를 측정한다.

예를 들어 mass를 minimize하면서 safety metric에 upper limit를 두면, active multiplier는 safety requirement를 더 엄격하게 할 때 추가되는 minimum mass의 first-order rate를 나타낸다.


Engineering Interpretation

Engineering objectives는 units와 preferred direction이 서로 다를 수 있다.

  • Mass와 manufacturing cost는 일반적으로 minimize한다.
  • Efficiency, reliability, safety margin은 maximize objective이므로 sign transformation이 필요하다.
  • Failure probability, energy loss, environmental impact는 minimize한다.

Pareto front는 하나의 universally best design이 아니라 achievable trade-offs를 보여준다. Decision maker는 knee region, regulatory limits, budget, uncertainty margin을 함께 고려하여 final design을 선택해야 한다.

Scalarization 결과 하나만 제시하면 preference assumptions가 숨겨질 수 있다. 여러 weights, $p$ values, 또는 $\epsilon$ limits를 사용하여 nearby Pareto designs와 sensitivity를 함께 비교하는 것이 중요하다.


Method Comparison

  • Weighted sum은 가장 단순하고 positive weights에서 Pareto point를 반환하지만 nonconvex front를 완전히 생성하지 못한다.
  • Global criterion은 utopia point까지의 distance로 compromise를 해석하며 $p$로 worst-objective emphasis를 조절한다.
  • Weighted min-max는 largest deviation을 제어하고 broader Pareto set을 생성할 수 있지만 weak Pareto points를 포함할 수 있다.
  • $\epsilon$-constraint는 한 objective를 optimize하고 나머지에 explicit engineering limits를 적용하며 nonconvex front에도 사용할 수 있다.

Method selection은 필요한 output이 single compromise인지 complete frontier인지, preferences가 weights인지 physical limits인지, objective scales와 front geometry가 어떤지에 따라 달라진다.


Summary

  • Multi-objective problem은 feasible design $x$를 criterion vector $f(x)\in Z$로 mapping한다.
  • Pareto point는 다른 feasible design에 dominate되지 않으며, Pareto front는 attainable trade-off boundary를 이룬다.
  • Utopia point는 objectives별 independent minima를 모은 reference vector이며 일반적으로 unattainable하다.
  • Objective normalization은 units와 magnitudes가 다른 objectives의 comparison을 가능하게 한다.
  • Positive weighted sum은 Pareto point를 제공하지만 nonconvex Pareto-front portions를 놓칠 수 있다.
  • Weighted global criterion은 utopia point까지의 $p$-norm distance를 minimize하며 $p\to\infty$에서 min-max method가 된다.
  • $\epsilon$-constraint method는 secondary objectives를 explicit limits로 바꾸며 unique solution이면 Pareto optimal이다.
  • Pareto front와 constraint multipliers는 mass, efficiency, safety, cost 사이의 engineering trade-off를 해석하는 도구이다.