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

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

Operations Research Transactions ›› 2021, Vol. 25 ›› Issue (1): 96-106.doi: 10.15960/j.cnki.issn.1007-6093.2021.01.009

Previous Articles Next Articles

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

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

CLC Number:

O224

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.

Figures/Tables 1

References 7

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]	SUN Cong, ZHANG Ya. A brief review on gradient method [J]. Operations Research Transactions, 2021, 25(3): 119-132.
[2]	CHEN Xiangping. Spectral HS projection algorithm for solving nonlinear monotone equations [J]. Operations Research Transactions, 2018, 22(3): 15-27.
[3]	. A sufficient descent conjugate gradient method for nonlinear unconstrained optimization problems [J]. Operations Research Transactions, 2018, 22(3): 59-68.
[4]	SHAO Shuting, DU Shouqiang. Smoothing cautious DPRP conjugate gradient method for solving a kind of special nonsmooth equations with max-type function [J]. Operations Research Transactions, 2018, 22(3): 69-78.
[5]	CHEN Yuanyuan, GAO Yan, LIU Zhimin, DU Shouqiang. The smoothing gradient method for a kind of special optimization problem [J]. Operations Research Transactions, 2017, 21(2): 119-125.
[6]	TIAN Zhaowei, ZHANG Liwei. A look at the convergence of the augmented Lagrange method for nondifferentiable convex programming from the view of a gradient method with constant stepsize [J]. Operations Research Transactions, 2017, 21(1): 111-117.
[7]	WAN Rui, XU Zi. On the linear convergence of the general alternating proximal gradient method for convex minimization [J]. Operations Research Transactions, 2014, 18(3): 1-12.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 1

References 7

Related Articles 7

Recommended Articles

Metrics

Comments