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

✍ Scribed by Woo-Je Kim; Chan-Kyoo Park; Soondal Park

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 124 KB
• Volume: 116
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(98)00117-9

✦ Synopsis

This paper presents a method of sensitivity analysis on the cost coecients and the right-hand sides for most variants of the primal±dual interior point method. We ®rst de®ne an e-optimal solution to describe the characteristics of the ®nal solution obtained by the primal±dual interior point method. Then an e-sensitivity analysis is de®ned to determine the characteristic region where the ®nal solution remains the e-optimal solution as a cost coecient or a right-hand side changes. To develop the method of e-sensitivity analysis, we ®rst derive the expressions for the ®nal 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 coecients and the right-hand sides by manipulating the mathematical expressions for the ®nal solution. Finally, we show that in the nondegenerate case, the characteristic regions obtained by e-sensitivity analysis are convergent to those obtained by sensitivity analysis in the simplex algorithm.