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

该项目解决了线性规划（LP）背景下灵敏度分析的新方法的设计、开发和实现，该方法不需要最优基础的知识。这种灵敏度分析方法的主要应用是在内点法的背景下。范围分析是本研究项目的重点。还讨论了参数分析，并对极差分析的方法进行了激励。该方法基于Adler和Monteiro提出的参数线性规划问题的新观点。给出了代价范围和右侧系数范围的一种新的解释，并证明了LP问题的范围的计算简化为对某些LP子问题的最优值的估计。本研究涉及两个主要任务。首先是理解简并的影响。二是开发子问题最优值的有效估计方法。该项目有望增强（并可能改变）我们对LP敏感性分析的理解。

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.