An Efficient Primal-Dual Interior Point Method for Linear Programming Problems Based on a New Kernel Function with a Trigonometric Barrier Term

被引:36
作者
Bouafia, Mousaab [1 ,2 ]
Benterki, Djamel [3 ]
Yassine, Adnan [2 ]
机构
[1] Univ 8 May 1945 Guelma, Lab Adv Control, LabCAV, BP 401, Guelma 24000, Algeria
[2] Normandie Univ, FR CNRS 3335, LMAH ULH, 25 Rue Philippe Lebon, F-76600 Le Havre, France
[3] Univ Setif 1, LMFN, Setif 19000, Algeria
关键词
Linear optimization; Kernel function; Interior point methods; Complexity bound; ALGORITHM; COMPLEXITY;
D O I
10.1007/s10957-016-0895-0
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper, we present a primal-dual interior point method for linear optimization problems based on a new efficient kernel function with a trigonometric barrier term. We derive the complexity bounds for large and small-update methods, respectively. We obtain the best known complexity bound for large update, which improves significantly the so far obtained complexity results based on a trigonometric kernel function given by Peyghami et al. The results obtained in this paper are the first to reach this goal.
引用
收藏
页码:528 / 545
页数:18
相关论文
共 17 条
[1]  
Bai Y.Q., 2002, P 9 AUSTR OPT DAY PE
[2]   A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization [J].
Bai, YQ ;
El Ghami, M ;
Roos, C .
SIAM JOURNAL ON OPTIMIZATION, 2004, 15 (01) :101-128
[3]   Complexity Analysis of Primal-Dual Interior-Point Methods for Linear Optimization Based on a New Parametric Kernel Function with a Trigonometric Barrier Term [J].
Cai, X. Z. ;
Wang, G. Q. ;
El Ghami, M. ;
Yue, Y. J. .
ABSTRACT AND APPLIED ANALYSIS, 2014,
[4]   An interior-point algorithm for linear optimization based on a new barrier function [J].
Cho, Gyeong-Mi .
APPLIED MATHEMATICS AND COMPUTATION, 2011, 218 (02) :386-395
[5]   Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term [J].
El Ghami, M. ;
Guennoun, Z. A. ;
Bouali, S. ;
Steihaug, T. .
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2012, 236 (15) :3613-3623
[6]  
El Ghami M., 2008, International Journal of Applied Mathematics, V21, P99
[7]   A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING [J].
KARMARKAR, N .
COMBINATORICA, 1984, 4 (04) :373-395
[8]  
Kheirfam B., 2015, Yugosl. J. Oper. Res., V25, P233, DOI [10.2298/YJOR120904006K, DOI 10.2298/YJOR120904006K]
[9]   Interior-point algorithm for linear optimization based on a new trigonometric kernel function [J].
Li, Xin ;
Zhang, Mingwang .
OPERATIONS RESEARCH LETTERS, 2015, 43 (05) :471-475
[10]  
Megiddo N., 1989, PROGR MATH PROGRAMMI, P131, DOI 10.1007/978-1-4613-9617-8_8