Shrinkwrapping Linear Programs
Shrinkwrapping Linear Programs
批准号:
0430672
负责人:
James Renegar
金额:
$18.05万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2004
资助国家:
美国
项目状态:
已结题
起止时间:
2004-08-15 至 2008-07-31
中文摘要
建议在计算和理论上进一步发展一族新的线性规划算法(更确切地说,是双曲规划算法)。设想的是新算法框架的全面数学发展,隔离那些似乎与构建真正实用的算法相关的想法,并免费提供实现(部分是为了鼓励其他研究人员参与并改进这些努力)。与线性规划的现有算法不同,新的框架层是组合结构。算法按顺序遍历各个层,从最不复杂的层开始,直到得到最优解,这通常发生在到达最后一层之前很久,即在用完整的组合结构进行显式计算之前很久。通过基本对称多项式、其双曲性圆锥和离散快速傅立叶变换(DFFT),分层的新思想在计算上变得容易处理。线性规划作为一种建模工具广泛存在于日常应用中,在各种运输调度中、在一系列综合财务管理活动中被依赖,更广泛地说,在任何需要最有效地部署有限资源的地方。更广泛地使用线性规划的一个主要瓶颈,特别是在数据经常变化的情况下,是解线性规划所需的计算时间。因此,通过创建能够比以前更快地获得线性规划解的算法,从而扩展线性规划作为建模工具的有用性,通过创建能够比以前更快地获得线性规划解的算法,从而扩展线性规划作为建模工具的有用性,开发诸如此处所示的新框架的新框架对社会具有潜在的影响。该提议的智力价值来自新框架的潜在价值,即通过将鼓舞人心的新概念注入研究领域来激励对线性规划(及其扩展)的算法研究,该领域在自内点方法产生以来的20年中在很大程度上成为静止的领域。智力价值还来自框架带来的凝聚力,该框架从工程(例如,线性规划,DFFT)到经典数学(例如对称函数、黎曼几何)。
英文摘要
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).
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Design of Gradient-Based Methods for Solving General and Huge Convex Optimization Problems
-
批准号:1812904
-
项目类别:Standard Grant
-
资助金额:$31.68万
-
财政年份:2018
-
负责人:James Renegar
-
依托单位:
CCF AF:EAGER:ASSESSING PRACTICALITY OF A NEW FRAMEWORK FOR SOLVING CONIC OPTIMIZATION PROBLEMS BY FIRST-ORDER METHODS
-
批准号:1552518
-
项目类别:Standard Grant
-
资助金额:$10.0万
-
财政年份:2015
-
负责人:James Renegar
-
依托单位:
A Deeper Understanding of the Geometry of Interior-Point Methods
-
批准号:9901941
-
项目类别:Standard Grant
-
资助金额:$19.84万
-
财政年份:1999
-
负责人:James Renegar
-
依托单位:
Issues Relating Linear Programming, Complexity Theory and Numeric Computation
-
批准号:9403580
-
项目类别:Standard Grant
-
资助金额:$12.21万
-
财政年份:1995
-
负责人:James Renegar
-
依托单位:
Complexity Theory Issues in Numeric and Algebraic Computation
-
批准号:9103285
-
项目类别:Continuing Grant
-
资助金额:$19.28万
-
财政年份:1991
-
负责人:James Renegar
-
依托单位:
Mathematical Sciences: Computational Complexity of Linear Programming and Polynomial Zero Approximation
-
批准号:8800835
-
项目类别:Continuing Grant
-
资助金额:$17.86万
-
财政年份:1988
-
负责人:James Renegar
-
依托单位:
Mathematical Sciences Postdoctoral Research Fellowship
-
批准号:8511482
-
项目类别:Fellowship Award
-
资助金额:$6.44万
-
财政年份:1985
-
负责人:James Renegar
-
依托单位:
Mathematical Sciences: Average Computational Complexity of Simplicial Algorithms
-
批准号:8404133
-
项目类别:Standard Grant
-
资助金额:$2.44万
-
财政年份:1984
-
负责人:James Renegar
-
依托单位:
国内基金
海外基金
Development of a Linear Stochastic Model for Wind Field Reconstruction from Limited Measurement Data
-
批准号:--
-
项目类别:--
-
资助金额:40万元
-
批准年份:2020
-
负责人:Vikrant Gupta
-
依托单位: