Interior-point algorithm for linear optimization based on a new trigonometric kernel function

被引：31
作者：
Li, Xin [1 ]
Zhang, Mingwang [1 ]
机构：
[1] China Three Gorges Univ, Coll Sci, Yi Chang 443002, Peoples R China
来源：
OPERATIONS RESEARCH LETTERS | 2015年 / 43卷 / 05期
关键词：
Linear optimization; Kernel function; Interior-point algorithm; Large-update; Polynomial complexity;
D O I：
10.1016/j.orl.2015.06.013
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper, we present a new primal-dual interior-point algorithm for linear optimization based on a trigonometric kernel function. By simple analysis, we derive the worst case complexity for a large-update primal-dual interior-point method based on this kernel function. This complexity estimate improves a result from El Ghami et al. (2012) and matches the one obtained in Reza Peza Peyghami et al. (2014). (C) 2015 Elsevier B.V. All rights reserved.
引用
收藏
页码：471 / 475
页数：5
相关论文
共 12 条
[1]  
Bai Y.Q., 2002, P IND OPT S OPT DAY
[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]   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
[4]   A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING [J].
KARMARKAR, N .
COMBINATORICA, 1984, 4 (04) :373-395
[5]  
Megiddo N., 1989, PROGR MATH PROGRAMMI, P131, DOI 10.1007/978-1-4613-9617-8_8
[6]   ON THE IMPLEMENTATION OF A PRIMAL-DUAL INTERIOR POINT METHOD [J].
Mehrotra, Sanjay .
SIAM JOURNAL ON OPTIMIZATION, 1992, 2 (04) :575-601
[7]  
Peng J., 2002, SELF REGULAR FUNCTIO, V93, P234
[8]  
Peng Jiming., 2002, PRIN SER APPL MATH
[9]   Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function [J].
Peyghami, M. Reza ;
Hafshejani, S. Fathi ;
Shirvani, L. .
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2014, 255 :74-85
[10]  
Qian Z., 2008, Journal of Shanghai University, V12, P388, DOI [10.1007/s11741-008-0503-2, DOI 10.1007/S11741-008-0503-2]
12