线性插值投影次梯度方法的最优个体收敛速率

The Optimal Individual Convergence Rate for the Projected Subgradient Method with Linear Interpolation Operation

投影次梯度算法(projected subgradient method,PSM)是求解非光滑约束优化问题最简单的一阶梯度方法,目前只是对所有迭代进行加权平均的输出方式得到最优收敛速率,其个体收敛速率问题甚至作为open问题被提及.最近,Nesterov和Shikhman在对偶平均方法(dual averaging method,DAM)的迭代中嵌入一种线性插值操作,得到一种拟单调的求解非光滑问题的次梯度方法,并证明了在一般凸情形下具有个体最优收敛速率,但其讨论仅限于对偶平均方法.通过使用相同技巧,提出了一种嵌入线性插值操作的投影次梯度方法,与线性插值对偶平均方法不同的是,所提方法还对投影次梯度方法本身进行了适当的修改以确保个体收敛性.同时证明了该方法在一般凸情形下可以获得个体最优收敛速率,并进一步将所获结论推广至随机方法情形.实验验证了理论分析的正确性以及所提算法在保持实时稳定性方面的良好性能.

The projected subgradient method is one of the simplest algorithms for solving nonsmooth constrained optimization problems.So far,only the optimal convergence rate in terms of the averaged output has been obtained.Its individual convergence rate is even regarded as an open problem.Recently,by incorporating a linear interpolation operation into the dual averaging methods,Nesterov and Shikhman achieved a quasi-monotone subgradient method for nonsmooth convex minimization,which is proved to have the optimal individual convergence rate.Unfortunately,their discussion is only limited to the dual averaging methods.This paper focuses on the individual convergence rate of projected subgradient methods.By employing the same technique,we present a projected subgradient method with linear interpolation operation.In contrast to the work of Nesterov and Shikhman,the projected subgradient method itself in the proposed method has to be modified slightly so as to ensure the individual convergence rate. We prove that the proposed method has the optimal individual convergence rate for solving nonsmooth convex problems.Further,the corresponding stochastic method is proved to have the optimal individual convergence rate.This can be viewed as an approximate answer to the open problem of optimal individual convergence of the projected subgradient methods.The experiments verify the correctness of our analysis and demonstrate the high performance of the proposed methods in real-time stabilization.