Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1046.90057
Beck, Amir; Teboulle, Marc
Mirror descent and nonlinear projected subgradient methods for convex optimization. (English)
[J] Oper. Res. Lett. 31, No. 3, 167-175 (2003). ISSN 0167-6377

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 2000:: *90C25 Convex programming
90C52 Methods of reduced gradient type

Keywords: Nonsmooth convex minimization; Projected subgradient methods; Nonlinear; projections; Mirror descent algorithms; Relative entropy; Complexity analysis; Global rate of; convergence

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]