Affine-invariant contracting-point methods for Convex Optimization

DOI10.1007/S10107-021-01761-9zbMATH Open1512.90162arXiv2009.08894MaRDI QIDQ6349404

Yu. E. Nesterov, Nikita Doikov

Publication date: 18 September 2020

Abstract: 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 $pgeq1$. The resulting global rate of convergence in functional residual is then $calO(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 it with 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.

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06)

This page was built for publication: Affine-invariant contracting-point methods for Convex Optimization