ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (3): 529-536.doi: 10.7544/issn1000-1239.2017.20160155

• 人工智能 • 上一篇    下一篇

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

陶蔚1,潘志松1,朱小辉2,陶卿2   

  1. 1(中国人民解放军理工大学指挥信息系统学院 南京 210007); 2(中国人民解放军陆军军官学院十一系 合肥 230031) (wtao_plaust@163.com)
  • 出版日期: 2017-03-01
  • 基金资助: 
    国家自然科学基金项目(61673394,61273296)

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

Tao Wei1, Pan Zhisong1, Zhu Xiaohui2, Tao Qing2   

  1. 1(College of Command Information System, PLA University of Science and Technology, Nanjing 210007); 2(11st Department, Army Officer Academy of PLA, Hefei 230031)
  • Online: 2017-03-01

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

关键词: 一阶梯度方法, 个体收敛速率, 投影次梯度方法, 线性插值操作, 对偶平均方法

Abstract: 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.

Key words: first-order method, individual convergence rate, projected subgradient method, linear interpolation operation, dual averaging method

中图分类号: