RAIRO - Operations Research (RAIRO: RO)

| Abstract | PDF (231.3 KB) | References |

RAIRO-Oper. Res. 42 (2008) 199-213
DOI: 10.1051/ro:2008009

Generic Primal-dual Interior Point Methods Based on a New Kernel Function

M. EL Ghami¹ and C. Roos²

¹ Department of Informatics, University of Bergen, Thormøblensgate 55, 5008 Bergen, Norway; melghami@ii.uib.no
² Faculty of Electrical Engineering, Mathematics, and Computer Science, Delft University of Technology, PO Box 5031, 2600 GA Delft, The Netherlands; C.Roos@ewi.tudelft.nl

(Received February 9, 2007. Accepted November 28, 2007 Published online 17 May 2008.)

Abstract
In this paper we present a generic primal-dual interior point methods (IPMs) for linear optimization in which the search direction depends on a univariate kernel function which is also used as proximity measure in the analysis of the algorithm. The proposed kernel function does not satisfy all the conditions proposed in [2]. We show that the corresponding large-update algorithm improves the iteration complexity with a factor $n^{\frac16}$ when compared with the method based on the use of the classical logarithmic barrier function. For small-update interior point methods the iteration bound is $O(\sqrt{n}\log\frac{n}{\epsilon}),$ which is currently the best-known bound for primal-dual IPMs.

Mathematics Subject Classification. 90C05, 90C31.

Key words: Linear optimization, primal-dual interior-point algorithm, large and small-update method.

© EDP Sciences, ROADEF, SMAI 2008