文档介绍：Journal putational and Applied Mathematics 224 (2009) 500–513
Contents lists available at ScienceDirect
Journal putational and Applied
Mathematics
journal homepage: ate/cam
A polynomial-time algorithm for linear optimization based on a new
class of kernel functions
M. El Ghami a,∗, I. Ivanov b, . Melissen b, C. Roos b, T. Steihaug a
a University of Bergen, Department of Informatics, Høyteknologisenteret, N-5020, Bergen, Norway
b Delft University of Technology, Department of Information Systems and Algorithms, . Box 5031, 2600 GA Delft, herlands
a r t i c l e i n f o a b s t r a c t
Article history: In this paper we present a class of polynomial primal-dual interior-point algorithms for
Received 7 November 2007 linear optimization based on a new class of kernel functions. This class is fairly general
and includes the class of finite kernel functions by . Bai, Ghami and C. Roos [.
MSC: Bai, M. El Ghami, and C. Roos. A new efficient large-update primal-dual interior-point
90C51 method based on a finite barrier, SIAM Journal on Optimization, 13 (3) (2003) 766–782].
90C05
The proposed functions have a finite value at the boundary of the feasible region. They
Keywords: are not exponentially convex and also not strongly convex like the usual barrier functions.
Kernel function The goal of this paper is to investigate such a class of kernel functions and to show that
Primal-dual interior-point algorithm the interior-point methods based on these functions have plexity results.
Large-update method In order to achieve plexity results, several new arguments had to be used for
Small-update method
the analysis. The iteration bound of large-update interior-point√ methods based on these
Complexity ( n )
functions and analyzed in this paper, is shown to√ be O n log n log . For small-update
n
interior-point methods the iteration bound is O n log , which is currently the best-
known bound for primal-dual IPMs. We also pr