梯度Q-线性收敛的光滑凸极小化的一阶算法

doi:10.15960/j.cnki.issn.1007-6093.2021.01.009

运筹学学报 ›› 2021, Vol. 25 ›› Issue (1): 96-106.doi: 10.15960/j.cnki.issn.1007-6093.2021.01.009

梯度Q-线性收敛的光滑凸极小化的一阶算法

叶加青¹, 陈倩竹², 胡海平²^,*()

1. 淮南联合大学信息工程学院, 安徽淮南 232038
2. 上海大学理学院, 上海 200444

收稿日期:2019-03-18 出版日期:2021-03-15 发布日期:2021-03-05
通讯作者: 胡海平 E-mail:hu_jack@staff.shu.edu.cn
作者简介:胡海平 E-mail: hu_jack@staff.shu.edu.cn
基金资助:
安徽省质量工程重点教研项目(2018jyxm1429)

Optimizing first-order methods for smooth convex minimization of gradient Q-linearly convergence

Jiaqing YE¹, Qianzhu CHEN², Haiping HU²^,*()

1. School of Information Engineering, Huainan Union University, Huainan 232038, Anhui, China
2. College of Sciences, Shanghai University, Shanghai 200444, China

Received:2019-03-18 Online:2021-03-15 Published:2021-03-05
Contact: Haiping HU E-mail:hu_jack@staff.shu.edu.cn

摘要/Abstract

摘要：

受性能估计问题（PEP）方法的启发，通过考察最坏函数误差的收敛边界（即效率），优化了迭代点对应的梯度满足Q-线性收敛的光滑凸极小化的一阶方法的步长系数。介绍新的有效的一阶方法，称为QGM，具有与优化梯度法（OGM）类似的计算有效形式。

关键词: 一阶算法, 光滑凸极小化, 梯度法

Abstract:

Inspired by the performance estimation problem (PEP) method, this paper optimizes the step size of the first order method of smooth convex minimization that the gradient corresponding to the iteration point satisfies Q-convergence by examining the worst case convergence boundary (i.e. efficiency) of the cost function. This paper introduces a new and effective first-order method called QGM, which has an effective computation form similar to the optimized gradient method (OGM).

Key words: first-order methods, smooth convex minimization, gradient method

中图分类号:

O224

叶加青, 陈倩竹, 胡海平. 梯度Q-线性收敛的光滑凸极小化的一阶算法[J]. 运筹学学报, 2021, 25(1): 96-106.

Jiaqing YE, Qianzhu CHEN, Haiping HU. Optimizing first-order methods for smooth convex minimization of gradient Q-linearly convergence[J]. Operations Research Transactions, 2021, 25(1): 96-106.

图/表 1

1	Nesterov Y . A method for unconstrained convex minimization problemwith the rate of convergence O(1/k²)[J]. Soviet Mathematics Doklady, 1983, 27 (2): 372- 376.
2	Nesterov Y. {Introductory lectures on convex optimization: A basiccourse[M]// Applied Optimization, Dordrecht: Kluwer Academic Publishers, 2004.
3	Drori Y , Teboulle M . Performance of first-order methods for smooth convex minimization: a novel approach[J]. Mathematical Programming, 2014, 145 (1-2): 451- 482. doi: 10.1007/s10107-013-0653-0
4	Kim D , Fessler J A . Optimized first-order methods for smooth convex minimization[J]. Mathematical Programming, 2014, 159 (1-2): 81- 107.
5	Kim D, Fessler J A. Optimizing the Efficiency of First-order Methods for Decreasing the Gradient of Smooth Convex Functions. arXiv: 1803.06600v2[math. OC]
6	Grant M , Boyd S . Graph Implementations for Nonsmooth Convex Programs[J]. Lecture Notes in Control and Information Sciences, 2008, 371, 95- 110.
7	Beck A . Quadratic Matrix Programming[J]. SIAM Journal on Optimization, 2007, 17 (4): 1224- 1238. doi: 10.1137/05064816X

N	FGM	OGM	QGM
5	LR²/28.66	LR²/53.80	LR²/66.90
10	LR²/81.07	LR²/153.63	LR²/217.80
20	LR²/263.65	LR²/515.39	LR²/780.53
40	LR²/934.89	LR²/1869.2	LR²/2952.7

[1]	吴晓宇, 邵虎, 刘鹏杰, 周金诚. 两个充分下降的RMIL型共轭梯度法及图像去噪应用[J]. 运筹学学报（中英文）, 2026, 30(2): 79-92.
[2]	徐洋, 王军霖, 徐姿. 单边相对光滑非凸-凹极小极大问题的镜像梯度算法[J]. 运筹学学报（中英文）, 2024, 28(1): 18-28.
[3]	刘鹏杰, 江羡珍, 宋丹. 一类具有充分下降性的谱共轭梯度法[J]. 运筹学学报, 2022, 26(4): 87-97.
[4]	张慧灵, 徐洋, 徐姿. 分块凸-非凹极小极大问题的交替近端梯度算法[J]. 运筹学学报, 2022, 26(4): 64-74.
[5]	张慧玲, 赛·闹尔再, 吴晓云. 修正PRP共轭梯度方法求解无约束最优化问题[J]. 运筹学学报, 2022, 26(2): 64-72.
[6]	孙聪, 张亚. 梯度法简述[J]. 运筹学学报, 2021, 25(3): 119-132.
[7]	徐姿, 张慧灵. 非凸极小极大问题的优化算法与复杂度分析[J]. 运筹学学报, 2021, 25(3): 74-86.
[8]	钱晓慧, 王湘美. 一种单位化的增量梯度算法[J]. 运筹学学报, 2021, 25(2): 81-92.
[9]	李红武, 谢敏, 张榕. 一类非光滑凸优化问题的邻近梯度算法[J]. 运筹学学报, 2021, 25(1): 61-72.
[10]	邵淑婷, 杜守强. 求解一类特殊非光滑极大值函数方程的光滑保守DPRP共轭梯度法[J]. 运筹学学报, 2018, 22(3): 69-78.
[11]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[12]	陈香萍. 谱HS投影算法求解非线性单调方程组[J]. 运筹学学报, 2018, 22(3): 15-27.
[13]	陈元媛, 高岩, 刘志敏, 杜守强. 一类特殊优化问题的光滑梯度法[J]. 运筹学学报, 2017, 21(2): 119-125.
[14]	田朝薇, 张立卫. 从常步长梯度方法的视角看不可微凸优化增广Lagrange方法的收敛性[J]. 运筹学学报, 2017, 21(1): 111-117.

梯度Q-线性收敛的光滑凸极小化的一阶算法

Optimizing first-order methods for smooth convex minimization of gradient Q-linearly convergence

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

相关文章 14

编辑推荐

Metrics

本文评价