Projected subgradient methods with non-Euclidean distances for non-differentiable convex minimization and variational inequalities. (English) Zbl 1190.90118
Summary: We study subgradient projection type methods for solving non-differentiable convex minimization problems and monotone variational inequalities. The methods can be viewed as a natural extension of subgradient projection type algorithms, and are based on using non-Euclidean projection-like maps, which generate interior trajectories. The resulting algorithms are easy to implement and rely on a single projection per iteration. We prove several convergence results and establish rate of convergence estimates under various and mild assumptions on the problem’s data and the corresponding step-sizes.
MSC:
| 90C25 | Convex programming |
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 65K05 | Numerical mathematical programming methods |
References:
| [1] | Auslender A. (1973). Résolution numérique d’inégalites variationnelles. RAIRO 2: 67–72 · Zbl 0269.49048 |
| [2] | Auslender A. (1976). Optimisation, methodes numeriques. Masson, Paris · Zbl 0326.90057 |
| [3] | Auslender A., Teboulle M. (2006). Interior gradient and proximal methods for convex and conic optimization. SIAM J. Optim. 16: 697–725 · Zbl 1113.90118 · doi:10.1137/S1052623403427823 |
| [4] | Auslender A., Teboulle M. (2004). Interior gradient and Epsilon-subgradient methods for constrained convex minimization. Math. Oper. Res. 29: 1–26 · Zbl 1082.90087 · doi:10.1287/moor.1030.0062 |
| [5] | Auslender A., Teboulle M. (2005). Interior projection-like methods for monotone variational inequalities. Math. Program. Ser. A 104: 39–68 · Zbl 1159.90517 · doi:10.1007/s10107-004-0568-x |
| [6] | Auslender A., Guillet A., Gourgand M. (1974). Résolution numérique d’inégalites variationnelles. C.R.A.S serie A t.279: 341–344 · Zbl 0292.49022 |
| [7] | Beck A., Teboulle M. (2003). Mirror descent and nonlinear projected subgradient methods for convexoptimization. Oper. Res. Lett. 31: 167–175 · Zbl 1046.90057 · doi:10.1016/S0167-6377(02)00231-6 |
| [8] | Ben-Tal A., Margalit T., Nemirovsky A. (2001). The ordered subsets mirror descent optimization method with applications to tomography. SIAM J. Optim. 12: 79–108 · Zbl 0992.92034 · doi:10.1137/S1052623499354564 |
| [9] | Bruck R.E. (1977). On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space. J. Math. Anal. Appl. 61: 159–164 · Zbl 0423.47023 · doi:10.1016/0022-247X(77)90152-4 |
| [10] | Ermoliev Y.M., Ermoliev M. (1966). Methods of solution of nonlinear extremal problems. Cybernetics 2: 1–16 · Zbl 0512.90079 · doi:10.1007/BF01071403 |
| [11] | Konnov I.V. (2001). Combined relaxation methods for variational inequalities. Springer, Berlin · Zbl 0982.49009 |
| [12] | Korpelevich, G.M.: The extragradient method for finding saddle points and other problems. Ekonomie. i Mathe. Metody 12, 746–756 (1976) [english translation: Matecon 13 35–49 (1977)] · Zbl 0342.90044 |
| [13] | Nemirovsky A. (1981). Effective iterative methods for solving equations with monotone operators. MATECON 17: 344–359 |
| [14] | Nemirovsky, A.: Prox-method with rate of convergence O(1/k) for smooth variational inequalities and saddle point problems. Draft of 30/01/03 |
| [15] | Nemirovsky A., Yudin D. (1983). Problem complexity and method efficiency in optimization. Wiley, New York |
| [16] | Nurminski, E.A.: Bibliography on nondifferentiable optimization. In: Progress in nondifferentiable optimization, IIASA Collaborative Proceedings Series, CP-82-98 (1982) |
| [17] | Polyak B.T. (1969). Minimization of nonsmooth functionals. U.S.S.R. Comput. Math. Math. Phys. 18: 14–29 · Zbl 0395.65033 · doi:10.1016/0041-5553(78)90004-6 |
| [18] | Polyak B.T. (1987). Introduction to optimization. Optimization Software Inc., New York · Zbl 0708.90083 |
| [19] | Rockafellar R.T. (1970). Convex analysis. Princeton University Press, Princeton · Zbl 0193.18401 |
| [20] | Shor N.S. (1969). The generalized gradient descent. Trudy I Zimnei Skoly po Mat. Programmirovanyi 3: 578–585 |
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.
