  


An analogue of the KleeWalkup result for Sonnevend’s curvature of the central path
Murat Mut(mhm309lehigh.edu) Abstract: For linear optimization (LO) problems, we consider a curvature integral ﬁrst introduced by Sonnevend et al. (1991). Our main result states that in order to establish an upper bound for the total Sonnevend curvature of the central path, it is sufficient to consider only the case when n = 2m. This also implies that the worst cases of LO problems for pathfollowing algorithms can be reconstructed for the case of n = 2m. As a byproduct, our construction yields an asymptotically Ω(n) worstcase lower bound for Sonnevend’s curvature. Our research is motivated by the work of Deza et al. (2008) for the geometric curvature of the central path, which is analogous to the KleeWalkup result for the diameter of a polytope. Keywords: Curvature Central path Polytopes Diameter Complexity Interiorpoint methods Linear optimization Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Download: [PDF] Entry Submitted: 04/10/2013 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  