文献类型：期刊文章

作　　者：王奇超[1] 文再文[1] 蓝光辉[2] 袁亚湘[3]

Qichao Wang;Zaiwen Wen;Guanghui Lan;Ya-xiang Yuan

机构地区：[1]北京大学北京国际数学研究中心,北京100871 [2]H.Milton Stewart School of Industrial and Systems Engineering,Georgia Institute of Technology,Atlanta,GA 30332,USA [3]中国科学院数学与系统科学研究院计算数学与科学工程计算研究所,北京100190

出　　处：《中国科学：数学》

基　　金：国家自然科学基金(批准号:11831002和11331012)资助项目。

年　　份：2020

卷　　号：50

期　　号：9

起止页码：1271-1336

语　　种：中文

收录情况：BDHX、BDHX2017、CSCD、CSCD2019_2020、JST、PUBMED、RCCSE、ZGKJHX、ZMATH、核心刊

摘　　要：优化算法的收敛性分析是优化中很重要的一个领域,然而收敛性并不足以作为比较不同算法效率的标准,因此需要另外一套衡量优化问题难易程度以及优化算法效率高低的理论,这套理论被称为优化算法的复杂度分析理论.本文共分为5个部分.第1节介绍复杂度分析的背景和理论框架,给出复杂度分析的定义、方法和例子,并总结本文中的复杂度结论.第2节介绍光滑优化问题的复杂度分析,给出不同优化问题的复杂度上界和下界,并给出加速梯度法收敛性分析的框架.第3节介绍非光滑优化问题的复杂度上界,介绍次梯度法、重心法、椭球法和近似点梯度法的复杂度分析.第4节介绍条件梯度法的复杂度分析,介绍条件梯度法的复杂度上界和下界,以及加速条件梯度法的框架.第5节介绍随机优化算法的复杂度分析,比较随机优化算法在凸和非凸问题下收敛的置信水平和复杂度.

关 键 词：优化算法 复杂度分析  加速梯度法  条件梯度法  随机优化算法  

分 类 号：O224] TP18[数学类]