The Analysis Of Semidefinite Programming’S Application In Combinatorial Optimization

Semidefinite programming is an extension of linear programming,with vector variables replaced by matrix variables and non-negativity elementwise replaced by positive semidefiniteness. SDP is widely attentioned and make more and more scholars put to come in, mainly from two aspects. One is semidefinite programming has a good application in a wide range of application, such as in combinatorial optimization, statistics, structural design, electronics engineering (filter design and mobile communications) and other fields. The second is the interior point algorithm of linear programming successful promotion on the semidefinite programming, And with the maturing of research, the performance of interior point algorithm of semidefinite programming for semidefinite programming research has important theoretical significance and application value which is also more and more good, and it has been provened that interior point algorithm is reliable and effective algorithm to proposed to solve the small and medium-sized.In recent years semidefinite programming, especially the linear semidefinite programming has been widely research in the field of algorithm.It set a polynomial time approximation algorithm which have good approximation performance and provides a new train of thought for some NP-hard problem. I have setted a polynomial time approximation algorithm by application SDP algorithm with combinatorial optimization of random ideal for vertex cover problem and annular gene permutation problem.In the thesis, first of all, this paper summarizes the content of semidefinite programming, the basic definition and the formula are brieily introduced, and according to the domain of semidefinite programming function, it can be divided into the real semidefinite programming SDP and the plural the CSDP semidefinite programming.I have demonstrateed the SDP and the CSDP can mutual transformation and equivalence:Under the guidance of Mr Zhu. we have applied SDP algorithm with combinatorial optimization of random ideal for vertex cover problem and its approximation performance is2; the CSDP thought to design a polynomial approximation algorithm for annular gene permutation problem, and its approximation performance is (4+π)/8,which is the best approximation algorithm for this problem so far. Finally we used matlab to realization of the algorithm by programming.In conclusion, the good characteristics of semidefinite programming random algorithm in the field of combinatorial optimization not only be more and more attention, but also attract more scholars to study this field.