Abstract
Let f : ℜs ↦ ℜ be a real-valued scalar field, and let x = (x1,…, xs)T ∈ ℜs be partitioned into t subsets of non-overlapping variables as x = (X1,…,Xt )T, with Xi ∈ ℜp 1, for i = 1,…, t, ∈t i=1pi = s Alternating optimization (AO) is an iterative procedure for minimizing (or maximizing) the function f(x) = f(X1,X2,…,Xt) jointly over all variables by alternating restricted minimizations over the individual subsets of variables X1,…,Xt. AO is the basis for the c-means clustering algorithms (t=2), many forms of vector quantization (t = 2, 3 and 4), and the expectation-maximization (EM) algorithm (t = 4) for normal mixture decomposition. First we review where and how AO fits into the overall optimization landscape. Then we discuss the important theoretical issues connected with the AO approach. Finally, we state (without proofs) two new theorems that give very general local and global convergence and rate of convergence results which hold for all partitionings of x.
Research supported by ONR Grant 00014-96-1-0642.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Lloyd, S.P. (1957). Least squares quantization of PCM, [originally an unpublished Bell Labs technical note], reprinted in IEEE Trans. IT, 28, March, 1982, 129–137.
Wolfe, J.H. (1970). Pattern clustering by multivariate mixture analysis, Multivariate Behavioral Research, v. 5, 329–350.
Bezdek, J.C. (1973). Fuzzy Mathematics for Pattern Classification, PhD Thesis, Cornell University, Ithaca, NY.
Bezdek, J.C., Coray, C., Gunderson, R. and Watson, J. (1981). Detection and Characterization of Cluster Substructure II. Fuzzy c-Varieties and Convex Combinations Thereof, SIAM J. Appl. Math., 40(2), 358–372.
Windham, M.P. (1985). Numerical classification of proximity data with assignment measures, Journal of Classification, v. 2, 157–172.
Dave, R.N. (1990). Fuzzy shell-clustering and applications to circle detection in digital images, International Journal of General Systems, v. 16, 343–355.
Hathaway, R.J. and Bezdek, J. C. (1993). Switching Regression Models and Fuzzy Clustering, IEEE Trans. Fuzzy Systems, 1(3), 195–204.
Krishnapuram, R. and J.M. Keller (1993). A possibilistic approach to clustering, IEEE Trans. on Fuzzy Systems, v. 1, 98–110.
Hathaway, R.J., and J.C. Bezdek (2001). Fuzzy c-means clustering of incomplete data, to appear, IEEE Trans. on Systems, Man and Cybernetics B.
Bezdek, J.C. and R.J. Hathaway (2002). Alternating optimization, parts 1 and 2, in preparation for IEEE Trans. on Systs., Man and Cybernetics.
Apostol, T.M. (1969). Calculus, Ginn Blaisdell, Waltham, MA.
Ortega, J.M. and W.C. Rheinboldt (1970). Iterative Solution of Nonlinear Equations in Several Variables. New York: Academic Press.
Gill, P.E., Murray, W. and Wright, M. H. (1981). Practical Optimization, Academic Press, NY.
Dennis, J.E., Jr., and R.B. Schnabel (1983). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs, NJ: Prentice-Hall.
Luenberger, D.G. (1969). Optimization by Vector Space Methods, Wiley, NY.
Luenberger, D.G. (1984). Linear and Nonlinear Programming. Second Edition, Reading, MA: Addison-Wesley.
Zangwill, W. (1969). Nonlinear Programming: A Unified Approach. Englewood Cliffs, NJ: Prentice-Hall.
Goldberg, D.E. (1989). Genetic algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA.
Fogle, D.B. (1995). Evolutionary Computation, IEEE Press, Piscataway, NJ.
Golden, R.M. (1996). Mathematical methods for Neural Network Analysis and Design, Bradford Books, MIT Press, Cambridge, MA.
Nguyen, H.T. and Sugeno, M. (eds.) (1997). Fuzzy Systems: Modeling and Control, Kluwer, Norwell, MA.
Hu, Y., and R.J. Hathaway (2001). On efficiency of optimization in fuzzy c-means, preprint.
Bezdek, J.C. and R.J. Hathaway (1992). Numerical convergence and interpretation of the fuzzy c-shells clustering algorithms, IEEE Trans. on Neural Networks, v. 3, 787–793.
Bezdek, J.C., Hathaway, R.J., Sabin, M.J., and W.T. Tucker (1987a). Convergence theory for fuzzy c-means: counterexamples and repairs, IEEE Trans. on Systems, Man and Cybernetics, SMC-17, 873–877.
Bezdek, J.C., Hathaway, R.J., Howard, R.E., Wilson, C.A., and M.P. Windham (1987b). Local convergence analysis of a grouped variable version of coordinate descent, Journal of Optimization Theory and Applications, v. 54, 471–477.
Hathaway, R.J. and J.C. Bezdek (1991). Grouped coordinate minimization using Newton’s method for inexact minimization in one vector coordinate, Journal of Optimization Theory and Applications, v. 71, 503–516.
Hathaway, R.J., Hu. Y.K., and J. C. Bezdek (2001). Local convergence analysis of trilevel alternating optimization, Neural, Parallel, and Scientific Computation, 9, 19–28.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bezdek, J.C., Hathaway, R.J. (2002). Some Notes on Alternating Optimization. In: Pal, N.R., Sugeno, M. (eds) Advances in Soft Computing — AFSS 2002. AFSS 2002. Lecture Notes in Computer Science(), vol 2275. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45631-7_39
Download citation
DOI: https://doi.org/10.1007/3-540-45631-7_39
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43150-3
Online ISBN: 978-3-540-45631-5
eBook Packages: Springer Book Archive