一种改进的动态步长的次梯度算法

赵婷婷　王湘美

摘 要 次梯度法是解决大规模凸优化问题的经典和有效的方法之一， 步长的选取对次梯度法的收敛性起着至关重要的作用. Goffino等（1999）提出了动态步长次梯度算法，通过改进其中的一个参数，提出了改进的动态步长次梯度算法，并证明了改进算法的收敛性. 最后，通过数值实验可以看出改进的算法比原来的算法更有效.

关键词 计算数学;凸优化;次梯度算法;动态步长

中图分类号 0224文献标识码 A

Abstract The subgradient algorithm is one of the classical and important algorithms to solve the largescale convex optimization problems， and it is well known that the convergence of the algorithm depends heavily on the choice of the step sizes. A modified version of the dynamic step sizes proposed by Goffino（1999） was proposed and the convergence of the algorithm was established. Some numerical experiments illustrate that the new algorithm is more effective than the prior one.

Key words Computational mathematics;Convex optimization;Subgradient method;Dynamic step size rule

参考文献

[1] ERMOL'EV Y M. Methods of solution of nonlinear extremal problems[J]. Cybernetics， 1966， 2（4）：1-14.

[2] SHOR N Z. Minimization Methods for Nondifferentiable Functions[J]. Springer， 1985，3（11-12）：885-888.

[3] POLJAK B T. Minimization of nonsmooth functionals[J]. Gaea， 1985， 300（1）：752-754.

[4] KIM S， AHN H. Convergence of a generalized subgradient method for nondifferentiable convex optimization[J]. Math. Program.， 1991， 50（1-3）：75-80.

[5] GOFFINO J L， KIWIEL K C. Convergence of a simple subgradient level method[J]. Math. Program.， 1999， 85（1）：207-211.

[6] 史樹中. 凸分析[M]. 上海科学技术出版社， 1990.

[7] LONG Q， LI J  Y. Numerical Performance of subgradient methods in solving nonsmooth optimization problems[J]. Journal of Chongqing Normal University， 2013， 30（6）：25-30.