多目的最適化(multi-objective optimization)とは、複数の目的関数を同時に小さくしたい最適化問題のことで、どの目的関数も悪くせずにどれかを良くすることのできない点を Pareto 最適解とよぶ。コンパクトな集合の上の下半連続な目的関数では、どの点についても、どの目的関数の値もそれ以下である Pareto 最適解がある。正の重みの和の最小点は Geoffrion の意味の真の Pareto 最適解であり、凸集合の上の凸関数ではその逆も成り立つ。重み付き Chebyshev スカラー化と ε 制約法は、凸性を仮定せずに弱 Pareto 最適解・Pareto 最適解を特徴づける。
多目的最適化(multi-objective optimization)とは、複数の目的関数 $f_1,\dots,f_k$ を同時に小さくしたい最適化問題のことである。費用を下げたいが品質も上げたい、誤差を小さくしたいがモデルは単純にしたい、というように、評価の基準が 1 つに決まらない場面で現れる。一般にはすべての $f_i$ を同時に最小にする点はないので、「最適」の意味を Pareto 最適 に取り替える。どの目的関数も悪くせずにどれかを良くすることのできない点が Pareto 最適解である。
1 つの目的関数の最適化の枠組みは 数理最適化 で、正の重みの和をとるスカラー化と凸の場合の逆は 目的関数 の定理「スカラー化と Pareto 最適解」で扱う。この記事では次のことを示す。コンパクトな実行可能集合の上では、どの点もある Pareto 最適解に優越されるかそれと値が等しい(thm-moo-existence)。正の重みの和の最小点は、Geoffrion の意味の真の Pareto 最適解とちょうど一致する(凸の場合。thm-moo-geoffrion)。重み付きの和では得られない Pareto 最適解も、凸性を仮定せずに、重み付き Chebyshev スカラー化(thm-moo-chebyshev)と ε 制約法(thm-moo-epsilon)で特徴づけられる。
集合 $X$ と関数 $f_1,\dots,f_k\colon X\to\mathbb{R}$($k\ge2$)について、$F(x):=(f_1(x),\dots,f_k(x))\in\mathbb{R}^k$ とおき、
$$
\text{(MOP)}\qquad\text{最小化 } F(x)=(f_1(x),\dots,f_k(x))\quad\text{条件 } x\in X
$$
を 多目的最適化問題 という。$u,v\in\mathbb{R}^k$ について、すべての $i$ で $u_i\le v_i$ であることを $u\le v$、すべての $i$ で $u_i< v_i$ であることを $u< v$ と書く。
最大化したい基準 $g$ は $f=-g$ に替えて最小化に直す。経済学で、ほかの誰かの効用を下げずには誰の効用も上げられない配分を Pareto 最適(Pareto 効率的)というのは、各人の効用を最大化する多目的最適化問題の Pareto 最適解のことである。
$\le$ は $\mathbb{R}^k$ の半順序だが、$k\ge2$ では $(1,0)$ と $(0,1)$ のように比べられない組がある。完全最適解はすべての $f_i$ を同時に最小にする点で、これがあれば目的関数どうしは競合しない(BV04 §4.7.5, pp. 181–182)。多くの問題ではこれがなく、Pareto 最適解が「これ以上は一方を良くすると他方が悪くなる」妥協の点の全体として現れる。Pareto フロントは、$k=2$ のとき BV04 の言う最適トレードオフ曲線(optimal trade-off curve)である(BV04 §4.7.5, p. 183)。
(MOP) について次が成り立つ。
1:$F(y)< F(x)$ なら $F(y)\le F(x)$ かつ $F(y)\ne F(x)$ なので、$y$ は $x$ を優越する。対偶をとればよい。
2:右辺の集合に $F(x)$ と異なる値 $F(y)$ があることは、$y$ が $x$ を優越することそのものである。
3:完全最適解 $x^*$ をとる。$x$ が Pareto 最適解なら、$F(x^*)\le F(x)$ で $x^*$ は $x$ を優越しないので $F(x^*)=F(x)$ であり、すべての $y$ で $F(x)=F(x^*)\le F(y)$ だから $x$ も完全最適解である。逆に完全最適解 $x$ を $y$ が優越すると $F(y)\le F(x)\le F(y)$ から $F(y)=F(x)$ となり、優越の定義に反する。
4:$\phi_i$ は狭義単調増加なので、$a\le b\iff\phi_i(a)\le\phi_i(b)$、$a< b\iff\phi_i(a)< \phi_i(b)$ である。したがって優越の関係も、$F(y)< F(x)$ という関係も、取り替えの前後で変わらない。$\square$
2 は BV04 §4.7.3 の式 (4.59)(p. 177)を多目的の場合に書いたもので、4 は BV04 Exercise 4.51(p. 206)の多目的の場合である。1 の逆は成り立たない(ex-moo-table-check の 5 行目の点 $(0,\frac12)$)。
1 つの目的関数では、コンパクト集合の上の下半連続関数は最小値をとる(下半連続)。多目的の場合にも同じ仮定で Pareto 最適解があり、しかも Pareto 最適解は「十分に多い」。
$X$ を位相空間の空でないコンパクト部分集合、$f_1,\dots,f_k\colon X\to\mathbb{R}$ を下半連続とする。このとき、任意の $x\in X$ について、Pareto 最適解 $y$ で $F(y)\le F(x)$ となるものがある。とくに (MOP) は Pareto 最適解をもつ。
$x\in X$ を固定し、$X_x:=\{z\in X\mid F(z)\le F(x)\}=\bigcap_{i}\{z\in X\mid f_i(z)\le f_i(x)\}$ とおく。下半連続関数の劣位集合 $\{f_i\le c\}$ は $X$ の閉集合なので、$X_x$ はコンパクト集合 $X$ の閉部分集合でコンパクトであり、$x\in X_x$ なので空でない。下半連続関数の和 $s:=f_1+\dots+f_k$ も下半連続なので、$s$ は $X_x$ の上で最小値をとる。その最小点を $y$ とすると $y\in X_x$ より $F(y)\le F(x)$ である。
$y$ が Pareto 最適解であることを示す。$z\in X$ が $y$ を優越するとすると、$F(z)\le F(y)\le F(x)$ なので $z\in X_x$ であり、$F(z)\le F(y)$ かつ $F(z)\ne F(y)$ からすべての $i$ で $f_i(z)\le f_i(y)$、ある $i$ で $f_i(z)< f_i(y)$ となる。よって $s(z)< s(y)$ で、$y$ の最小性に反する。$\square$
コンパクト性は外せない。$X=(0,1]$、$f_1(x)=f_2(x)=x$ では、どの $x$ も $x/2$ に優越され、Pareto 最適解はない。
$w\in\mathbb{R}^k$ について $\sum_iw_if_i$ を最小化することを重み付きの和による スカラー化 という。目的関数 の定理「スカラー化と Pareto 最適解」により、すべての $w_i>0$ なら最小点は Pareto 最適解であり、$X$ が凸集合で各 $f_i$ が凸関数なら、どの弱 Pareto 最適解もある $w\ge0$、$w\ne0$ の重みの和の最小点になる。重みの成分に $0$ を許すと、最小点が Pareto 最適解でないことがある。そこで、どの Pareto 最適解が正の重みで得られるかが問題になる。
正の重みで得られる点は、ある目的関数を改善したときに別の目的関数が悪くなる割合に上限がある点である。この考えを定式化したのが次の概念で、Geoffrion による(Geo68)。
(MOP) の Pareto 最適解 $x^*$ が 真の Pareto 最適解(Geoffrion の意味の proper Pareto optimal)であるとは、ある $M>0$ があって次が成り立つことをいう:$i$ と $x\in X$ が $f_i(x)< f_i(x^*)$ を満たせば、ある $j$ で $f_j(x)>f_j(x^*)$ かつ
$$
f_i(x^*)-f_i(x)\le M\bigl(f_j(x)-f_j(x^*)\bigr)
$$
となる。
$X$ が有限集合なら、Pareto 最適解はどれも真の Pareto 最適解である(左辺と右辺の比は有限個しかないので、その最大値を $M$ にとればよい)。
(MOP) と $x^*\in X$ について次が成り立つ。
1:$x^*$ が Pareto 最適解であることは 目的関数 の定理「スカラー化と Pareto 最適解」の 1 である。$k\ge2$ なので
$$
M:=(k-1)\max_{i\ne j}\frac{w_j}{w_i}>0
$$
とおく。$f_i(x)< f_i(x^*)$ とする。$x^*$ の最小性から $\sum_lw_l(f_l(x)-f_l(x^*))\ge0$ なので
$$
\sum_{l\ne i}w_l\bigl(f_l(x)-f_l(x^*)\bigr)\ge w_i\bigl(f_i(x^*)-f_i(x)\bigr)>0
$$
である。左辺の $k-1$ 個の項のうち最大のものを $l=j$ の項とすると、$(k-1)w_j(f_j(x)-f_j(x^*))\ge w_i(f_i(x^*)-f_i(x))>0$ で、$f_j(x)>f_j(x^*)$ かつ
$$
f_i(x^*)-f_i(x)\le(k-1)\frac{w_j}{w_i}\bigl(f_j(x)-f_j(x^*)\bigr)\le M\bigl(f_j(x)-f_j(x^*)\bigr)
$$
である。
2:$M$ を定義のものとし、$i$ を 1 つ固定する。$X$ の上の $k$ 個の関数
$$
g_i^{(i)}(x):=f_i(x)-f_i(x^*),\qquad g_j^{(i)}(x):=f_i(x)-f_i(x^*)+M\bigl(f_j(x)-f_j(x^*)\bigr)\quad(j\ne i)
$$
を考える。どれも凸関数の正の係数の和に定数を足したもので凸であり、$x^*$ で値 $0$ をとる。すべての $g_l^{(i)}(x)< 0$ となる $x\in X$ はない。実際そのような $x$ があれば、$f_i(x)< f_i(x^*)$ なので定義から $f_j(x)>f_j(x^*)$ かつ $f_i(x^*)-f_i(x)\le M(f_j(x)-f_j(x^*))$ となる $j$ があるが、後者は $g_j^{(i)}(x)\ge0$ を意味する。したがって $x^*$ は関数の組 $(g_1^{(i)},\dots,g_k^{(i)})$ の多目的最適化問題の弱 Pareto 最適解である。目的関数 の定理「スカラー化と Pareto 最適解」の 3(凸の場合の逆)により、$\lambda_l^{(i)}\ge0$、$\sum_l\lambda_l^{(i)}=1$ となる重みで、$x^*$ が $\sum_l\lambda^{(i)}_lg^{(i)}_l$ の最小点となるものがある(重みは正の数で割って和を $1$ にした)。定数を除くと
$$
\sum_l\lambda_l^{(i)}g_l^{(i)}=f_i+M\sum_{j\ne i}\lambda_j^{(i)}f_j+(\text{定数})
$$
なので、$x^*$ は $\psi_i:=f_i+M\sum_{j\ne i}\lambda^{(i)}_jf_j$ の $X$ の上の最小点である。$\psi_1,\dots,\psi_k$ のどれも $x^*$ で最小なので、その和 $\sum_i\psi_i=\sum_lw_lf_l$、$w_l:=1+M\sum_{i\ne l}\lambda^{(i)}_l\ge1$ も $x^*$ で最小である。$\square$
凸性は 2 で外せない(ex-moo-table-check の 2 行目)。真の Pareto 最適解でない Pareto 最適解は、凸な問題でも正の重みでは得られず、重みに $0$ を含むスカラー化か、次の節の方法で求めることになる。
$X:=\{x\in\mathbb{R}^2\mid(x_1-1)^2+(x_2-1)^2\le1\}$、$f_1(x)=x_1$、$f_2(x)=x_2$ とする。Pareto 最適解の全体は円周の左下の 4 分の 1 の弧 $\Gamma:=\{(1-\cos\theta,1-\sin\theta)\mid0\le\theta\le\pi/2\}$ である。
$w_1,w_2>0$ について $w_1x_1+w_2x_2$ の円板の上の最小点は、中心 $(1,1)$ から $-(w_1,w_2)$ の方向に半径 $1$ だけ進んだ点 $(1-\cos\theta,1-\sin\theta)$($\cos\theta=w_1/\lvert w\rvert$)で、$0< \theta< \pi/2$ の点がすべてこれで得られ、目的関数 の定理「スカラー化と Pareto 最適解」の 1 により Pareto 最適解である。端点 $(0,1)$ と $(1,0)$ はそれぞれ $f_1$、$f_2$ の円板の上のただ 1 つの最小点なので、これを優越する点はない。逆に $x\notin\Gamma$ なら $x$ を優越する $\Gamma$ の点がある:$x_1\ge1$ なら $(1,0)$ が、$x_2\ge1$ なら $(0,1)$ が、$x_1,x_2< 1$ なら中心から $x$ の方向に円周まで進めた点 $(1,1)+(x-(1,1))/r$($r:=\lvert x-(1,1)\rvert\le1$)が $x$ を優越する(各座標は $1-(1-x_i)/r\le x_i$ で、$x\notin\Gamma$ なら $r< 1$ なので等号は成り立たない)。
端点 $a:=(1,0)$($\theta=\pi/2$)は Pareto 最適解だが、正の重みでは得られない。これは thm-moo-geoffrion の 1 と合っている:弧の上の点 $x=(1-\sin t,1-\cos t)$($0< t< \pi/2$)では $f_1(a)-f_1(x)=\sin t$、$f_2(x)-f_2(a)=1-\cos t$ で、比 $\sin t/(1-\cos t)$ は $t\to0$ で $\infty$ に発散するので、$a$ は真の Pareto 最適解でない。
重み付きの和の最小点は、像 $F(X)$ を直線(超平面)で下から支える点である。$F(X)$ が凹んでいると、その凹みの中の Pareto 最適値はどの重みでも得られない(目的関数 の反例の表の 5・6 行目)。和の代わりに重み付きの最大値をとると、この制約がなくなる。
(MOP) について、$z\in\mathbb{R}^k$(参照点)と、すべての $i$ で $w_i>0$ である $w\in\mathbb{R}^k$ をとり、
$$
\varphi_{w,z}(x):=\max_{1\le i\le k}w_i\bigl(f_i(x)-z_i\bigr)\qquad(x\in X)
$$
とおく。
1:$x^*$ を最小点とし、$F(y)< F(x^*)$ となる $y\in X$ があるとする。$w_i>0$ なので各 $i$ で $w_i(f_i(y)-z_i)< w_i(f_i(x^*)-z_i)\le\varphi_{w,z}(x^*)$ であり、最大値をとって $\varphi_{w,z}(y)< \varphi_{w,z}(x^*)$ となる。これは最小性に反する。
2:ただ 1 つの最小点 $x^*$ を $y$ が優越するとすると、各 $i$ で $w_i(f_i(y)-z_i)\le w_i(f_i(x^*)-z_i)$ なので $\varphi_{w,z}(y)\le\varphi_{w,z}(x^*)$ で、$y$ も最小点である。$F(y)\ne F(x^*)$ より $y\ne x^*$ で、一意性に反する。
3:$w_i>0$ で、$\varphi_{w,z}(x^*)=\max_i1=1$ である。$\varphi_{w,z}(x)< 1$ となる $x\in X$ があれば、すべての $i$ で $f_i(x)-z_i< f_i(x^*)-z_i$、すなわち $F(x)< F(x^*)$ となり、$x^*$ が弱 Pareto 最適解であることに反する。よって $x^*$ は最小点で、最小値は $1$ である。$x^*$ が Pareto 最適解で $y$ が最小点なら、$\varphi_{w,z}(y)=1$ から各 $i$ で $f_i(y)\le f_i(x^*)$ であり、$y$ が $x^*$ を優越しないので $F(y)=F(x^*)$ である。$\square$
$z$ には各 $f_i$ の下限より小さい点(理想点を少し下げた点)をとることが多い。そうすれば $z< F(x^*)$ はすべての $x^*$ で成り立ち、重み $w$ を動かすことで弱 Pareto 最適解がすべて得られる。$w=(1,\dots,1)$、$z=0$ の場合に「$\max_iF_i$ のただ 1 つの最小点は Pareto 最適解である」ことは BV04 Exercise 4.55(pp. 206–207)にある。最大値をとる関数は微分できない点をもつが、補助変数 $t$ を入れて「最小化 $t$ 条件 $w_i(f_i(x)-z_i)\le t$(すべての $i$)」と書けば、$X$ が凸集合で各 $f_i$ が凸なら凸最適化問題になる(数理最適化 の命題「問題の書き換え」と同じエピグラフ形)。
もう 1 つの方法は、1 つの目的関数だけを最小化し、残りを上限つきの制約に回すものである。$j$ と $\varepsilon\in\mathbb{R}^k$ について
$$
\text{(P}_j(\varepsilon))\qquad\text{最小化 } f_j(x)\quad\text{条件 } x\in X,\ f_i(x)\le\varepsilon_i\ (i\ne j)
$$
とおき、これを ε 制約法 という($\varepsilon_j$ は使わない)。
(MOP) について次が成り立つ。
1:最適解 $x^*$ について $F(y)< F(x^*)$ となる $y\in X$ があれば、$i\ne j$ で $f_i(y)< f_i(x^*)\le\varepsilon_i$ なので $y$ は $\mathrm{(P}_j(\varepsilon))$ の条件を満たし、$f_j(y)< f_j(x^*)$ が最適性に反する。
2:ただ 1 つの最適解 $x^*$ を $y$ が優越するとすると、$i\ne j$ で $f_i(y)\le f_i(x^*)\le\varepsilon_i$ なので $y$ は条件を満たし、$f_j(y)\le f_j(x^*)$ から $y$ も最適解である。$F(y)\ne F(x^*)$ より $y\ne x^*$ で、一意性に反する。
3:$x^*$ を Pareto 最適解とし、$j$ を固定する。$x^*$ は $\mathrm{(P}_j(F(x^*)))$ の条件を満たす。条件を満たす $y$ で $f_j(y)< f_j(x^*)$ となるものがあれば、$F(y)\le F(x^*)$ かつ $F(y)\ne F(x^*)$ で $y$ は $x^*$ を優越するので、そのような $y$ はなく、$x^*$ は最適解である。逆に、すべての $j$ で $x^*$ が $\mathrm{(P}_j(F(x^*)))$ の最適解であるとし、$y$ が $x^*$ を優越するとする。$f_j(y)< f_j(x^*)$ となる $j$ をとると、$y$ は $\mathrm{(P}_j(F(x^*)))$ の条件を満たし、$x^*$ の最適性に反する。$\square$
$X:=\{(0,1),(1,0),(\frac35,\frac35)\}\subset\mathbb{R}^2$、$f_i(x)=x_i$ とする。3 点はどれも互いに優越しないので、すべて Pareto 最適解である。$x^*:=(\frac35,\frac35)$ は、どの $w\ge0$、$w\ne0$ の重みの和の最小点にもならない(目的関数 の反例の表の 5 行目の確かめ)。
thm-moo-existence・thm-moo-geoffrion・thm-moo-chebyshev・thm-moo-epsilon の仮定を 1 つずつ外す。
| 外す仮定 | 例 | 成り立たなくなること |
|---|---|---|
| thm-moo-existence の「$X$ がコンパクト」 | $X=(0,1]$、$f_1=f_2=x$ | Pareto 最適解の存在 |
| thm-moo-geoffrion の 2 の「$X$ が凸」 | ex-moo-three-points の $X$ と $x^*$ | 真の Pareto 最適解が正の重みの和の最小点になる |
| thm-moo-geoffrion の 2 の「真の」(Pareto 最適解に弱める) | ex-moo-disk の端点 $a=(1,0)$ | 正の重みの和の最小点になる |
| thm-moo-chebyshev の 1 の「すべての $w_i>0$」 | $X=[0,1]^2$、$f_i=x_i$、$w=(1,0)$、$z=(1,0)$、点 $(1,1)$ | 最小点が弱 Pareto 最適解 |
| thm-moo-chebyshev の 2 の「最小点がただ 1 つ」 | $X=[0,1]^2$、$f_i=x_i$、$w=(1,2)$、$z=(-1,0)$、点 $(0,\frac12)$ | 最小点が Pareto 最適解 |
| thm-moo-epsilon の 3 の「すべての $j$ で」($j=1$ だけにする) | $X=[0,1]^2$、$f_i=x_i$、$x^*=(0,1)$ | $x^*$ が Pareto 最適解 |
1 行目:$(0,1]$ はコンパクトでない。どの $x\in(0,1]$ も $x/2\in(0,1]$ に優越されるので、Pareto 最適解はない。
2 行目:$X$ は有限集合で凸でない($(0,1)$ と $(1,0)$ の中点 $(\frac12,\frac12)$ を含まない)。有限集合なので $x^*$ は真の Pareto 最適解である。$w_1,w_2>0$ について 3 点での $w_1x_1+w_2x_2$ の値は $w_2$、$w_1$、$\frac35(w_1+w_2)$ で、$\min(w_1,w_2)\le\frac12(w_1+w_2)< \frac35(w_1+w_2)$ だから $x^*$ は最小点にならない。
3 行目:$X$ は凸、$f_i$ は 1 次式で凸で、$a$ は Pareto 最適解である。$w_1,w_2>0$ なら ex-moo-disk のとおり最小点は $0< \theta< \pi/2$ の点で $a$ ではない。
4 行目:$w_2=0$ なので $\varphi_{w,z}(x)=\max(x_1-1,0)=0$($x\in X$)で、$X$ のすべての点が最小点である。$(1,1)$ は $(0,0)< (1,1)$ なので弱 Pareto 最適解でない。
5 行目:$w>0$ である。$\varphi_{w,z}(x)=\max(x_1+1,2x_2)\ge1$ で、値 $1$ をとる点は $x_1=0$、$x_2\le\frac12$ の点の全体だから、最小点はただ 1 つでない。$(0,\frac12)$ は最小点だが $(0,0)$ に優越され、Pareto 最適解でない(1 のとおり弱 Pareto 最適解ではある)。
6 行目:$\mathrm{(P}_1(F(x^*)))$ は「最小化 $x_1$ 条件 $x_2\le1$」で、$x^*=(0,1)$ は最適解である。しかし $(0,0)$ が $x^*$ を優越し、$x^*$ は Pareto 最適解でない。実際 $\mathrm{(P}_2(F(x^*)))$(最小化 $x_2$ 条件 $x_1\le0$)の最適値は $0< 1$ で、$x^*$ は最適解でない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する