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

发布时间：2018-04-12 13:44

本文选题：一阶梯度方法 + 个体收敛速率　；参考：《计算机研究与发展》2017年03期

【摘要】：投影次梯度算法(projected subgradient method,PSM)是求解非光滑约束优化问题最简单的一阶梯度方法,目前只是对所有迭代进行加权平均的输出方式得到最优收敛速率,其个体收敛速率问题甚至作为open问题被提及.最近,Nesterov和Shikhman在对偶平均方法(dual averaging method,DAM)的迭代中嵌入一种线性插值操作,得到一种拟单调的求解非光滑问题的次梯度方法,并证明了在一般凸情形下具有个体最优收敛速率,但其讨论仅限于对偶平均方法.通过使用相同技巧,提出了一种嵌入线性插值操作的投影次梯度方法,与线性插值对偶平均方法不同的是,所提方法还对投影次梯度方法本身进行了适当的修改以确保个体收敛性.同时证明了该方法在一般凸情形下可以获得个体最优收敛速率,并进一步将所获结论推广至随机方法情形.实验验证了理论分析的正确性以及所提算法在保持实时稳定性方面的良好性能.
[Abstract]:Projection subgradient algorithm (projected subgradient method PSM) is the simplest first-order gradient method for solving non-smooth constrained optimization problems. At present, it is only a weighted average of all iterations to obtain the optimal convergence rate.The problem of individual convergence rate is even mentioned as a open problem.Recently, Nesterov and Shikhman embedded a linear interpolation operation in the iteration of dual averaging method DAM, and obtained a quasi-monotone subgradient method for solving non-smooth problems, and proved that there is an individual optimal convergence rate in general convex cases.But the discussion is limited to the dual averaging method.By using the same technique, a projection subgradient method with embedded linear interpolation operations is proposed, which is different from the dual average method of linear interpolation.The proposed method also modifies the projection subgradient method itself to ensure individual convergence.At the same time, it is proved that the method can obtain the optimal convergence rate of individuals in the general convex case, and the results obtained are further extended to the case of stochastic methods.Experiments verify the correctness of the theoretical analysis and the good performance of the proposed algorithm in maintaining real-time stability.
【作者单位】：中国人民解放军理工大学指挥信息系统学院;中国人民解放军陆军军官学院十一系;
【基金】：国家自然科学基金项目(61673394,61273296)~~
【分类号】：O224

【相似文献】