×

Mirror descent and nonlinear projected subgradient methods for convex optimization. (English) Zbl 1046.90057

Summary: The mirror descent algorithm (MDA) was introduced by Nemirovsky and Yudin for solving convex optimization problems. This method exhibits an efficiency estimate that is mildly dependent in the decision variables dimension, and thus suitable for solving very large scale optimization problems. We present a new derivation and analysis of this algorithm. We show that the MDA can be viewed as a nonlinear projected-subgradient type method, derived from using a general distance-like function instead of the usual Euclidean squared distance. Within this interpretation, we derive in a simple way convergence and efficiency estimates. We then propose an Entropic mirror descent algorithm for convex minimization over the unit simplex, with a global efficiency estimate proven to be mildly dependent in the dimension of the problem.

MSC:

90C25 Convex programming
90C52 Methods of reduced gradient type
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ben-Tal, A.; Margalit, T.; Nemirovski, A., The ordered subsets mirror descent optimization method with applications to tomography, SIAM J. optim., 12, 79-108, (2001) · Zbl 0992.92034
[2] Bertsekas, D., Nonlinear programming, (1999), Athena Scientific Belmont, MA
[3] Bregman, L.M., A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming, USSR computational mathematics and mathematical physics, 7, 200-217, (1967) · Zbl 0186.23807
[4] Censor, Y.; Lent, A., An iterative row-action method for interval convex programming, J. optim. theory appl., 34, 3, 321-353, (1981) · Zbl 0431.49042
[5] Chen, G.; Teboulle, M., Convergence analysis of a proximal-like minimization algorithm using Bregman functions, SIAM J. optim., 3, 538-543, (1993) · Zbl 0808.90103
[6] Doljanski, M.; Teboulle, M., An interior proximal algorithm and the exponential multiplier method for semi-definite programming, SIAM J. optim., 9, 1-13, (1998)
[7] Kemperman, J.H.B., On the optimum rate of transmitting information, Ann. math. statist., 40, 2156-2177, (1969) · Zbl 0287.94021
[8] Kiwiel, K.C., Proximal minimization methods with generalized Bregman functions, SIAM J. control optim., 35, 1142-1168, (1997) · Zbl 0890.65061
[9] Nedic, A.; Bertsekas, D., Incremental subgradient methods for nondifferentiable optimization, SIAM J. optim., 12, 109-138, (2001) · Zbl 0991.90099
[10] Nemirovski, A.; Yudin, D., Problem complexity and method efficiency in optimization, (1983), Wiley New York
[11] Rockafellar, R.T., Convex analysis, (1970), Princeton University Press Princeton, NJ · Zbl 0229.90020
[12] Rockafellar, R.T., Monotone operators and the proximal point algorithm, SIAM J. control optim., 14, 877-898, (1976) · Zbl 0358.90053
[13] Rockafellar, R.T.; Wets, R.J.B, Variational analysis, (1998), Springer New York
[14] Teboulle, M., Entropic proximal mappings with application to nonlinear programming, Math. oper. res., 17, 670-690, (1992) · Zbl 0766.90071
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.