多目的最適化の３つの解法 - 数学やプログラミングの備忘録

実務ではいろんなことを最小化したい場合がありますよね。例えば、時間だったり、電気代だったり、人手だったり、、。そんなときに、考えるのは多目的最適化です。その多目的最適化について解法を紹介します。

今、最小化したい $k$ 個のコスト関数を

$$ f_1(x), \dots, f_k(x) $$

とし、与えらた制約条件を満たす解の集合(実行可能領域)を $F$ とします。

このとき、多目的最適化問題としての求解アプローチは、いろいろありますが、この記事では基本的な３つ紹介します。

1. パラメータ法

$\begin{array}{ll} \displaystyle\min_{x} & \displaystyle\sum_{i=1}^k \lambda_i f_i(x)\\ \text{s.t.} & x \in F \end{array}$

$\lambda_i>0\ (i=1,\dots,k)$ はパラメータです。 $\lambda_i$ を大きくすると、対応するコスト関数の $f_i(x)$ をより小さくした解が、最適解になります。

例えば、あるコスト関数 $f_j(x)$ が最も重要である場合、他のコスト関数を制約式に入れてしまいます。

$\begin{array}{ll} \min_{x} & f_j(x)\\ \text{s.t.} & x \in F\\ & f_i (x) \le \alpha_i\ (i=1,\dots,k,\ i\neq j) \end{array}$

この問題は、「 $f_j(x)$ 以外のコスト関数は、 $\alpha_i$ というパラメータを使用し、 $f_i(x)$ は大きくもここまで」というように、制約化された問題です。

この問題が実行不能(解が存在しない)ならば、 $\alpha_i$ が小さ過ぎたこになる
この問題の最適解 $\bar{x}$ が、 $f_i(\bar{x})=\alpha_i$ を満たすとき、対応する $\alpha_i$ を大きくしたとする。このとき更新された最適化問題の最適解を $\hat{x}$ とすると、 $f_j(\bar{x}) \ge f_j(\hat{x})$ が成立。