Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/103833
Title: On the relationship between the curvature integral and the complexity of path-following methods in linear programming
Authors: Zhao, G. 
Keywords: Bounds of derivatives
Central trajectory (path)
Complexity
Curvature integral
Derivatives
Linear programming
Path-following methods
Issue Date: Feb-1996
Source: Zhao, G. (1996-02). On the relationship between the curvature integral and the complexity of path-following methods in linear programming. SIAM Journal on Optimization 6 (1) : 57-73. ScholarBank@NUS Repository.
Abstract: In this paper we study the complexity of primal-dual path-following methods which are a particular kind of interior point method for solving linear programs. In particular we establish a relationship between the complexity and the integral of a weighted curvature along the central trajectory (path) defined in the interior of the feasible solution space of a linear program. An important property of the trajectory, viz., that its higher order derivatives are bounded by a geometric series, is presented. Applying this property we show that the complexity of such methods is bounded from below and from above by the curvature integral. This theorem reduces the complexity analysis to a relatively simple problem of estimating the curvature integral.
Source Title: SIAM Journal on Optimization
URI: http://scholarbank.nus.edu.sg/handle/10635/103833
ISSN: 10526234
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

13
checked on Jan 19, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.