ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2017, Vol. 54 ›› Issue (3): 529-536.doi: 10.7544/issn1000-1239.2017.20160155

Previous Articles     Next Articles

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

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

CLC Number: