Generic Primal-dual Interior Point Methods Based on a New Kernel Function
Department of Informatics, University
of Bergen, Thormøblensgate 55, 5008 Bergen, Norway;
2 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
Accepted: 28 November 2007
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 . We show that the corresponding large-update algorithm improves the iteration complexity with a factor 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 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