Studies On The Entropic Regularization Method For The Maximum Clique Problem

The maximum clique problem is one of the classical NP-complete problems from combinatorial optimization. Ever science the problem was proposed, many research and applications have been done. But for the complexity, more researches are focused on the approximation method, in otlier words, heuristic, and get many results.The maximum clique problem has some equal descriptions, and the research methods differ on different models. The research of this paper is based on the continuous quadratic model which was proposed by Motzkin and Straus in 1965. The merit of this model is that it enable us use the tools form continuous field. But for the adjacent matrixes in this model are always degraded, the problems are ill-posed. So many techniques are used to release the ill-posness and get a series of results.What's important, the constraint condition in the model is expressed as a simplex, and this enable us use the information theory. As a result, the information theory method for the maximum clique—entropy function method and cross-entropy function method, and D-function regulanzation method are introduced here. In chapter 3, the entropy regularization method and cross-entropic regularization are introduced, and in chapter 4 the D-function regularization method is introduced. These two chapters are the main work of the paper. By introducing the foundation of the models, the analysis of the models and the algorithms design, we give an overall introduction of our methods, In the chapter 5, some simple comparisons the numerical experiments and simple analysis of the methods are given. Simple analysis shows that our two methods can release the ill-poseness. And comparing with other complex methods, we nearly get the same results, so the validity and the stability of our methods are shown. Thus they are worth further researching.