Article Contents
Article Contents

# Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization

• Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm. In this paper, a new kernel function which its barrier term is integral type is proposed. We study the properties of the new kernel function, and give a primal-dual interior-point algorithm for solving linear optimization based on the new kernel function. Polynomial complexity of algorithm is analyzed. The iteration bounds both for large-update and for small-update methods are obtained, respectively. The iteration bound for small-update method is the best known complexity bound.
Mathematics Subject Classification: Primary: 90C05, 90C51.

 Citation:

•  [1] Y. Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization, SIAM Journal on Optimization, 15 (2004), 101-128.doi: 10.1137/S1052623403423114. [2] Y. Q. Bai, J. Guo and C. Roos, A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms, Acta Mathematica Sinica English Series, 25 (2009), 2169-2178.doi: 10.1007/s10114-009-6457-8. [3] Y. Q. Bai and C. Roos, A polynomial-time algorithm for linear optimization based on a new simple kernel function, Optimization Methods and Software, 18 (2003), 631-646.doi: 10.1080/10556780310001639735. [4] Y. Q. Bai, M. El Ghami and C. Roos, A new efficient large-update primal-dual interior-point method based on a finite barrier, SIAM Journal on Optimization, 13 (2002), 766-782.doi: 10.1137/S1052623401398132. [5] Y. Q. Bai, C. Roos and M. El Ghami, A primal-dual interior-point method for linear optimization based on a new proximity function, Optimization Methods and Software, 17 (2002), 985-1008.doi: 10.1080/1055678021000090024. [6] N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395.doi: 10.1007/BF02579150. [7] Y. Nesterov and A. Nemirovskii, Interior-point polynomial methods in convex programming, SIAM, Philadelphia, 1994.doi: 10.1137/1.9781611970791. [8] J. M. Peng, C. Roos and T. Terlaky, A new class of polynomial primal-dual methods for linear and semidefinite programming, European Journal of Operational Research, 143 (2002), 234-256.doi: 10.1016/S0377-2217(02)00275-8. [9] J. Renegar, A polynomial time algorithm based on Newton's method for linear programming, Mathematical Programming, 40 (1988), 59-94.doi: 10.1007/BF01580724. [10] C. Roos and J. P. Vial, A polynomial method of approximate centers for linear programming, Mathematical Programming, 54 (1992), 295-305.doi: 10.1007/BF01586056.