多梯度下降算法 (一）

多梯度下降算法

考虑如下的无约束多目标优化问题：

一般的做法是对多个目标作加权处理得到一个单目标的函数，然后利用梯度下降，智能优化算法如状态转移算法，遗传算法等求解。当然，也可以直接利用智能优化算法求解上述问题，得到一组Pareto解。尽管智能优化算法在求解全局最优解方面相对梯度下降算法有着一定优势，但其求解速度往往是比较慢的。那么，有没有基于梯度的算法来求解问题（1）呢？答案是有的，这就是多梯度下降算法 （Multiple Gradient Descent Algorithm (MGDA)) ,参见文献¹²:

梯度下降

我们都知道，对于无约束的单目标优化问题，利用梯度下降算法，在足够小的步长下，能保证下一步的值比上一步要小，其更新方式：, 其中 为步长, 为搜索方向，当 时， 该算法也叫最速下降算法。为得到此结论，首先对进行泰勒展开：

由上式可知函数沿着方向下降的速率为：

其中 为梯度 和搜索方向间的夹角，不难看出，要使得函数f(x_k) 沿着下降（也即),夹角应大于90度，也即； 要使得下降速率最大，夹角应该为180度，为梯度的相反方向 ， 因此此时也可表示为：

多梯度下降

上面可以看出，梯度下降的本质其实是找到一个搜索方向 使得， 那么对于多目标问题，如果能找到一个搜索方向使得, 则该方向会使得所有目标函数都朝着下降的方向去更新，那怎么求一个最速下降的搜索方向呢？上文提到过，对于单目标的梯度下降，搜索方向可通过求解问题（2）, 类似的，多梯度下降的方向可通过求解下面的优化问题³：

其思路也比较清楚，首先最大化 , 然后的过程和问题（2）一样，就是要使得 最大的值也小于0，那么这样就达到了能使得所有目标函数下降的目的。不过 （3）并不好解，因此我们将其转化成：

该问题的对偶问题为⁴：

且问题（4）的KKT条件为： ³。可以看出， d_k为的一个凸组合。

根据问题（3）可以看出，如果说不存在这样的使得 , 则（3）的最优解,此时算法无法继续更新，达到Pareto最优点。如果存在这么一个使得 ，则有。因此，假设为问题 （4） 的解，则可得到如下推论¹：

1. 如果 是Pareto最优解，则 ,
2. 如果不是Pareto最优解，则有：
   

两个目标的场景

在两个目标的场景下， 其中，。可通过求解，其示意图如下：

上图较为直观，图中间的情况可通过对目标函数求导得到, 这里不做细致的推导,可参考文献⁵⁶⁷ 。

应用场景

目前该算法已被应用到多个领域，如多任务学习⁵，多车牌识别⁶⁷, 联邦多目标学习⁸等。