优化算法的复杂度分析

Complexity analysis for optimization methods

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

The subject on convergence analysis of optimization methods is an important area in optimization theory. However, convergence is not sufficient as a criterion for comparing the efficiency of different algorithms.Therefore, we need another theory to measure the difficulty of optimization problems and the efficiency of optimization algorithms. This theory is called complexity analysis theory of optimization algorithms. This paper is divided into five parts. The first section introduces the basic setups of complexity analysis frameworks, gives the definition, methods and examples of complexity analysis, and summarizes the complexity results. In the second section, the complexity analysis for the smooth optimization problem is introduced. We give the upper and lower complexity bounds for different optimization problems, and also introduce the framework of convergence analysis for the accelerated gradient method. In the third section, the upper bounds of the complexity of nonsmooth optimization problems are introduced. We present the complexity analysis for the subgradient method, the mirror descent method, the center-of-gravity method, and the ellipsoid method. In the fourth section, we introduce the complexity analysis for the conditional gradient method, study its upper and lower bounds of complexity and present the framework of the accelerated conditional gradient method. In the fifth section, we introduce the complexity analysis of the stochastic optimization algorithm, and compare the confidence level for the convergence under convex and nonconvex settings.