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敏感性分析的理解。

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.