The Study Of Smoothing Methods For Semidefinite Programming

Semidefinite programming (SDP) is an extension of linear programming. In recent years, the theory and algorithm for SDP have developed greatly, and its numerous applications are found in combinatorial optimization, system engineering and electrical engineering. SDP is a very important research field in mathematical programming.In this paper, we first summarize the theory, algorithm, research state and significance of SDP. Then, a non-interior smoothing method is proposed for solving the SDP problems. The main work includes the following three aspects:1. The equivalent smoothing equations of the optimal condition are obtained by exploiting the smoothing entropy function. Applying Newton's method to solve the equations, a smoothing method for the solution of SDP is derived. The feasibility and convergence of the algorithm are analyzed theoretically. Some numerical results are also included which indicate that the proposed method is efficient.2. By regarding the smoothing parameter of the smoothing entropy function as a independent variable, a new algorithm is proposed. The method is shown to be globally and locally superlinearly convergent under suitable assumptions. Numerical experiments show that the method is efficient.3. Through improving the update methods of iterative points and parameters, the number of solving linear equations is reduced and a new method for solving SDP problems is derived. Theoretical analysis and numerical results are included which show that the method is very promising and comparable to several correlative methods.