Algorithms And Applications Of Semidefinite Programming

Semidefinite programming is an extension of linear programming, with non-negativity vector variables replaced by semidefinite positive matrix variables. In recent years, the theory and algorithm for semidefinite programming have developed greatly, and it's most important applications are found in system theory, control theory, combinatorial optimization and mobile cotmnunication. Semidefinite programming is a new and important research field in mathematical programming.This paper consists of three parts as follows,1.A nonsmooth convex programming is relaxed to a smooth convex programming by using a cutting-plane, which is constructed by subgradient. An algorithm based on the cutting-plane is presented. In this way, a cutting plane algorithm and it's convergence for semide?nite programming are provided. As applications of succeeding, numerical examples of Max-cut and Vertex cover are given.2.A new kind of algorithm, based on the Golden section method for semidefinite programming is presented, which makes full use of the structure of the feasiable region. The algorithm is simple and has small amount of operation. As an application of succeeding, a numerical example of Max-cut is given.3.Several semidefinite relaxation detection strategies of the CDMA maximum likelihood multiuser detection are investigated. Rounding, coordinate descent, cutting plane and branch and bound based on quadratic programming algorithm are presented to get the suboptirnal solution. Combining numerical experiments, the advantages and the disadvantages of them are analyzed.