×

zbMATH — the first resource for mathematics

Proximal minimization algorithm with \(D\)-functions. (English) Zbl 0794.90058
Summary: The original proximal minimization algorithm employs quadratic additive terms in the objective of the subproblems. We replace these quadratic additive terms by more general \(D\)-functions which resemble (but are not strictly) distance functions. We characterize the properties of such \(D\)- functions which, when used in the proximal minimization algorithm, preserve its overall convergence. The quadratic case as well as an entropy-oriented proximal minimization algorithm are obtained as special cases.

MSC:
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Minty, G. J.,Monotone (Nonlinear) Operators in Hilbert Space, Duke Mathematics Journal, Vol. 29, pp. 341-346, 1962. · Zbl 0111.31202 · doi:10.1215/S0012-7094-62-02933-2
[2] Moreau, J. J.,Proximité et Dualité dans un Espace Hilbertien, Bulletin de la Société Mathématique de France, Vol. 93, pp. 273-299, 1965.
[3] Rockafellar, R. T.,Monotone Operators and the Proximal Point Algorithm, SIAM Journal on Control and Optimization, Vol. 14, pp. 877-898, 1976. · Zbl 0358.90053 · doi:10.1137/0314056
[4] Rockafellar, R. T.,Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming, Mathematics of Operations Research, Vol. 1, pp. 97-116, 1976. · Zbl 0402.90076 · doi:10.1287/moor.1.2.97
[5] Bregman, L. M.,The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming, USSR Computational Mathematics and Mathematical Physics, Vol. 7, pp. 200-217, 1967. · Zbl 0186.23807 · doi:10.1016/0041-5553(67)90040-7
[6] Censor, Y., andLent, A.,An Iterative Row-Action Method for Interval Convex Programming, Journal of Optimization Theory and Applications, Vol. 34, pp. 321-353, 1981. · Zbl 0431.49042 · doi:10.1007/BF00934676
[7] De Pierro, A. R., andIusem, A. N.,A Relaxed Version of Bregman’s Method for Convex Programming, Journal of Optimization Theory and Applications, Vol. 51, pp. 421-440, 1986. · Zbl 0581.90069 · doi:10.1007/BF00940283
[8] Censor, Y., andSegman, J.,On Block-Iterative Entropy Maximization, Journal of Information and Optimization Sciences, Vol. 8, pp. 275-291, 1987. · Zbl 0631.90087
[9] Censor, Y., De Pierro, A. R., Elfving, T., Herman, G. T., andIusem, A. N.,On Iterative Methods for Linearly Constrained Entropy Maximization, Numerical Analysis and Mathematical Modelling, Edited by A. Wakulicz, Banach Center Publications, PWN-Polish Scientific Publishers, Warsaw, Poland, Vol. 24, pp. 145-163, 1990.
[10] Lent, A., andCensor, Y.,The Primal-Dual Algorithm as a Constraint-Set Manipulation Device, Mathematical Programming, Vol. 50, pp. 343-357, 1991. · Zbl 0734.90066 · doi:10.1007/BF01594943
[11] Eriksson, J. R.,An Iterative Primal-Dual Algorithm for Linear Programming, Report LITH-MAT-R-1985-10, Department of Mathematics, Linköping University, Linköping, Sweden.
[12] Bertsekas, D. P., andTsitsiklis, J. N.,Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, New Jersey, 1989. · Zbl 0743.65107
[13] Bertsekas, D. P.,Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, New York, 1982. · Zbl 0572.90067
[14] Bertsekas, D. P., Private Communication, March 1990.
[15] Teboulle, M.,Entropic Proximal Mappings with Applications to Nonlinear Programming, Mathematics of Operations Research (to appear), also available as Technical Report, Department of Mathematics and Statistics, University of Maryland, Baltimore, Maryland, 1990.
[16] Chen, G., andTeboulle, M.,Convergence Analysis of Proximal-Like Minimization Algorithm Using Bregman Functions, Research Report 90-23, Department of Mathematics, University of Maryland at Baltimore County, Catonsville, Maryland, 1990.
[17] Eckstein, J.,Splitting Methods for Monotone Operators with Applications to Parallel Optimization, Technical Report CICS-TH-140, Center for Intelligent Control Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1989.
[18] Eckstein, J.,Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming, Mathematics of Operations Research (to appear). · Zbl 0807.47036
[19] Eggermont, P. P. B.,Multiplicative Iterative Algorithms for Convex Programming, Linear Algebra and Its Applications, Vol. 130, pp. 25-42, 1990. · Zbl 0715.65037 · doi:10.1016/0024-3795(90)90204-P
[20] Shepp, L. A., andVardi, Y.,Maximum Likelihood Reconstruction in Emission Tomography, IEEE Transactions on Medical Imaging, Vol. MI-1, pp. 113-122, 1982. · doi:10.1109/TMI.1982.4307558
[21] Tseng, P., andBertsekas, D. P.,On the Convergence of the Exponential Multiplier Method for Convex Programming, Technical Report LIDS-P-1995, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1990.
[22] Censor, Y., De Pierro, A. R., andIusem, A. N.,Optimization of Burg’s Entropy over Linear Constraints, Applied Numerical Mathematics, Vol. 7, pp. 151-165, 1991. · Zbl 0722.65032 · doi:10.1016/0168-9274(91)90059-9
[23] Auslender, A.,Optimisation: Méthodes Numériques, Masson, Paris, France, 1976.
[24] Zenios, S. A., andCensor, Y.,Parallel Computing with Block-Iterative Image Reconstruction Algorithms, Applied Numerical Mathematics, Vol. 7, pp. 399-415, 1991. · Zbl 0727.65118 · doi:10.1016/0168-9274(91)90010-W
[25] Zenios, S. A., andCensor, Y.,Massively Parallel Row-Action Algorithms for Some Nonlinear Transportation Problems, SIAM Journal on Optimization, Vol. 1, pp. 373-400, 1991. · Zbl 0754.90057 · doi:10.1137/0801024
[26] Powell, M. J. D.,An Algorithm for Maximizing Entropy Subject to Simple Bounds, Mathematical Programming, Vol. 42, pp. 171-180, 1988. · Zbl 0649.90086 · doi:10.1007/BF01589401
[27] Fang, S. C., andRajasekera, R. J.,Quadratically Constrained Minimum Cross-Entropy Analysis, Mathematical Programming, Vol. 44, pp. 85-96, 1989. · Zbl 0671.90071 · doi:10.1007/BF01587079
[28] Nielsen, S., andZenios, S. A.,Proximal Minimizations with D-Functions and the Massively Parallel Solutions of Linear Network Programs, Report 91-06-05, Decision Sciences Department, The Wharton School, University of Pennsylvania, Philadelphia, 1991.
[29] Nielsen, S., andZenios, S. A.,Solving Linear Stochastic Network Problems Using Massively Parallel Proximal Algorithms, Report 92-01-05, Decision Sciences Department, The Wharton School, University of Pennsylvania, Philadelphia, 1992.
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.