We develop a general formalism for computing high quality, low-cost solutions to nonconvex combinatorial optimization problems expressible as distributed interacting local constraints. For problems of this type, generalized deterministic annealing (GDA) avoids the performance-related sacrifices of current techniques. GDA exploits the localized structure of such problems by assigning K-state neurons to each optimization variable. The neuron values correspond to the probability densities of K-state local Markov chains and may be updated serially or in parallel; the Markov model is derived from the Markov model of simulated annealing (SA), although it is greatly simplified. Theorems are presented that firmly establish the convergence properties of GDA, as well as supplying practical guidelines for selecting the initial and final temperatures in the annealing process. A benchmark image enhancement application is provided where the performance of GDA is compared to other optimization methods. The empirical data taken in conjunction with the formal analytical results suggest that GDA enjoys significant performance advantages relative to current methods for combinatorial optimization.