Affine-invariant contracting-point methods for Convex Optimization

Nikita Doikov () and Yurii Nesterov ()
Additional contact information
Nikita Doikov: Université catholique de Louvain, ICTEAM
Yurii Nesterov: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3240, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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 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 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.

Keywords: Convex optimization; Frank-Wolfe algorithm; Newton method; Trust region methods; Tensor methods; Global complexity bounds (search for similar items in EconPapers)
Pages: 23
Date: 2023-01-01
Note: In: Mathematical Programming, 2023, vol. 198(1), p. 115-137
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvrp:3240

DOI: 10.1007/s10107-021-01761-9

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().