Advanced Search

Query:

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

Format:

Display: entries per page entries

Zbl 1094.90046
Solodov, M.V.
On approximations with finite precision in bundle methods for nonsmooth optimization. (English)
[J] J. Optimization Theory Appl. 119, No. 1, 151-165 (2003). ISSN 0022-3239; ISSN 1573-2878/e

Summary: We consider the proximal form of a bundle algorithm for minimizing a nonsmooth convex function, assuming that the function and subgradient values are evaluated approximately. We show how these approximations should be controlled in order to satisfy the desired optimality tolerance. For example, this is relevant in the context of Lagrangian relaxation, where obtaining exact information about the function and subgradient values involves solving exactly a certain optimization problem, which can be relatively costly (and as we show, in any case unnecessary). We show that approximation with some finite precision is sufficient in this setting and give an explicit characterization of this precision. Alternatively, our result can be viewed as a stability analysis of standard proximal bundle methods, as it answers the following question: for a given approximation error, what kind of approximate solution can be obtained and how does it depend on the magnitude of the perturbation?

MSC 2000:: *90C30 Nonlinear programming
49J52 Nonsmooth analysis (other weak concepts of optimality)

Keywords: Nonsmooth optimization; convex optimization; bundle methods; stability analysis; perturbations

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]