多目标优化过程中的Pareto解的收敛性

求解多目标问题的pareto解的算法大多采用迭代的方法，在这里只要做一个简短的论文[1]Convergence rates analysis of a multiobjective proximal gradient method的笔记,[1]中的方法首先设计了merit function，然后采用merit function趋于0等效于寻找到pareto的解的策略，
针对原问题进行pareto的解的迭代求解，迭代的过程是用了proximal gradient method去求解problem.

Merit Function

而[2]中解释了,Merit function与pareto解之间的关系,如下,Merit function为

$$u(x) = \sup_{y\in\mathcal{S}} \min_{i\in\{1,...,m\}}\big(F_i(x) - F_i(y)\big), \forall y\in\mathcal{S}$$

这里的$i\in\{1,...,m\}$表示每一个$F_i(x) - F_i(y)$都要满足min的要求，而不是从m个$F_i$中选出最小的那个。
可以看出$F_i(x) - F_i(y)$仍是一个关于$x$的函数，$u(x)$的结果是一个$x$的映射，表示这个$x$集合中的元素映射到实数轴$R$.
一旦假设$u(x)=0$, 那么, $i\in\{1,...,m\},\{F_i(x) - F_i(y)\}$集合中的m个元素(关于x的函数)都要小于0,即没有一个$F_i(x)-F_i(y)$是大于0的。这等效于，$F={F_1, ..., F_m}$这个多元目标函数的可行解$\mathcal{S}$集合中存在x(可能多个)，使得任意的

$$F_i(x) \leq F_i(y), i\in\{1,...,m\}, \forall y\in\mathcal{S}$$

那么, 可以推得$x$是weakly pareto solution(可以取等号的情况)。
基于提出的算法用proximal gradient method迭代求解, 但是要如何分析收敛性呢, 最终的解为什么是pareto efficient的解呢,
这就要结合以上的Merit function的分析了,
所以寻找pareto解法收敛过程就变成了如何对Merit funciton求解其极限为0的过程了,求解得到$x$如果使得Merit Function收敛到0, 那么这个解就是pareto解。

Algorithm

算法其实步骤不多,比较好理解,但是文章[1]中的算法自定义了一些变量,需要好好理解下。
待续…

Convergence

待续…

Conclusion

对比与前一篇文章 一种多目标优化中的pareto最优解的方法---MGDA的小结中分析的MGDA算法，这两篇文章(同一作者)更加理论的分析了算法的收敛性，前一篇文章的算法收敛性分析，简直跟没有分析一样。。。当然这两个算法的思路也不一样。MGDA算法几乎不能保证找找到的是pareto efficient解，因为他只保证是pareto stationary解，但是[1]中的Lemma 2.1分析了，如果多目标的问题是convex，pareto stationary即为weakly Pareto optimal，所以也能说明如果MGDA找到了精确的pareto stationary解，即找到pareto efficient解。

[1] Convergence rates analysis of a multiobjective proximal gradient method
[2] Merit functions for multiobjective optimization and convergence rates analysis of multiobjective proximal gradient methods