Analysis Of Complexity Of Primal-dual Interior-point Algorithms For Semidefinite Optimization

In the development of mathematical programming, interior-point method is one of the effective methods to solve linear optimization problems. Owing to semidefinite optimization is widely used in combinatorial optimization, sensor network localization, structural design, and electrical engineering and so on. The method of solving semidefinite optimization is greatly important. Similarly, interior-point method is also suitable for solving semidefinite optimization problems. Our main research is primal-dual interior-point method for semidefinite optimization in this paper.In primal-dual interior-point method, kernel functions play an important role in defining new research directions. The core task of design primal-dual interior-point method is constructing a good kernel function. We propose two new kernel functions in this paper, research their properties, and design primal-dual interior-point method for semidefinite optimization based on this two kernel functions. We analyze the iterative process and polynomial time complexity of the primal-dual interior-point method for semidefinite optimization and calculate the iteration bounds for large-update methods and small-update methods, the results can achieve the best known theory bounds until now. Because of the design process is similar to linear programming, we main research primal-dual interior-point method for semidefinite optimization in this paper.We also research primal-dual interior-point method for linear optimization based on the two kernel functions of this paper. Because of the primal-dual interior-point method for linear optimization and the primal-dual interior-point method for semidefinite optimization are similar in properties and complexity of the algorithm, and the results are same. So we only expound primal-dual interior-point method for semidefinite optimization in this paper.