Generalized Uniformly Optimal Methods for Nonlinear Programming
Generalized Uniformly Optimal Methods for Nonlinear Programming
复制标题
DOI：
10.1007/s10915-019-00915-4
复制
发表时间：
2019-06-01
影响因子：
2.5
通讯作者：
Zhang, Hongchao
中科院分区：
文献类型：
--
作者：
Ghadimi, Saeed;Lan, Guanghui;Zhang, Hongchao
一致最优凸规划算法被设计用于实现凸优化问题的最优复杂度界，而不考虑目标函数的平滑程度。在本文中，我们提出了一个通用框架来扩展这些现有算法来解决更一般的非线性，可能是非凸的优化问题。基本思想是将局部搜索步骤（梯度下降或拟牛顿迭代）纳入一致最优凸规划方法中，然后强制沿轨迹计算的函数值具有单调递减性质。虽然通常不知道非凸规划的最优方法，但这些类型的算法将在不需要任何问题参数的情况下实现非凸问题的最优复杂性和凸问题的最优复杂性。因此，我们可以对一般的非线性规划问题有一个统一的处理方法，而不考虑它们的凹凸性和光滑性。特别地，我们证明了加速梯度和水平方法，最初都是为解决凸优化问题而设计的，可以统一地用于解决凸和非凸问题。在类似的情况下，我们展示了一些研究得很好的非线性规划技术，例如准牛顿迭代，可以嵌入到最优凸优化算法中，以可能进一步提高它们的数值性能。我们的理论和算法的发展是由一些有希望的数值结果得到解决一些重要的非凸和非线性数据分析问题在文献中补充。
Uniformly optimal convex programming algorithms have been designed to achieve the optimal complexity bounds for convex optimization problems regardless of the level of smoothness of the objective function. In this paper, we present a generic framework to extend such existing algorithms to solve more general nonlinear, possibly nonconvex, optimization problems. The basic idea is to incorporate a local search step (gradient descent or Quasi-Newton iteration) into the uniformly optimal convex programming methods, and then enforce a monotone decreasing property of the function values computed along the trajectory. While optimal methods for nonconvex programming are not generally known, algorithms of these types will achieve the best known complexity for nonconvex problems, and the optimal complexity for convex ones without requiring any problem parameters. As a consequence, we can have a unified treatment for a general class of nonlinear programming problems regardless of their convexity and smoothness level. In particular, we show that the accelerated gradient and level methods, both originally designed for solving convex optimization problems only, can be used for solving both convex and nonconvex problems uniformly. In a similar vein, we show that some well-studied techniques for nonlinear programming, e.g., Quasi-Newton iteration, can be embedded into optimal convex optimization algorithms to possibly further enhance their numerical performance. Our theoretical and algorithmic developments are complemented by some promising numerical results obtained for solving a few important nonconvex and nonlinear data analysis problems in the literature.