Full-Newton Step Infeasible Interior-Point Algorithm For Conic Programming

This thesis focuses on designing and analyzing full-Newton step infeasibleinterior-point algorithm for conic programming problems, including linear pro-gramming and semi-definite programming.There exist many methods for solving the above two kinds of conic pro-gramming problems. In all of them, interior-point methods (IPMs) have beenconsidered as a class of e?cient algorithms. One may distinguish between fea-sible IPMs and infeasible IPMs (IIPMs). Feasible IPMs start with a strictlyfeasible interior point and maintain feasibility during the solution process. IIPMsstart with an arbitrary positive point, and feasibility is reached as optimality isapproached.In 2006, C. Roos designed an e?cient infeasible interior-point algorithm withfull-Newton steps for linear programming. The algorithm decreases the dualitygap and the feasibility residuals at the same rate. Assuming that an optimalsolution exists, the algorithm has O n log n? complexity bound, which coincideswith the best-known bound for IIPMs. The algorithm constructs strictly feasibleiterates for a sequence of perturbations of the given problem and its dual problem.A special feature of the algorithm is that it uses only full-Newton steps.In this thesis, we take further research on the full-Newton step IIPM. Itcontains two parts, one is the simplified analysis for the algorithm and the otheris for designing the new algorithm. First, by using a classic proximity measure,we simplify the complexity analysis of the full-Newton step IIPM for linear pro-gramming, presented by C. Roos, see [SIAM J. Optim. 16(4):1110-1136, 2006].Beside, we extend the method to analyze the full-Newton step IIPM for semi-definite programming. Furthermore, we present a new full-Newton step IIPMfor solving linear programming based on a simple locally-kernel function. In ouralgorithm, the locally-kernel function is used to construct the search directionand to define a quadratic convergence neighborhood. Meanwhile, it is also used as a proximity function to measure the distance between the iterative points andthe central path. Then, we extend our algorithm to semi-definite programmingproblem. The complexity analysis shows that the full-Newton step IIPM basedon the simple locally-kernel function obtains the best complexity bound amongexisting literature.