Study On Full-Newton Step Interior-point Algorithms Based On Kernel Functions For Conic Programming

It is generally agreed that primal-dual interior-point methods(IPMs)are one of the most efficient methods for solving linear optimization(LO)problems.Until 2001 primal-dual IPMs all have used the Newton direction as the search direction;this direction is closely related to the well-known primal-dual logarithmic barrier function.By replacing the logarithmic barrier function with a new kernel barrier function,one can obtain a new search direction and design a new interior-point algorithm based on the kernel function.The introduced property of exponential convexity of the kernel function for designing the large-update algorithm has played a crucial role in greatly simplified the analysis of IPMs.Motivated by this trend,we use the property of exponential convexity to analyze the full-Newton step feasible IPM.Later,we propose the full-Newton step infeasible interior-point algorithm for LO,then we extend the method to semidefinite optimization(SDO).The thesis devotes to designing new algorithms and studying complexities of the algorithms.Firstly,we propose a full-Newton step interior-point algorithm for LO by a finite barrier kernel function.We not only use the kernel function to determine the search direction but also apply the property of exponential convexity of the kernel function to analyse the full-Newton step interior-point algorithm.Moreover,the analysis is simplified and the complexity of the algorithm coincides with the currently best iteration bound for LO problems.Based on the general form of the kernel function for designing the large-update algorithm,we study the finite barrier kernel function and point out that the finite barrier kernel function can not use to design a large-update algorithm.In fact,these kinds of kernel functions have great advantages for designing the full-Newton step IPMs.For the purpose of getting good numerical results,we modify the search direction decided by the kernel function.Based on the classic wide neighborhood algorithm,we propose a new feasible IPM with a new wide neighborhood.Although the theoretical result of the algorithm is worse than the full-Newton step IPMs,the numerical results are reported to show the efficiency of the algorithm,which is just made up for the deficiency of full-Newton step IPMs.Secondly,by a similar kernel function,we present an infeasible interior-point algorithm for LO.Although the classic full-Newton infeasible interior-point methods(IIPMs)have the advantage in theoretical analysis,the classic full-Newton direction and proximity measure that adopted make the analysis be difficult.The new simple kernel function is used to construct the search direction and define a quadratic convergence neighborhood,moreover,the property of the kernel function especially the exponential convexity that greatly simplifies the analysis of full-Newton step IIPMs.The complexity of the algorithm coincides with the currently best iteration bound for LO problems.Then we extend our algorithm to SDO.The analysis of the classic SDO full-Newton step IIPMs is greatly simplified and the complexity of the algorithm coincides with the currently best iteration bound for IIPMs.Finally,by a much tighter upper bound for the proximity after the feasibility step,we design a new full-Newton step IIPM for SDO,the algorithm is used only one step as the feasible step and does not need any centering step.In fact,based on using the idea of elimination of the centering steps to simplified classical full-Newton step IIPMs,we modify the direction decided by the kernel function,which targets the new barrier update parameter center of the next pair of perturbed problems.Moreover,the analysis is simplified and the obtained complexity bound coincides with the currently best-known iteration bound for IIPMs,while the numerical tests demonstrated that the proximity measure reduced a lot and the proposed algorithm is more efficient than the classical full-Newton step IIPMs.