论文标题
使用插值条件没有功能评估的插值条件的一阶方法的有限步骤性能
Finite Step Performance of First-order Methods Using Interpolation Conditions Without Function Evaluations
论文作者
论文摘要
我们提出了一项程序，以数值计算有限步骤的情况下，在给定算法上保证了使用Lipschitz连续梯度对强凸功能的不受约束优化。提供的解决方案方法是泰勒，Hendrickx和Glineur在[Math]中得出的一种替代方法。 prog。 161（1-2），2017年]。差异在于，我们的解决方案使用条件通过函数在感兴趣类别中的函数梯度插值和梯度评估，而他们的解决方案则使用条件将一组点，梯度评估和功能评估的插值来插值。这种替代解决方案的动机是，在许多情况下，算法和感兴趣的性能指标既不依赖于功能评估。主要的发展是一种程序，以避免在这些条件数量中遭受阶乘增长，而在解决最坏情况下的表现时，该套件的大小将被插值。
We present a procedure to numerically compute finite step worst case performance guarantees on a given algorithm for the unconstrained optimization of strongly convex functions with Lipschitz continuous gradients. The solution method provided serves as an alternative approach to that derived by Taylor, Hendrickx, and Glineur in [Math. Prog. 161 (1-2), 2017]. The difference lies in the fact that our solution uses conditions for the interpolation of a set of points and gradient evaluations by the gradient of a function in the class of interest, whereas their solution uses conditions for the interpolation of a set of points, gradient evaluations, and function evaluations by a function in the class of interest. The motivation for this alternative solution is that, in many cases, neither the algorithm nor the performance metric of interest rely upon function evaluations. The primary development is a procedure to avoid suffering from the factorial growth in the number of these conditions with the size of the set to be interpolated when solving for the worst case performance.
