多目标优化问题

多目标优化问题可以描述为如下形式

\begin{array}{rllllll} \text{minimize} & \bold{f}(\bold{x})=\begin{Bmatrix} f_1(\bold{x})\\ f_2(\bold{x})\\ \vdots\\ f_m(\bold{x})\\ \end{Bmatrix}\\ \text{subject to} & \bold{x}\in \Omega \end{array}

如果 objectives 与 constraints 之间没有冲突，那么一定可以找到一个点 $\bold{x}^\ast$ 同时 minimize 所有的 objectives.

Lexicographic Optimization

思想比较简单

\begin{array}{rllllll} \text{minimize} & f_k(\bold{x})\\ \text{subject to} & \bold{x}\in \Omega\\ &f_j(\bold{x})=f_j^{\min} & j \in [1,k-1] \end{array}

$\varepsilon$ -Constraint Approach 是从多个 Objective Function 选出一个 Primary Objective 作为优化目标，对于剩下的 Objective Function 只需要让其不超过一定误差 $\varepsilon_j$ 即可

\begin{array}{rllllll} \text{minimize} & f_1(\bold{x})\\ \text{subject to} & \bold{x}\in \Omega\\ &f_j(\bold{x})\le \varepsilon_j & j \in [2,m] \end{array}

痛点： $\varepsilon$ 通常很难敲定

就是把多个目标函数加权和成一个函数了

\begin{array}{rllllll} \text{minimize} & f(\bold{x})=\sum_{j=1}^m w_j f_j(\bold{x})\\ \text{subject to} & \bold{x}\in \Omega\\ & w_j\ge 0 \end{array}

finding a solution that minimizes the maximum deviation from some vector of ‘ideal’ objective values

我们令 $f_i^{\min}$ 为目标函数 $f_i$ 的最小值. 对于每一个解 $\bold{x}$ ，我们可以对 $f_i$ 计算出 deviation，考虑到 magnitude 的话，我们可以令

z_i=\frac{f_i(\bold{x})-f_i^{\min}}{|f_i^{\min}|}\\ z_i=\frac{f_i(\bold{x})-f_i^{\min}}{f_i^{\max}-f_i^{\min}}

所以原问题可以转化为

\begin{array}{rllllll} \text{minimize} & f(\bold{x})=\max(z_1,z_2,\dots, z_m)\\ \text{subject to} & \bold{x}\in\Omega \end{array}

这个问题解出来的解也是 Pareto point.