EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Subgradient ellipsoid method for nonsmooth convex problems

Anton Rodomanov iD, Yurii Nesterov

Mathematical Programming · 2023-05 · 199 (1-2) · 305-341

DOI: 10.1007/s10107-022-01833-4 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 14.06.2022. Verfasst von Anton Rodomanov und 1 weiteren Autor:innen. Beteiligte Einrichtung: Institute of Information and Communication Technologies, Electronics and Applied Mathematics (ICTEAM), Catholic University of Louvain (UCL), Louvain-…. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 23 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: european research council.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this paper, we present a new ellipsoid-type algorithm for solving nonsmooth problems with convex structure. Examples of such problems include nonsmooth convex 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 dimensionality 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).

Schlagwörter

Stichwörter der Autor:innen

Accuracy certificatesConvex optimizationEllipsoid methodNonsmooth optimizationSaddle-point problemsSeparating oracleSubgradient methodVariational inequalities

Autor:innen und Institutionen

  • Institute of Information and Communication Technologies, Electronics and Applied Mathematics (ICTEAM), Catholic University of Louvain (UCL), Louvain-la-Neuve, Belgium.
  • Center for Operations Research and Econometrics (CORE), Catholic University of Louvain (UCL), Louvain-la-Neuve, Belgium.

ORCID-Profile: Anton Rodomanov

Förderung

  • european research council

Zitieren

APA

Rodomanov, A., & Nesterov, Y. (2023). Subgradient ellipsoid method for nonsmooth convex problems. Mathematical Programming, 199(1-2), 305-341. https://doi.org/10.1007/s10107-022-01833-4

Vancouver

Rodomanov A, Nesterov Y. Subgradient ellipsoid method for nonsmooth convex problems. Mathematical Programming. 2023;199(1-2):305-341. doi:10.1007/s10107-022-01833-4

BibTeX
@article{Rodomanov2023,
  author = {Rodomanov, Anton and Nesterov, Yurii},
  title = {Subgradient ellipsoid method for nonsmooth convex problems},
  journal = {Mathematical Programming},
  year = {2023},
  volume = {199},
  number = {1-2},
  pages = {305--341},
  doi = {10.1007/s10107-022-01833-4}
}
Kostenlos starten →