×
Solodov, M. V.

On approximations with finite precision in bundle methods for nonsmooth optimization. (English) Zbl 1094.90046

J. Optimization Theory Appl. 119, No. 1, 151-165 (2003).
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?

Cited in 25 Documents

MSC:

90C30 Nonlinear programming
49J52 Nonsmooth analysis

Keywords:

Nonsmooth optimization; convex optimization; bundle methods; stability analysis; perturbations
PDF BibTeX XML Cite
\textit{M. V. Solodov}, J. Optim. Theory Appl. 119, No. 1, 151--165 (2003; Zbl 1094.90046)
Full Text: DOI

References:

[1] Kiwiel, K. C., Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics, Springer Verlag, Berlin, Germany, Vol. 1133, 1985. · Zbl 0561.90059
[2] Hiriart-Urruty, J. B., and LemarÉchal, C., Convex Analysis and Minimization Algorithms, Springer Verlag, Berlin, Germany, 1993. · Zbl 0795.49001
[3] Bonnans, J. F., Gilbert, J. C., LemarÉchal, C., and SagastizÁbal, C. A., Optimisation Numérique: Aspects Théoriques et Pratiques, Springer Verlag, Berlin, Germany, 1997.
[4] Bertsekas, D. P., and Tsitsiklis, J. N., Parallel and Distributed Computation, Prentice-Hall, Englewood Cliffs, New Jersey, 1989. · Zbl 0743.65107
[5] LemarÉchal, C., Lagrangian Decomposition and Nonsmooth Optimization: Bundle Algorithm, Prox Iteration, Augmented Lagrangian, in Nonsmooth Optimization: Methods and Applications, Edited by F. Giannessi, Gordon and Breach, Philadelphia, Pennsylvania, pp. 201-216, 1992. · Zbl 1050.90553
[6] Bertsekas, D. P., Nonlinear Programming, Athena Scientific, Belmont, Massachusetts, 1995.
[7] Solodov, M. V., Convergence Analysis of Perturbed Feasible Descent Methods, Journal of Optimization Theory and Applications, Vol. 93, pp. 337-353, 1997. · Zbl 0899.90149
[8] Solodov, M. V., and Zavriev, S. K., Error Stability Properties of Generalized Gradient-Type Algorithms, Journal of Optimization Theory and Applications, Vol. 98, pp. 663-680, 1998. · Zbl 0913.90245
[9] Kiwiel, K. C., Approximations in Proximal Bundle Methods and Decomposition of Convex Programs, Journal of Optimization Theory and Applications, Vol. 84, pp. 529-548, 1995. · Zbl 0824.90110
[10] HintermÜller, M., A Proximal Bundle Method Based on Approximate Subgradients, Computational Optimization and Applications, Vol. 20, pp. 245-266, 2001. · Zbl 1054.90053
[11] Miller, S. A., An Inexact Bundle Method for Solving Large Structured Linear Matrix Inequalities, PhD Thesis, University of California, Santa Barbara, California, 2001.
[12] Kiwiel, K. C., A Method for Solving Certain Quadratic Programming Problems Arising in Nonsmooth Optimization, IMA Journal of Numerical Analysis, Vol. 6, pp. 137-152, 1986. · Zbl 0603.65041
[13] Kiwiel, K. C., Proximity Control in Bundle Methods for Convex Nondifferentiable Minimization, Mathematical Programming, Vol. 46, pp. 105-122, 1990. · Zbl 0697.90060
[14] Schramm, H., and Zowe, J., A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results, SIAM Journal on Optimization, Vol. 2, pp. 121-152, 1992. · Zbl 0761.90090
[15] Bonnans, J. F., Gilbert, J. C., LemarÉchal, C., and SagastizÁbal, C., A Family of Variable-Metric Proximal-Point Methods, Mathematical Programming, Vol. 68, pp. 15-47, 1995. · Zbl 0832.90102
[16] LemarÉchal, C., and SagastizÁbal, C., An Approach to Variable-Metric Bundle Methods, System Modelling and Optimization, Lecture Notes in Control and Information Sciences, Edited by J. Henry, and J. P. Yvon, Springer, Berlin, Germany, Vol. 197, pp. 144-162, 1994. · Zbl 0811.90085
[17] Mifflin, R., A Quasi-Second-Order Proximal Bundle Algorithm, Mathematical Programming, Vol. 73, pp. 51-72, 1996.
[18] LemarÉchal, C., and SagastizÁbal, C., Variable-Metric Bundle Methods: From Conceptual to Implementable Forms, Mathematical Programming, Vol. 76, pp. 393-410, 1997. · Zbl 0872.90072
[19] Chen, X., and Fukushima, M., Proximal Quasi-Newton Methods for Nondifferentiable Convex Optimization, Mathematical Programming, Vol. 85, pp. 313-334, 1999. · Zbl 0946.90111
[20] LukŠan, L., and VlcŠek, J., Globally Convergent Variable-Metric Method for Convex Nonsmooth Unconstrained Optimization, Journal of Optimization Theory and Applications, Vol. 102, pp. 593-613, 1999. · Zbl 0955.90102
[21] Mangasarian, O. L., Nonlinear Programming, McGraw-Hill, New York, New York, 1969.
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.