Infeasible Interior Point Algorithm For Semidefinite Programming

Semidefinite Programming(SDP) is a generalization of Linear Programming(LP), its constraint is nonsmooth and convex, so SDP is a nonsmooth and convex optimization problem. In recent years, the theory and algorithms for SDP have developed greatly. It has various applications in combinatorial optimization, image processing, pattern recognition and other fields. SDP is an important research field in mathematical programming. In several methods for solving the problem of mathematical programming, the interior point algorithm has good practical performance and theoretical performance, and becomes a core algorithm of SDP.SDP algorithm consists of feasible algorithm and infeasible algorithm according to whether the constraint condition is feasible or not. This paper mainly studies the infeasible algorithm of SDP. An algorithm of low theoretical complexity has a bad practical performance, and an algorithm of good practical performance has high theoretical complexity in the interior point algorithm. In fact, we often want to keep good practical performance and reduce theoretical complexity. Then, this paper introduces two new interior point algorithms for the infeasible algorithm of SDP, our purpose is to achieve lower theoretical complexity and get the better practical performance. Work is as follows:1. We firstly summarize the development background of SDP, introduce basic concepts and theories, main algorithms and recent research of SDP.2. A homogeneous and infeasible interior point algorithm: We present a homogeneous infeasible interior point algorithm of SDP in a new wide neighborhood in order to achieve low iteration complexity and get the better experiement numerial results. Monotone complementarity problem(MCP) is the KKT condition of SDP. We can sovle MCP by constructing a homogeneous MCP model(HMCP) and presenting a new wide neighborhood. Then, we can derive the optimal solution of SDP. This algorithm is easy to determine whether SDP is feasible or not. When we choose the direction of NT, we can prove that iteration points is convergent in new wide neighborhood and the iteration complexity is (?)((?)logL) less than usual iteration complexity of SDP, where n is the dimension of SDP, L=Tr(X~0 S~0) ? with ? the required precision and( X~0, S~0) the initial point. The numerical experiment is provided, and we can prove this algorithm is better than other infeasible interior point algorithms in numerical experiment results.3. A new full-NT-step infeasible interior point algorithm: Full-NT-step algorithm consists of a feasibility step and several centrality steps, it has the advantage that no step lengths are needed, and the amount of calculation is reduced. New algorithm introduces a specific kernel function instead of the classic logarithmical barrier function and gets a feasibility step different from general algorithms. At the same time, a slightly wider neighborhood is introduced. A sharper quadratic convergence result is obtained, and the result of polynomial complexity coincides with the best known one for full-NT-step infeasible interior point algorithm.