Research On Wide Neighborhood Interior-Point Algorithms For Linear Programming

The wide neighborhood interior-point method is an effective method for solving linear programming.Among them,Ai-Zhang’s wide neighborhood and Ai-Zhang’s method proposed by Wenbao Ai and Shuzhong Zhang have been studied in depth for their theoretical superiority and computational effectiveness.In this thesis,several types of wide neighborhood interior-point algorithms for linear programming are proposed based on Ai-Zhang’s wide neighborhood and Ai-Zhang’s method.This thesis focuses on the iteration complexity analysis of the proposed algorithms based on the second-order corrector technique.The proposed algorithms are demonstrated to have the best iteration complexity.Besides,the feasibility and effectiveness of the proposed algorithms are verified via numerical tests.The main contributions of this thesis include the following three aspects.First,this thesis proposes a wide neighborhood interior-point algorithm based on step-truncated technique.The proposed algorithm improves the second-order corrector wide neighborhood interior-point algorithm proposed by Liu et al.The step-truncated technique truncates the step size as one when the step size is greater than one.Then,the duality gap is minimized by decreasing the center parameter until the new iterate reaches the boundary of the Ai-Zhang’s wide neighborhood.The proposed algorithm is proved to be quadratically convergent in the nondegenerate case.The numerical results on large-scale problems show that the step-truncated technique can speed up the convergence rate of the algorithm under the requirement of high precision.Second,two classes of interior-point algorithms based on classical kernel functions and Ai-Zhang’s wide neighborhood are explored.Among them,the first class of algorithms is obtained by generalizing the Kheirfam-Haghighi’s algorithm.To further improve the computational efficiency of the first class of algorithms,the corresponding second-order corrector algorithms are obtained by adding the second-order corrector directions derived from the negative search directions.The explored two classes of algorithms are proved to have the best iteration complexity via respectively constructing a unified iteration complexity analysis framework.The numerical results show the feasibility and effectiveness of the explored two classes of algorithms.Third,two classes of wide neighborhood interior-point algorithms based on the algebraic equivalent transformation technique are explored.The two classes of algorithms are obtained by generalizing the Darvay-Takacs’s algorithm based on the square root function and its corresponding second-order corrector algorithm,respectively.The explored two classes of algorithms are proved to have the best iteration complexity via respectively constructing a unified iteration complexity analysis framework.Numerical results demonstrate the feasibility of the explored two classes of algorithms.