Multi-objective optimization — 多目的最適化

多目的最適化（多目的計画法とも、英語: multi-objective optimization, multi-criteria optimization）は、数理最適化の一分野であり、一般に互いに競合する2つ以上の目的関数（基準）を同時に最適化する問題を扱います。形式的には、この問題は許容解の集合上でベクトル目的関数を最小化するものとして記述されます。

定義と用語

多目的最適化問題は、一般的に次のように記述されます： $\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$に対しても、すべての$i=1,\dots ,k$について$f_i(x)\le f_i(x^{*})$であり、かつ少なくとも一つのインデックス$j$について$f_j(x)<f_j(x^{*})$となるような解が存在しない許容解$x^{*}\in S$。言い換えれば、ある基準値を他のいずれかの基準値を悪化させることなしに改善することができない場合、その解はパレート最適です。
• パレートフロント（またはパレート集合）: パレート最適解に対応するすべての目的ベクトルの集合。
• 弱パレート最適解: すべての$i$に対して$f_i(x)<f_i(x^{*})$となるような他の解$x\in S$が存在しない解$x^{*}\in S$。

主要な性質と定理

• 加重和定理: 凸問題（すべての関数$f_i(x)$と集合$S$が凸である場合）において、任意のパレート最適解$x^{*}$は、ある非負の重み$w_i\ge 0$の組に対して、基準の加重和$\underset{x\in S}{\min }\sum _{i=1}^k{w}_i{f}_i(x)$を最小化するスカラー問題の解となります。しかし、非凸問題では、この方法ではパレートフロントの一部を見つけられない場合があります。

• カルーシュ・クーン・タッカー（KKT）最適性条件: 滑らかな問題に対する最適性の必要条件は、多目的の場合にも一般化されます。パレート最適点においては、目的関数と有効な制約の勾配が線形従属となるような、非ゼロの非負乗数（重み）の組が存在します。

• 解集合の特性: パレートフロントは、いくつかの重要な質的特徴を持ちます。その境界は、理想点（すべての基準の要素ごとの最小値から構成される）とナディア点（フロント上の要素ごとの最大値から構成される）によって定められます。

例

• 線形問題: 制約$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$-制約法: 1つの基準を最適化し、残りの基準は$f_i(x)\le {\epsilon }_i$という形の制約に変換します。この方法は、フロントの非凸部分の解を見つけることができます。

多目的最適化は、工学設計、経済学（例：ポートフォリオ最適化）、経営、環境学など、幅広い分野で応用されています。