Subgradient ellipsoid method for nonsmooth convex problems

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

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

Abstract: In this paper, we present a new ellipsoid-type algorithm for solving nonsmooth problems with convex structure. Examples of such problems include nonsmooth con- vex minimization problems, convex-concave saddle-point problems and variational inequalities with monotone operator. Our algorithm can be seen as a combination of the standard Subgradient and Ellipsoid methods. However, in contrast to the latter one, the proposed method has a reasonable convergence rate even when the dimen- sionality of the problem is sufficiently large. For generating accuracy certificates in our algorithm, we propose an efficient technique, which ameliorates the previously known recipes (Nemirovski in Math Oper Res 35(1):52–78, 2010).

Keywords: Subgradient method; Ellipsoid method; Accuracy certificates; Separating oracle; Convex optimization; Nonsmooth optimization; Saddle-point problems; Variational inequalities (search for similar items in EconPapers)
Pages: 37
Date: 2023-01-01
Note: In: Mathematical Programming, 2023, vol. 199, p. 305-341
References: Add references at CitEc
Citations:

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:3236

DOI: 10.1007/s10107-022-01833-4

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