Skip to main content
SpringerLink
Log in

Proximal minimization algorithm withD-functions

  • Contributed Papers
  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

The original proximal minimization algorithm employs quadratic additive terms in the objectives of the subproblems. In this paper, we replace these quadratic additive terms by more generalD-functions which resemble (but are not strictly) distance functions. We characterize the properties of suchD-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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Minty, G. J.,Monotone (Nonlinear) Operators in Hilbert Space, Duke Mathematics Journal, Vol. 29, pp. 341–346, 1962.

    Google Scholar 

  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.

    Google Scholar 

  3. Rockafellar, R. T.,Monotone Operators and the Proximal Point Algorithm, SIAM Journal on Control and Optimization, Vol. 14, pp. 877–898, 1976.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  8. Censor, Y., andSegman, J.,On Block-Iterative Entropy Maximization, Journal of Information and Optimization Sciences, Vol. 8, pp. 275–291, 1987.

    Google Scholar 

  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.

    Google Scholar 

  10. Lent, A., andCensor, Y.,The Primal-Dual Algorithm as a Constraint-Set Manipulation Device, Mathematical Programming, Vol. 50, pp. 343–357, 1991.

    Google Scholar 

  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.

    Google Scholar 

  13. Bertsekas, D. P.,Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, New York, 1982.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  18. Eckstein, J.,Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming, Mathematics of Operations Research (to appear).

  19. Eggermont, P. P. B.,Multiplicative Iterative Algorithms for Convex Programming, Linear Algebra and Its Applications, Vol. 130, pp. 25–42, 1990.

    Google Scholar 

  20. Shepp, L. A., andVardi, Y.,Maximum Likelihood Reconstruction in Emission Tomography, IEEE Transactions on Medical Imaging, Vol. MI-1, pp. 113–122, 1982.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  23. Auslender, A.,Optimisation: Méthodes Numériques, Masson, Paris, France, 1976.

    Google Scholar 

  24. Zenios, S. A., andCensor, Y.,Parallel Computing with Block-Iterative Image Reconstruction Algorithms, Applied Numerical Mathematics, Vol. 7, pp. 399–415, 1991.

    Google Scholar 

  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.

    Google Scholar 

  26. Powell, M. J. D.,An Algorithm for Maximizing Entropy Subject to Simple Bounds, Mathematical Programming, Vol. 42, pp. 171–180, 1988.

    Google Scholar 

  27. Fang, S. C., andRajasekera, R. J.,Quadratically Constrained Minimum Cross-Entropy Analysis, Mathematical Programming, Vol. 44, pp. 85–96, 1989.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Haifa, 31905, Mt. Carmel, Haifa, Israel

    Y. Censor (Professor of Mathematics and Computer Science)

  2. Wharton School, University of Pennsylvania, 19104-6366, Philadelphia, Pennsylvania

    S. A. Zenios (Associate Professor of Decision Sciences)

Authors
  1. Y. Censor
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. A. Zenios
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by O. L. Mangasarian

The work of the first author was supported by NSF Grant CCR-8811135 and NIH Grant HL-28438, while visiting the Decision Sciences Department of the Wharton School and the Medical Image Processing Group at the Department of Radiology, both at the University of Pennsylvania, Philadelphia, Pennsylvania. The work of the second author was supported by NSF Grant CCR-91-04042 and AFOSR Grant 91-0168.

The authors received valuable comments on the December 1989 and June 1990 versions of this paper, which led to considerable improvements of the results and their presentation. For this, they are indebted to D. Bertsekas, A. De Pierro, J. Eckstein, P. Eggermont, A. Iusem, M. Ferris, M. Teboulle, and three anonymous referees.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Censor, Y., Zenios, S.A. Proximal minimization algorithm withD-functions. J Optim Theory Appl 73, 451–464 (1992). https://doi.org/10.1007/BF00940051

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00940051

Key Words

Search

Navigation