  


A Comparative Study of New Barrier Functions for PrimalDual InteriorPoint Algorithms in Linear Optimization
Y.Q. Bai (Y.Baiewi.tudelft.nl) Abstract: Recently, socalled selfregular barrier functions for primaldual interiorpoint methods (IPMs) for linear optimization were introduced. Each such barrier function is determined by its (univariate) selfregular kernel function. We introduce a new class of kernel functions. The class is defined by some simple conditions on the kernel function and its derivatives. These properties enable us to derive many new and tight estimates that greatly simplify the analysis of IPMs based on these kernel functions. Both in the algorithm and in its analysis we use a single neighborhood of the central path; the neighborhood naturally depends on the kernel function. An important conclusion is that inverse functions of suitable restrictions of the kernel function and its first derivative more or less determine the behavior of the corresponding IPMs. Based on the new estimates we present a simple and unified computational scheme for the complexity analysis of kernel function in the new class. We apply this scheme to seven specific kernel functions. Some of these functions are selfregular and others are not. One of the functions differs from the others, and from all selfregular functions, in the sense that its growth term is linear. Iteration bounds both for large and smallupdate methods are derived. It is shown that smallupdate methods based on the new kernel functions all have the same complexity as the classical primaldual IPM, namely $O(\sqrt{n}\,\log\frac{n}{\e})$. For largeupdate methods the best obtained bound is $O(\sqrt{n}\,(\log n)\,\log\frac{n}{\e})$, which is up till now the best known bound for such methods. Keywords: Linear optimization, interiorpoint method, primaldual method, largeupdate method, polynomial complexity Category 1: Linear, Cone and Semidefinite Programming Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: TU Delft, Mekelweg 4, Delft, NL Download: [PDF] Entry Submitted: 09/08/2003 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  