优化算法的复杂度分析

来源 :中国科学:数学 | 被引量 : 0次 | 上传用户:nsldp
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
优化算法的收敛性分析是优化中很重要的一个领域,然而收敛性并不足以作为比较不同算法效率的标准,因此需要另外一套衡量优化问题难易程度以及优化算法效率高低的理论,这套理论被称为优化算法的复杂度分析理论.本文共分为5个部分.第1节介绍复杂度分析的背景和理论框架,给出复杂度分析的定义、方法和例子,并总结本文中的复杂度结论.第2节介绍光滑优化问题的复杂度分析,给出不同优化问题的复杂度上界和下界,并给出加速梯度法收敛性分析的框架.第3节介绍非光滑优化问题的复杂度上界,介绍次梯度法、重心法、椭球法和近似点梯度法的复杂度分析.第4节介绍条件梯度法的复杂度分析,介绍条件梯度法的复杂度上界和下界,以及加速条件梯度法的框架.第5节介绍随机优化算法的复杂度分析,比较随机优化算法在凸和非凸问题下收敛的置信水平和复杂度.
其他文献
本文以儿童安全座椅为研究对象,系统分析对比了我国与国外儿童安全座椅发展现状及标准法规现状,期望本文能为我国儿童安全座椅的规范使用及其相关标准、法规的制定提供研究思
自然审美过程中“心”与“物”的关系是《文心雕龙·物色》篇的重要内容。由于涉及到复杂的审美心理机制,学者们的探讨或沿用传统的“感发说”,或使用“心物交融”的模糊提
针对白城地区220 kV及500 kV输电线路工程需要,以该地区气象部门记录的历年最大风速值为原始条件,通过对原始资料的分析论证取得了有效的可靠数据,对这些数据进行统计计算,得
为了提高我国青少年校园足球政策的活力,采用文献资料、逻辑分析、数理统计等研究方法,对我国青少年校园足球改革发展的政策活性化进行了研究。首先梳理了活性化概念的发展历
大数据背景下,随着会计信息化的逐步发展,企业的管理与改革面临严峻挑战,在目前科技飞速发展阶段,只有将会计信息化合理地应用于企业内部,才能配合企业各部门,完善部门职能,
提出一种新型的基于两自由度内模电流控制死区时间补偿方案。首先,将逆变器死区时间引起的误差电压看成扰动,在S域中建立逆变器模型和电机动态逆电流模型。然后通过幅值和相位
为了满足《浙江省中药饮片代煎服务工作质量管理规范》溯源监管的要求,联合代煎公司开发了配方煎药智能管理系统,实行了对饮片煎煮的每个环节都可以追溯查询。为了方便医疗机
话题演化可以帮助人们快速获取信息和了解趋势.提出了一种挖掘话题随时间变化的方法,通过话题抽取和话题关联实现话题的演化.对不同时间段的文集进行话题的自动抽取,话题数目
为了解决采用传统的集散控制系统(DCS)设备不易实现生产的信息化的现实,采用基于现场总线控制系统FCS(fieldbus control system)的自动化技术来实现生产的信息化。详细介绍了FCS在
盐商这一中国近代社会的活跃阶层,由于他们“贾而好儒”的特性,推动了近代书画审美观的转变,同时也使得绘画的风格和题材分别做出了相应的调整。袁氏绘画风格的出现即是这一审美