Volume 50, Number 4-5, October-December 2016
|Page(s)||935 - 949|
|Published online||03 November 2016|
Complexity analysis of interior point methods for linear programming based on a parameterized kernel function
1 LabCAV, Laboratory of Advanced Control, University of 8 May
1945 Guelma. BP 401, 24000 Guelma, Algeria.
2 Normandie Univ, LMAH – ULH, FR CNRS 3335, 25 rue Philippe Lebon, 76600 Le Havre, France.
3 L.M.F.N, Laboratory of Fundamental and Numerical Mathematics, University Setif 1, 19000 Setif, Algeria.
Accepted: 12 November 2015
Kernel function plays an important role in defining new search directions for primal-dual interior point algorithm for solving linear optimization problems. This problem has attracted the attention of many researchers for some years. The goal of their works is to find kernel functions that improve algorithmic complexity of this problem. In this paper, we introduce a real parameter p > 0 to generalize the kernel function (5) given by Bai et al. in [Y.Q. Bai, M El Ghami and C. Roos, SIAM J. Optim. 15 (2004) 101–128.], and give the corresponding primal-dual interior point methods for linear optimization. This parameterized kernel function yields the similar complexity bound given in [Y.Q. Bai, M El Ghami and C. Roos, SIAM J. Optim. 15 (2004) 101–128.] for both large-update and small-update methods.
Mathematics Subject Classification: 90C05 / 90C31 / 90C51
Key words: Linear optimization / Kernel function / interior point methods / complexity bound
© EDP Sciences, ROADEF, SMAI 2016
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.