凸优化和单调变分不等式收缩算法的统一框架

摘要

线性约束的凸优化问题可以转化成一个形式更一般的单调变分不等式.在变分不等式的框架下研究最优化问题的求解方法,就像微积分中利用导数求函数的极值,常常会带来很大的方便.求解单调变分不等式的投影收缩算法有一个预测-校正的统一框架,基于＂孪生方向和相同步长＂有两类花费几乎相当的算法,计算实践证明第二类算法效率往往更高.近年发展起来并被广泛采用的凸规划的分裂收缩算法属于一个更一般的框架,这个框架中的预测同样提供了一对孪生方向.迄今为止的凸规划的分裂收缩算法,都相当于变分不等式投影收缩算法中的第一类算法.本文指出,利用现有的步长法则,配上孪生方向中的另一个方向,同样可以构造相应的第二类算法.本文在统一框架下证明了两类算法的O（1/t）迭代复杂性.