Semidefinite Programming And Its Applications

Semidefinite programming is an extension of linear programming. In recentyears, the theory and algorithm for semidefinite programming have developed greatly,and its most important applications are found in combinatorial optimization, systemengineering and electrical engineering. Semidefinite programming is a new andimportant research field in mathematical programming. In the paper, we firstly summarize the theory, algorithm, application and recentresearch of semidefinite programming, then, introduce our some work in algorithmand application. For detail, we conclude them as follows: 1. A nonlinear programming algorithm was proposed for the Max-bisectionproblem, and the convergent result was given. The experiments show that theperformance of our method is similar to the Ye-0.699 algorithm, which is the bestapproximate algorithm in polynomial time. But our method can effectively solve theMax-bisection problem with a large scale. 2. An equivalent integral programming model and a new semidefiniteprogramming relaxation for the Max-bisection problem are given. Then, we solve therelaxation with a projected gradient algorithm. Coupled with the randomized method,an approximate solution of the Max-bisection problem is obtained. The numericalresults show that the method can effectively solve the Max-bisection problem. At last,the projected gradient algorithm is used in the CDMA maximum likelihood multiuserdetection. The experiment shows that the method is a good method for the CDMA. 3. A strength relaxation of semidefinite programming for standard quadraticoptimization problems is given. The relaxation is transformed to a semi-indefiniteprogramming. A linear programming cutting plane algorithm is proposed. The theoryand experiment prove that the algorithm is effective.