Bivariate Entropy Function Method And Homotopy Method For Maximum Clique Problem

The maximum clique problem is one of the classic NP-complete problems from combinatorial optimization. Since the problem was proposed, it has been studied intensively and applied to many fields. Considering the complexity of the problem, most researches were focused on the approximation method and many achievements have been obtained. This thesis is also devoted to approximation method. The main contents are organized as follows:In chapter 1, some definitions and optimization models about the maximum clique problem are introduced. Then the feature of the problem and the siganificance of studing the problem are outlined. At the end of the chapter, some related studies are presented.In chapter 2, a algorithm named bivariate entropy function algorithm is proposed. The algorithm is based on quadratic optimization model with hypecube constraint. With the help of bivariate entropy function, a new model is obtained, which can be solved to approximate primal model. With regard to how to solve the new model, a decent direction is obtained then It's proved that if the initial point is the interior point of hypercube and steplength is confined to (0,1) when carrying out one dimension search following the direction mentioned above in order to generate next point, then any point generated by such iteration is interior point of feasible field. Moreover, at the end of this chapter, the proposed algorithm is proved to be convergent.In chapter 3, homotopy method based on replicator dynamics is introduced. Some basic properties of replicator dynamics and its application to maximum clique problem are presented. Then, a regularized quadratic optimization model in the form of homotopy is presented. The approximation of the primal quadratic optimization model can be obtained by solving the regularized one and adjusting the homotopy parameter.In chapter 4, numerical experiments are performed on the algorithms in the former two chapters. Some details in numerical experiment are also presented, such as how to carry out one dimension search, how to set some initial values and how to adjust homotopy parameter. Besides, the numerical results of this thesis and some classic method are presented in the form of table.