Affine-invariant contracting-point methods for Convex Optimization

• 成果类型: Article
• 署名作者: Doikov, Nikita; Nesterov, Yurii
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01761-9
• 发表日期: 2023
• 页码: 115-137
• 关键词: 1st-order methods; complexity

摘要

In this paper, we develop new affine-invariant algorithms for solving composite convex minimization problems with bounded domain. We present a general framework of Contracting-Point methods, which solve at each iteration an auxiliary subproblem restricting the smooth part of the objective function onto contraction of the initial domain. This framework provides us with a systematic way for developing optimization methods of different order, endowed with the global complexity bounds. We show that using an appropriate affine-invariant smoothness condition, it is possible to implement one iteration of the Contracting-Point method by one step of the pure tensor method of degree p >= 1 . The resulting global rate of convergence in functional residual is then O(1/k(p)), where k is the iteration counter. It is important that all constants in our bounds are affine-invariant. For p = 1, our scheme recovers well-known Frank-Wolfe algorithm, providing itwith a new interpretation by a general perspective of tensor methods. Finally, within our framework, we present efficient implementation and total complexity analysis of the inexact second-order scheme (p = 2), called Contracting Newton method. It can be seen as a proper implementation of the trust-region idea. Preliminary numerical results confirm its good practical performance both in the number of iterations, and in computational time.