An Analogue of the Klee–Walkup Result for Sonnevend’s Curvature of the Central Path

Murat Mut () and Tamás Terlaky ()
Additional contact information
Murat Mut: Nielsen Marketing Analytics
Tamás Terlaky: Lehigh University

Journal of Optimization Theory and Applications, 2016, vol. 169, issue 1, No 2, 17-31

Abstract: Abstract For linear optimization problems, we consider a curvature integral of the central path which was first introduced by Sonnevend et al. (Math Progr 52:527–553, 1991). Our main result states that in order to establish an upper bound for the total Sonnevend curvature of the central path of a polytope, it is sufficient to consider only the case where the number of inequalities is twice as many as the number of variables. This also implies that the worst cases of linear optimization problems for certain path-following interior-point algorithms can be reconstructed for the aforementioned case. As a by-product, our construction yields an asymptotically worst-case lower bound in the order of magnitude of the number of inequalities for Sonnevend’s curvature. Our research is motivated by the work of Deza et al. (Electron Notes Discrete Math 31:221–225, 2008) for the geometric curvature of the central path, which is analogous to the Klee–Walkup result for the diameter of a polytope.

Keywords: Curvature; Central path; Polytopes; Diameter; Complexity; Interior-point methods; Linear optimization; 52B05; 65K05; 68Q25; 90C05; 90C51; 90C60 (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-015-0764-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:169:y:2016:i:1:d:10.1007_s10957-015-0764-2

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-015-0764-2

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().