Advanced Search

Query:

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

Format:

Display: entries per page entries

Zbl 0845.90099
Iusem, Alfredo N.; Teboulle, Marc
Convergence rate analysis of nonquadratic proximal methods for convex and linear programming. (English)
[J] Math. Oper. Res. 20, No.3, 657-677 (1995). ISSN 1526-5471; ISSN 0364-765X/e

Summary: The $\varphi$-divergence proximal method is an extension of the proximal minimization algorithm, where the usual quadratic proximal term is substituted by a class of convex statistical distances, called $\varphi$-divergences. We study the convergence rate of this nonquadratic proximal method for convex and particularly linear programming. We identify a class of $\varphi$-divergences for which superlinear convergence is attained both for optimization problems with strongly convex objectives at the optimum and linear programming problems, when the regularization parameters tend to zero. We prove also that with regularization parameters bounded away from zero, convergence is at least linear for a wider class of $\varphi$-divergences, when the method is applied to the same kinds of problems. We further analyze the associated class of augmented Lagrangian methods for convex programming with nonquadratic penalty terms, and prove convergence of the dual generated by these methods for linear programming problems under a weak nondegeneracy assumption.

MSC 2000:: *90C25 Convex programming
90C05 Linear programming
90C30 Nonlinear programming

Keywords: $\varphi$-divergence proximal method; convergence rate; superlinear convergence; augmented Lagrangian methods

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]