An ϵ–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.