Subgradient ellipsoid method for nonsmooth convex problems

被引：0

作者：

Anton Rodomanov

Yurii Nesterov

机构：

[1] Catholic University of Louvain (UCL),Institute of Information and Communication Technologies, Electronics and Applied Mathematics (ICTEAM)

[2] Catholic University of Louvain (UCL),Center for Operations Research and Econometrics (CORE)

来源：

Mathematical Programming | 2023年 / 199卷

关键词：

Subgradient method; Ellipsoid method; Accuracy certificates; Separating oracle; Convex optimization; Nonsmooth optimization; Saddle-point problems; Variational inequalities; 90C25; 90C47; 68Q25;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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

引用

页码：305 / 341

页数：36

共 28 条

[1]

Auslender A(1973)Résolution numérique d’inégalités variationnelles. RAIRO 7 67-72

[2]

Bland R(1981)The ellipsoid method: a survey Oper. Res. 29 1039-1091

[3]

Goldfarb D(2016)Stochastic intermediate gradient method for convex problems with stochastic inexact oracle J. Optim. Theory Appl. 171 121-145

[4]

Todd M(1981)The ellipsoid method and its consequences in combinatorial optimization Combinatorica 1 169-197

[5]

Dvurechensky P(1979)A polynomial algorithm in linear programming Soviet Math. Dokl. 244 1093-1096

[6]

Gasnikov A(2012)An optimal method for stochastic composite optimization Math. Program. 133 365-397

[7]

Grötschel M(1965)An algorithm for minimizing convex functions Soviet Math. Dokl. 160 1244-1247

[8]

Lovász L(2009)Robust stochastic approximation approach to stochastic programming SIAM J. Optim. 19 1574-1609

[9]

Schrijver A(2010)Accuracy certificates for computational problems with convex structure Math. Oper. Res. 35 52-78

[10]

Khachiyan L(1983)A method for solving the convex programming problem with convergence rate Soviet Math. Dokl. 269 543-547

← 1 2 3 →