×

A family of subgradient-based methods for convex optimization problems in a unifying framework. (English) Zbl 1355.90065

Summary: We propose a new family of subgradient- and gradient-based methods which converges with optimal complexity for convex optimization problems whose feasible region is simple enough. This includes cases where the objective function is non-smooth, smooth, have composite/saddle structure, or are given by an inexact oracle model. We unified the way of constructing the subproblems which are necessary to be solved at each iteration of these methods. This permitted us to analyse the convergence of these methods in a unified way compared to previous results which required different approaches for each method/algorithm. Our contribution rely on two well-known methods in non-smooth convex optimization: the mirror-descent method (MDM) by Nemirovski-Yudin and the dual-averaging method by Nesterov. Therefore, our family of methods includes them and many other methods as particular cases. For instance, the proposed family of classical gradient methods and its accelerations generalize Devolder et al.’s, Nesterov’s primal/dual gradient methods, and Tseng’s accelerated proximal gradient methods. Also our family of methods can partially become special cases of other universal methods, too. As an additional contribution, the novel extended MDM removes the compactness assumption of the feasible region and the fixation of the total number of iterations which is required by the original MDM in order to attain the optimal complexity.

MSC:

90C25 Convex programming
90C52 Methods of reduced gradient type
68Q25 Analysis of algorithms and problem complexity
49M37 Numerical methods based on nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] DOI: 10.1137/S1052623403427823 · Zbl 1113.90118 · doi:10.1137/S1052623403427823
[2] DOI: 10.1016/S0167-6377(02)00231-6 · Zbl 1046.90057 · doi:10.1016/S0167-6377(02)00231-6
[3] DOI: 10.1137/080716542 · Zbl 1175.94009 · doi:10.1137/080716542
[4] DOI: 10.1137/100818327 · Zbl 1251.90304 · doi:10.1137/100818327
[5] DOI: 10.1016/0041-5553(67)90040-7 · doi:10.1016/0041-5553(67)90040-7
[6] DOI: 10.1007/s10107-013-0677-5 · Zbl 1317.90196 · doi:10.1007/s10107-013-0677-5
[7] DOI: 10.1080/00207728108963798 · Zbl 0467.65028 · doi:10.1080/00207728108963798
[8] DOI: 10.1137/110848864 · Zbl 1301.62077 · doi:10.1137/110848864
[9] DOI: 10.1137/110848876 · Zbl 1293.62167 · doi:10.1137/110848876
[10] DOI: 10.1214/10-SSY010 · Zbl 1297.90097 · doi:10.1214/10-SSY010
[11] DOI: 10.1007/s10107-010-0434-y · Zbl 1273.90136 · doi:10.1007/s10107-010-0434-y
[12] DOI: 10.1007/s10107-008-0261-6 · Zbl 1208.90113 · doi:10.1007/s10107-008-0261-6
[13] DOI: 10.1137/120894464 · Zbl 1297.90119 · doi:10.1137/120894464
[14] DOI: 10.1137/070704277 · Zbl 1189.90109 · doi:10.1137/070704277
[15] Nemirovski A., Problem Complexity and Method Efficiency in Optimization (1979)
[16] Nesterov Yu., Sov. Math. Dokl. 27 pp 372– (1983)
[17] DOI: 10.1007/978-1-4419-8853-9 · doi:10.1007/978-1-4419-8853-9
[18] DOI: 10.1137/S1052623403422285 · Zbl 1096.90026 · doi:10.1137/S1052623403422285
[19] DOI: 10.1007/s10107-004-0552-5 · Zbl 1079.90102 · doi:10.1007/s10107-004-0552-5
[20] DOI: 10.1007/s10107-007-0149-x · Zbl 1191.90038 · doi:10.1007/s10107-007-0149-x
[21] DOI: 10.1007/s10107-012-0629-5 · Zbl 1287.90067 · doi:10.1007/s10107-012-0629-5
[22] DOI: 10.1007/s10107-014-0790-0 · Zbl 1327.90216 · doi:10.1007/s10107-014-0790-0
[23] DOI: 10.1007/s10957-014-0677-5 · Zbl 1330.90078 · doi:10.1007/s10957-014-0677-5
[24] DOI: 10.1007/s10107-010-0394-2 · Zbl 1207.65084 · doi:10.1007/s10107-010-0394-2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.