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

Siqi  Li; Weiyi Qian

doi:10.3934/naco.2015.5.37

Article Contents

2015, Volume 5, Issue 1: 37-46. Doi: 10.3934/naco.2015.5.37

This issue Previous Article On the global convergence of a parameter-adjusting Levenberg-Marquardt method Next Article Optimality of piecewise thermal conductivity in a snow-ice thermodynamic system

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

Siqi Li^1, and
Weiyi Qian^1,

1.
College of Mathematics and Physics, Bohai University, Jinzhou, MO 121000

Received: December 31, 2014

Revised: February 28, 2015

Published: February 2015

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C05, 90C51.

Citation:

Related Papers

Cited by

References

[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.