Research On Full-Newton Step Infeasible Interior Point Algorithm For Semidefinite Programming

Semidefinite programming?SDP?,as an extension of linear programming?LP?,has been widely used in many science and engineering fields,such as combinatorial optimization,control theory and pattern recognition.In recent years,many interior point methods for LP have been successfully extended to SDP,which attracts many scholars'attention.At present,the interior point method?IPM?is the most effective algorithm for SDP.According to the initial point is feasible or not,the interior point method can be divided into feasible interior point method?FIPM?and infeasible interior point method?IIPM?.The infeasible interior point algorithm with Full-Newton step has become a research hotspot,because it only uses Newton step in the iteration process,and does not require line search,which reduces computation cost of algorithm.The Full-Newton step infeasible interior point algorithm generally consists of two iterative processes:the feasibility step and the centering step.The feasibility steps serve to generate strictly feasible iterates for the new perturbed problem pair,and the iterates belong to the region of quadratic convergence of their center path.Taking the feasible point as the initial point of the centering step,after several iterations,it gets a feasible point of the next perturbed problem.In this thesis,based on the new feasible step search direction,a Full-Newton step infeasible interior point algorithm is proposed.Secondly,we improve the theoretical analysis of algorithm proposed by Wang et.al^[45],and simplify the analysis process of the algorithm.The main achievements are listed as follows:1.We present a new Full-Newton step infeasible interior point algorithm based on a special kernel function,which proposed by Liu and Sun^[35].The new algorithm uses the kernel function to replace the classical logarithmical barrier function,and then gets a new search direction.By using this search direction,the algorithm only performs one Full-Newton step without using the centering step in each iteration and can get the approximate optimal solution of the problem.Meanwhile,the iterative boundary of the algorithm coincides with the currently best iteration bounds for IIPM.2.Improving the theoretical analysis of the infeasible interior point algorithm proposed by Wang et al.^[45],and the theoretical analysis of algorithm adopted more simple and intuitive.The new theoretical analysis needs not to consider the infinite norm ofD_X^f _S but with its eigenvalue in the analysis process.Meanwhile,by introducing and scaling the suitable intermediate variables,it can obtain the iteration complexity of the algorithm.