ε-sensitivity analysis in the primal-dual interior point method

This paper presents a method of sensitivity analysis on the cost coefficients and the right-hand sides for most variants of the primal-dual interior point method. We first define an ε-optimal solution to describe the characteristics of the final solution obtained by the primal-dual interior point method. Then an ε-sensitivity analysis is defined to determine the characteristic region where the final solution remains the ε-optimal solution as a cost coefficient or a right-hand side changes. To develop the method of ε-sensitivity analysis, we first derive the expressions for the final solution from data which are commonly maintained in most variants of the primal-dual interior point method. Then we extract the characteristic regions on the cost coefficients and the right-hand sides by manipulating the mathematical expressions for the final solution. Finally, we show that in the nondegenerate case, the characteristic regions obtained by ε-sensitivity analysis are convergent to those obtained by sensitivity analysis in the simplex algorithm.