【科研两三招】一文了解多目标优化（multi-objective ...

Ylisar · 发表于 2022-7-16 14:31

在无线通信的理论研究工作中，我们通常需要建立一个优化问题以实现资源分配。这个优化问题将包括优化目标以及约束条件。相比于单目标优化问题，多目标优化问题[1]是系统性地同时优化一系列目标函数的过程，也被称为矢量优化（vector optimization）。
本文将首先介绍单目标优化问题，然后介绍多目标优化问题的基本形式和其基于性质的求解方法~仅供大家参考~
1. 单目标优化问题

许多无线资源分配问题可以被建模为约束优化问题，一般问题建模可表示为
$\mathop {\text{Minimize} }\limits_{\bf{x}} F\left( {\bf{x}} \right)\\ s.t. \ {g_j}\left( {\bf{x}} \right) \le 0,\ j = 1, 2,\ldots ,J,\\ \qquad{h_i}\left( {\bf{x}} \right) = 0,\ i = 1,2, \ldots ,L.$
其中是需要优化的变量，例如功率、频谱等。  表示优化目标，例如由香农公式定义的信道容量、数据速率、频谱效率等等。优化目标和优化变量都需要根据面向的场景和业务需求来定。约束条件中包含不等式约束和等式约束。  的可行域由约束条件所确定。
因此，求解该单目标优化问题即在满足约束条件的情况下找到  的最优解以最小化目标函数  。如果点  为最优解，那么将满足 $F({\bf{x}}^*)\leq F({\bf{x}}), \forall {\bf{x}}\in\bf{X}$ ，这里用 ${\bf{X}}$ 表示  的可行域。
特别地，如果该优化问题中不等式约束和等式约束都为关于参数  的线性函数，那么该问题被称为线性规划。线性规划问题的一个重要特征是容易获得全局最优解。
2. 多目标优化问题

多目标优化问题的一般形式表示为：
$\mathop {\text{Minimize} }\limits_{\bf{x}} \ {\bf{F}}({\bf{x}})=[F_1({\bf{x}}), F_2({\bf{x}}), \ldots, F_K({\bf{x}})]^T\\ s.t. \ g_j({\bf{x}})\leq 0, \ j=1,2,\ldots,J,\\ \qquad h_i({\bf{x}})=0, \ i=1,2,\ldots,L.$
上式中， $K$ 表示目标函数的数量， $J$ 表示不等式约束的数量， $L$ 表示等式约束的数量。变量 ${\bf{x}}\in E^N$ 表示决策矢量（通常也被称为设计矢量/优化矢量），其中 $N$ 表示独立变量 $x_i$ 的个数。 ${\bf{F}}({\bf{x}})\in E^K$ 表示目标函数  的矢量。  也被称为目标、标准、效用函数或损失函数等。约束中的不等式符号和等式符号将作用在对应的向量分量上。
可行设计空间  （通常也被称为可行决策空间或约束集合）定义为

$\qquad \qquad \qquad \{{\bf{x}}|g_i({\bf{x}})\leq0, j=1,2,\ldots,J; h_i({\bf{x}})=0, i=1,2,\ldots, L\}$
可行标准空间  （通常也被称为可行成本空间或可获得集合）定义为集合

$\qquad \qquad \qquad \{{\bf{F}}({\bf{x}})|{\bf{x}}\in{\bf{}X}\}$
概念区分：

可行性（feasibility）：意味着标准空间满足所有约束；
可获得性（attainability）：标准空间中的一点能够映射到设计空间中的一点。这是因为设计空间中的每个点都对应标准空间中的一个点，但反之可能不成立，即标准空间中的每个点不一定对应设计空间中的唯一一点。

为不失一般性，接下来将考虑为feasible且attainable。
3. 基本概念和定义

帕累托最优（Pareto optimality）

与单目标优化问题相比，多目标问题的解决方案更多的是一个概念，而不是一个定义。通常情况下，不存在单一的全局（global）解，通常需要确定一组点，这些点都符合预定的最优定义。定义最优点的主要概念是帕累托最优[2]，其定义如下：

定义1：帕累托最优：点是帕累托最优，当且仅当不存在另外的点使得 ${\bf{F}}({\bf{x}})\leq{\bf{F}}({\bf{x}}^*)$ 且对于至少一个目标函数满足 ${F_i}({\bf{x}})<{F_i}({\bf{x}}^*)$ 。

根据定义可以看到，所有的帕累托最优点位于可行标准空间的边界。通常，算法提供的解决方案可能不是帕累托最优，但可能满足其他标准，这使得它们在实际应用中很重要。例如，弱帕累托最优（weakly Pareto optimal）定义如下：

定义2：弱帕累托最优：点是弱帕累托最优，当且仅当不存在另外的点使得 ${\bf{F}}({\bf{x}})<{\bf{F}}({\bf{x}}^*)$ 。

如果没有其他点能同时改进所有目标函数，则该点为弱帕累托最优点。相反，如果没有其他点能改善至少一个目标函数而不损害另一个函数，那么这个点就是帕累托最优。帕累托最优点是弱帕累托最优点，但弱帕累托最优点不是帕累托最优点。
此外，所有的帕累托最优点可以被分为合适（proper）或不合适（improper），此处省略定义。
确定点是否为帕累托最优的方法如下：
$\mathop {\text{Minimize} }\limits_{{\bf{x}}\in{\bf{X}}, {\bf{\delta}}\geq0} \sum_{i=1}^{K}{\delta_i}\\ s.t. F_i({\bf{x}})+\delta_i=F_i({\bf{x}}^*), \ i=1,2,\ldots,K.$
如果所有的 $\delta_i$ 都为0，那么即为帕累托最优点。
对于任何给定的问题，可能有无穷多个帕累托最优点构成帕累托最优集。因此，我们必须区分提供帕累托最优集或其中一部分的方法和真正寻求单一最优点的方法。

必要充分条件（Necessary and sufficient conditions）

就全局标准 $F_g$ 而言，文献[3]给出了帕累托最优点的充分条件，有助于评估一个标量化方法的有效性：
<blockquote data-pid="P4lNi15N">定理1：定义 ${\bf{F}}\in{\bf{Z}},{\bf{x}}^*\in{\bf{X}}$ 且 ${\bf{F}}^*={\bf{F}}({\bf{x}}^*)$ 。定义一个标量全局标准 $F_g({\bf{F}}): {\bf{Z}}\rightarrow R^1$ 为可微分的，且 $\nabla_{F}F_g({\bf{F}})>0 \ \forall {\bf{F}}\in{\bf{Z}}$ 。假设 $F_g({\bf{F}}^*)=\min\{F_g({\bf{F}})<{\bf{F}}\in{\bf{Z}}\}$ ，那么

Mecanim · 发表于 2022-7-16 14:36

多目标优化问题确实十分有意思！
由于篇幅原因，我在下篇中继续总结了其他多目标优化问题的求解方法，并举了个例子来说明多目标优化问题的具体求解过程~~感兴趣的朋友可以移步这里https://zhuanlan.zhihu.com/p/537958187

		自动登录	找回密码
密码			立即注册