优化算法的复杂度分析

CSpace

	优化算法的复杂度分析
	王奇超 1; 文再文 1; 蓝光辉 2; 袁亚湘 3
	2020
Source Publication	中国科学. 数学
ISSN	1674-7216
Volume	50 Issue:9 Pages:1271-1336
Abstract	优化算法的收敛性分析是优化中很重要的一个领域,然而收敛性并不足以作为比较不同算法效率的标准,因此需要另外一套衡量优化问题难易程度以及优化算法效率高低的理论,这套理论被称为优化算法的复杂度分析理论.本文共分为5个部分.第1节介绍复杂度分析的背景和理论框架,给出复杂度分析的定义、方法和例子,并总结本文中的复杂度结论.第2节介绍光滑优化问题的复杂度分析,给出不同优化问题的复杂度上界和下界,并给出加速梯度法收敛性分析的框架.第3节介绍非光滑优化问题的复杂度上界,介绍次梯度法、重心法、椭球法和近似点梯度法的复杂度分析.第4节介绍条件梯度法的复杂度分析,介绍条件梯度法的复杂度上界和下界,以及加速条件梯度法的框架.第5节介绍随机优化算法的复杂度分析,比较随机优化算法在凸和非凸问题下收敛的置信水平和复杂度.
Keyword	optimization method complexity analysis accelerated gradient method conditional gradient method stochastic optimization method 优化算法复杂度分析加速梯度法条件梯度法随机优化算法
Indexed By	CSCD
Language	中文
CSCD ID	CSCD:6823304
Citation statistics
Document Type	期刊论文
Identifier	http://ir.amss.ac.cn/handle/2S8OKBNM/57655
Collection	中国科学院数学与系统科学研究院
Affiliation	1.北京大学 2.H.Milton Stewart School of Industrial and Systems Engineering,Georgia Institute of Technology 3.中国科学院数学与系统科学研究院
Recommended Citation GB/T 7714	王奇超,文再文,蓝光辉,等. 优化算法的复杂度分析[J]. 中国科学. 数学,2020,50(9):1271-1336.
APA	王奇超,文再文,蓝光辉,&袁亚湘.(2020).优化算法的复杂度分析.中国科学. 数学,50(9),1271-1336.
MLA	王奇超,et al."优化算法的复杂度分析".中国科学. 数学 50.9(2020):1271-1336.

Files in This Item:
There are no files associated with this item.

If you have any objections to this item, please fill out the form below and the administrator will contact you as soon as possible.
Content:
Email：	*
Institution:
Verification Code:	Refresh

Any comments and suggestions are welcomed.
Title:	*
Content:
Email：	*
Verification Code:	Refresh

中国科学院数学与系统科学研究院机构知识库