数学やプログラミングの備忘録

数理最適化, Python, C++をメインに紹介するブログ。

MENU

多目的最適化の3つの解法

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

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

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

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

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

  1. パラメータ法
  2. 制約化法
  3. min-max法

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) をより小さくした解が、最適解になります。

2. 制約化法

例えば、あるコスト関数  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}) が成立。

3. min-max法

コスト関数  f_1(x), \dots, f_k(x) に優先順位は無く、最大値を最小化したいときに使う方法。例えば、バスの遅延最小化を考えたときに、各バスそれぞれの遅延関数が、 f_1(x), \dots, f_k(x) に対応します。

(もし、 f_1(x) が電気代、 f_2(x) が交通費みたいに、全く違うものを比較する場合、スケーリングする必要があります)


\begin{array}{ll}
\displaystyle\min_{x} & \max\left\{f_i(x): i=1,\dots,k\right\}\\
\text{s.t.} & x \in F
\end{array}

最大値を最小化する問題は、このように表現できるが、このままでは最適化ソフトウェアで解けないので、次のように変形します。


\begin{array}{ll}
\displaystyle\min_{x,c} & c\\
\text{s.t.} & f_i(x)\le c\ (i=1,\dots,k)\\
& x \in F
\end{array}

全コスト関数を上から抑えた  c を最小化する問題で、maxが目的関数に入っている問題と同じ最適解を得ることができます。