Research Of Semidefinite Programming And Its Application

Semidefinite programming (SDP) is an extension of linear programming. In recent years, the interior point method was extended to the filed of semidefinite programming, the theory and algorithm for SDP have developed greatly, and its numerous applications are found in combinatorial optimization, cybernetics, system engineering, the design of filters, clinical medicine and mobile communications. SDP is a very important research filed in mathematical programming.In this paper, we first summarize theory, algorithm, research state and significance of SDP. The main work includes the following three aspects.1. A quadratic programming method based on semidefinite programming is given, which can give a better bound than the semidefinite programming method. Based on the model, we use the Branch-and-Bound algorithm to solve this problem. Under certain conditions, we prove its effectiveness by numerical experiment and theory.2. Based on the Branch-and-Bound algorithm, we study the design of FIR filters and the max-bisection problem. Numerical results show that: Compared with the conventi- onal randomized method, the Branch-and-Bound can obtain a better suboptimal solution to the design of FIR digital filters with a certain scale.We can get a lower error rate. Numerical results for the small scale problems and the middle scale problems demonstrate that a better solution can be obtained by the algorithm, and the algorithm is an effective algorithm for the max-bisection problem with a middle scale.3. We study semidefinite programming problems for which an optimal solution can be calculated directly without using an iterative method. First we present three classes of directly solvable SDP problems. Then we study a new class of SDP problems with special constraints through the invertible changes of matrix.