有哪些信誉好的足球投注网站- 1、本文档共69页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
优化算法复杂度分析简介
1 ∗1 †2 ‡3
王奇超 , 文再文 , 蓝光辉 , and 袁亚湘
1 北京大学北京国际数学研究中心
2 乔治亚理工学院 H. Milton Stewart 工业和系统工程学院
3 中国科学院数学与系统科学研究院，计算数学与科学工程计算研究所
摘要
优化算法的收敛性分析是优化中很重要的一个领域。然而收敛性并不足以作为比较不同算法效率的标准，
因此我们需要另外一套衡量优化问题难易程度以及优化算法效率高低的理论。这套理论被称为优化算法的复
杂度分析理论。本论文分共为五个部分。第一章介绍复杂度分析的背景和理论框架，给出复杂度分析的定义，
方法和例子，并总结本论文中的复杂度结论。第二章介绍光滑优化问题的复杂度分析，给出了不同优化问题
的复杂度上界和下界，并给出加速梯度法收敛性分析的框架。第三章介绍非光滑优化问题的复杂度上界，介
绍了次梯度法，重心法，椭球法和近似点梯度法的复杂度分析。第四章介绍了条件梯度法的复杂度分析，介
绍了条件梯度法的复杂度上界和下界，以及加速条件梯度法的框架。第五章介绍随机优化算法的复杂度分析，
比较了随机优化算法在凸和非凸问题下收敛的置信水平以及复杂度。
目录
1 复杂度分析的理论基础 2
1.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 复杂度分析的问题模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 全局信息 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 局部信息 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 解的精度 ϵ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 复杂度分析的算法模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.1 复杂度分析的度量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
文档评论（0）