Shrinkwrapping Linear Programs

点击翻译按钮获取中文摘要

It is proposed that a new family of algorithms for linear programming (moregenerally, for hyperbolic programming) be further developed, both computationallyand theoretically. Envisioned is a full mathematical development of the newalgorithmic framework, isolation of those ideas that appear likely to be pertinentfor constructing truly practical algorithms, and the free availability of implementations(partly to encourage other researchers to participate and improve on theefforts).Unlike existing algorithms for linear programming, the new framework layerscombinatorial structure. The algorithms work through the layers sequentially,beginning with the least complex one, and continuing until an optimal solu-tionis attained, which generally occurs long before reaching the final layer, i.e.,long before explicitly calculating with the full combinatorial structure. The newidea of layering is made computationally tractable via the elementary symmetricpolynomials, their hyperbolicity cones, and the discrete Fast Fourier Transform(dFFT).Linear programming as a modeling tool is pervasive in daily applications, beingrelied upon in all kinds of transportation scheduling, in an array of integrativefinancial management activities, and more generally, anywhere that limited resourcesneed to be deployed most efficiently. A primary bottleneck to even moreextensive use of linear programs, especially in settings where data change oftenis the computational time required to solve linear programs. Consequently,development of a novel framework such as the one presented here has the poten-tialof broader impact on society through the creation of algorithms capableof attaining linear program solutions faster than before, thereby extending theusefulness of linear programming as a modeling tool.Intellectual merit for the proposal comes from the new framework's po-tentialto invigorate algorithmic investigations into linear programming (and itsextensions) by infusing inspiring new concepts into the research area, an area thathas largely become staid in the 20 years since interior-point methods created stir.Intellectual merit also comes from the cohesion brought by the framework, aframework that stretches from engineering (e.g., linear programming, dFFT) toclassical mathematics (e.g., symmetric functions, Riemannian geometry).