Skip to main content
SpringerLink
Log in

Alternating Minimization as Sequential Unconstrained Minimization: A Survey

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

Abstract

Sequential unconstrained minimization is a general iterative method for minimizing a function over a given set. At each step of the iteration we minimize the sum of the objective function and an auxiliary function. The aim is to select the auxiliary functions so that, at least, we get convergence in function value to the constrained minimum. The SUMMA is a broad class of these methods for which such convergence holds. Included in the SUMMA class are the barrier-function methods, entropic and other proximal minimization algorithms, the simultaneous multiplicative algebraic reconstruction technique, and, after some reformulation, penalty-function methods. The alternating minimization method of Csiszár and Tusnády also falls within the SUMMA class, whenever their five-point property holds. Therefore, the expectation maximization maximum likelihood algorithm for the Poisson case is also in the SUMMA class.

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. Csiszár, I., Tusnády, G.: Information geometry and alternating minimization procedures. Stat. Decis. Suppl. 1, 205–237 (1984)

    Google Scholar 

  2. Rockmore, A., Macovski, A.: A maximum likelihood approach to emission image reconstruction from projections. IEEE Trans. Nucl. Sci. NS-23, 1428–1432 (1976)

    Article  Google Scholar 

  3. Shepp, L., Vardi, Y.: Maximum likelihood reconstruction for emission tomography. IEEE Trans. Med. Imaging MI-1, 113–122 (1982)

    Article  Google Scholar 

  4. Lange, K., Carson, R.: EM reconstruction algorithms for emission and transmission tomography. J. Comput. Assist. Tomogr. 8, 306–316 (1984)

    Google Scholar 

  5. Vardi, Y., Shepp, L.A., Kaufman, L.: A statistical model for positron emission tomography. J. Am. Stat. Assoc. 80, 8–20 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  6. Lange, K., Bahn, M., Little, R.: A theoretical study of some maximum likelihood algorithms for emission and transmission tomography. IEEE Trans. Med. Imaging MI-6(2), 106–114 (1987)

    Article  Google Scholar 

  7. Byrne, C.: Iterative image reconstruction algorithms based on cross-entropy minimization. IEEE Trans. Image Process. 2, 96–103 (1993)

    Article  Google Scholar 

  8. Byrne, C.: Erratum and addendum to ‘Iterative image reconstruction algorithms based on cross-entropy minimization’. IEEE Trans. Image Process. 4, 225–226 (1995)

    Google Scholar 

  9. Darroch, J., Ratcliff, D.: Generalized iterative scaling for log-linear models. Ann. Math. Stat. 43, 1470–1480 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  10. Schmidlin, P.: Iterative separation of sections in tomographic scintigrams. Nucl. Med. 9(1), 1–16 (1972)

    Google Scholar 

  11. Byrne, C.: Iterative reconstruction algorithms based on cross-entropy minimization. In: Levinson, S.E., Shepp, L. (eds.) Image Models (and their Speech Model Cousins). IMA Volumes in Mathematics and Its Applications, vol. 80, pp. 1–11. Springer, New York (1996)

    Chapter  Google Scholar 

  12. Fiacco, A., McCormick, G.: Nonlinear Programming: Sequential Unconstrained Minimization Techniques. SIAM Classics in Mathematics. SIAM, Philadelphia (1990)

    Book  MATH  Google Scholar 

  13. Byrne, C.: Sequential unconstrained minimization algorithms for constrained optimization. Inverse Probl. 24(1), 015013 (2008)

    Article  MathSciNet  Google Scholar 

  14. Teboulle, M.: Entropic proximal mappings with applications to nonlinear programming. Math. Oper. Res. 17(3), 670–690 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  15. Censor, Y., Zenios, S.A.: Proximal minimization algorithm with D-functions. J. Optim. Theory Appl. 73(3), 451–464 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  16. Censor, Y., Zenios, S.A.: Parallel Optimization: Theory, Algorithms and Applications. Oxford University Press, New York (1997)

    MATH  Google Scholar 

  17. Bauschke, H., Combettes, P., Noll, D.: Joint minimization with alternating Bregman proximity operators. Pac. J. Optim. 2, 401–424 (2006)

    MathSciNet  MATH  Google Scholar 

  18. Kullback, S., Leibler, R.: On information and sufficiency. Ann. Math. Stat. 22, 79–86 (1951)

    Article  MathSciNet  MATH  Google Scholar 

  19. Dempster, A.P., Laird, N.M., Rubin, D.B.: Maximum likelihood from incomplete data via the EM algorithm. J. R. Stat. Soc. B 37, 1–38 (1977)

    MathSciNet  Google Scholar 

  20. McLachlan, G.J., Krishnan, T.: The EM Algorithm and Extensions. Wiley, New York (1997)

    MATH  Google Scholar 

  21. 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 Comput. Math. Math. Phys. 7, 200–217 (1967)

    Article  Google Scholar 

  22. Butnariu, D., Byrne, C., Censor, Y.: Redundant axioms in the definition of Bregman functions. J. Convex Anal. 10, 245–254 (2003)

    MathSciNet  MATH  Google Scholar 

  23. Chen, G., Teboulle, M.: Convergence analysis of a proximal-like minimization algorithm using Bregman functions. SIAM J. Optim. 3, 538–543 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  24. Bauschke, H., Borwein, J.: Joint and separate convexity of the Bregman distance. In: Butnariu, D., Censor, Y., Reich, S. (eds.) Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications. Studies in Computational Mathematics, vol. 8, pp. 23–36. Elsevier, Amsterdam (2001)

    Chapter  Google Scholar 

  25. Eggermont, P., LaRiccia, V.: Maximum Penalized Likelihood Estimation. Density Estimation, vol. I. Springer, New York (2001)

    MATH  Google Scholar 

  26. Byrne, C., Censor, Y.: Proximity function minimization using multiple Bregman projections, with applications to split feasibility and Kullback–Leibler distance minimization. Ann. Oper. Res. 105, 77–98 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  27. Censor, Y., Elfving, T.: A multi-projection algorithm using Bregman projections in a product space. Numer. Algorithms 8, 221–239 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  28. Bauschke, H., Combettes, P.: Iterating Bregman retractions. SIAM J. Optim. 13, 1159–1173 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  29. Byrne, C., Eggermont, P.: EM Algorithms (2012) in preparation

  30. Byrne, C.: Bregman-Legendre multi-distance projection algorithms for convex feasibility and optimization. In: Butnariu, D., Censor, Y., Reich, S. (eds.) Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications. Studies in Computational Mathematics, vol. 8, pp. 87–100. Elsevier, Amsterdam (2001)

    Chapter  Google Scholar 

Download references

Acknowledgements

I wish to thank Professor Heinz Bauschke for calling to my attention the article [17], and the anonymous reviewers for helpful suggestions.

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, University of Massachusetts Lowell, Lowell, MA, 01854, USA

    Charles L. Byrne

Authors
  1. Charles L. Byrne
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Charles L. Byrne.

Additional information

Communicated by Marc Teboulle.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Byrne, C.L. Alternating Minimization as Sequential Unconstrained Minimization: A Survey. J Optim Theory Appl 156, 554–566 (2013). https://doi.org/10.1007/s10957-012-0134-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-012-0134-2

Keywords

Search

Navigation