Research Initiation: Sensitivity Analysis Approach in the Absence of an Optimal Basis and its Application to the Framework of Interior Point Methods

研究发起：无最优基础下的敏感性分析方法及其在内点方法框架中的应用

• 批准号: 9109404
• 负责人: Renato D. C. Monteiro
• 金额: $ 6万
• 依托单位: University of Arizona
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-07-01 至 1994-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9109404&HistoricalAwards=false
• 关键词: Research; Initiation; Sensitivity; Analysis; Approach

This project addresses the design, development, and implementation of a new approach to sensitivity analysis in the context of linear programming (LP) that does not require the knowledge of an optimal basis. The main application of this sensitivity analysis approach is in the context of interior point methods. Range analysis is the main emphasis of this research project. Parametric analysis is also discussed and serves to motivate the approach to range analysis. The approach is based on a new view of the parametric linear programming problem developed by Adler and Monteiro. A new interpretation for ranges of the cost and right hand side coefficients is given and it is shown that the computation of the ranges for the LP problem reduces to the estimation of optimal values of certain LP subproblems. Two major tasks are involved in this research. The first is to understand the affect of degeneracy. The second is to develop efficient ways of estimating the optimal values for the subproblems. This project promises to enhance (and possibly change) our understanding of LP sensitivity analysis.

该项目涉及设计，开发和 采用新的敏感性分析方法， 线性规划（LP）的背景，不需要 最佳基础的知识。 主要应用此 敏感性分析方法是内点法 方法. 极差分析是本研究的重点 项目 还讨论了参数分析， 激励范围分析方法。 该方法是基于 关于参数线性规划问题的一个新观点 由阿德勒和蒙泰罗提出。 值域的新解释 的成本和右手边系数，它是 表明LP问题的范围计算 简化为对某些LP的最优值的估计 子问题 本研究涉及两个主要任务。 第一个是了解简并的影响。 第二 是开发有效的方法来估计最佳值 子问题。 这个项目承诺提高（并可能改变）我们的 了解LP敏感性分析。