Primal-dual algorithms for linear programming based on the logarithmic barrier method
- 格式：pdf
- 大小：283.35 KB
- 文档页数：29
ISSN 0922{5641 Reports of the Faculty of Technical Mathematics and Informatics Nr. 92{104 Delft 1992 i
B. Jansen, C. Roos and T. Terlaky, Faculty of Technical Mathematics and Informatics, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands. e{mail: roos@dutiosa.twi.tudelft.nl, terlaky@dutiosa.twi.tudelft.nl, bjansen@dutiosa.twi.tudelft.nl J.{Ph. Vial, Dept. d'Economie Commerciale et Industrielle, Universite de Geneve, 102 Bd Carl Vogt, CH{1211 Geneve, Switzerland. e{mail: jpvial@uni2a.unige.ch This work is completed with the support of a research grant from SHELL. The rst author is supported by the Dutch Organization for Scienti c Research (NWO) under grant 611-304-028. The third author is on leave from the Eotvos University, Budapest, and partially supported by OTKA No. 2116. The fourth author completed this work under the support of the research grant # 12{26434.89 of the Fonds National Suisses de la Recherche Scienti que.
Copyright c 1992 by Faculty of Technical Mathematics and Informatics, Delft, The Netherlands. No part of this Journal may be reproduced in any form, by print, photoprint, micro lm or any other means without written permission from Faculty of Technical Mathematics and Informatics, Delft University of Technology, The Netherlands.
ISSN 0922-5641 Copyright c 1992 by the Faculty of Technical Mathematics and Informatics, Delft, The Netherlands. No part of this Journal may be reproduced in any form, by print, photoprint, microfilm, or any other means without permission from the Faculty of Technical Mathematics and Informatics, Delft University of Technology, The Netherlands. Copies of these reports may be obtained from the bureau of the Faculty of Technical Mathematics and Informatics, Julianalaan 132, 2628 BL Delft, phone +3115784568. A selection of these reports is available in PostScript form at the Faculty’s anonymous ftp-site. They are located in the directory /pub/publications/tech-reports at ftp.twi.tudelft.nl
Abstract
iii
1 Introduction
In 1984 Karmarkar published his remarkable paper 10]. Shortly after, some authors 4] pointed out the connection between his projective algorithm and the standard logarithmic barrier method 3] for mathematical programming. This relation has been further exploited to demonstrate that the logarithmic barrier approach leads to polynomial-time algorithms, 6] 7] and 25] 26]. In these methods the search direction of choice is the projected Newton direction associated with the barrier function. The norm of this direction is used in 25, 26] as a kind of measure of proximity to the central path. This leads to a simple convergence analysis of the so{called short{step path{following method, with p convergence bound of O( nL) iterations. The analysis extends quite naturally to the more practical long{step method with a bound of O(nL) iterations. Later, it was shown in 1], in the framework of quadratic programming, that the twenty years old implementation SUMT of the logarithmic barrier method 22] exactly coincides with the long{step method. (See also 16].) The most popular interior point algorithms nowadays are the so{called primal{ dual methods. They were rst introduced as path{following methods, 11] and 20], but later they have been extended to a potential reduction approach 12] p that is more practical but still has a bound of O( nL) iterations. In fact, an impressive amount of papers on primal{dual methods has been published in the last years. It is not our aim to give an extensive survey at this place. Instead we refer to the bibliography of Kranich 13] for more references. As their name indicates, primal{dual methods operate simultaneously on the primal and on the dual, an appealing feature due to the intimate relationship between the primal and the dual problem. The search direction in these methods is not derived from a logarithmic barrier or from a potential function. Rather, it is directly associated with the asymmetric system of equations that de nes the central path. This leads to analyses quite di erent from 25, 26]. To our knowledge, the logarithmic barrier function approach has not yet been used in connection with primal{dual methods. Since the more e cient implementations for linear programming are the primal{dual methods 15] 17] 19], it is appropriate to fully explore the theoretical algorithm for a better understanding of the method. The purpose of this paper is to ll the existing gap in the literature and to develop an approach similar to 25, 26] for primal{dual algorithms. In this paper we introduce a primal{dual barrier function, that naturally extends the standard primal and dual barrier logarithmic functions. We show that the directional derivative of the primal{dual logarithmic barrier function with respect to the standard primal{dual direction has a simple expression. We further observe that the absolute value of this derivative can be used as a new measure of proximity to the central path. Based on these remarks, the 1
