Sensitivity analysis in linear and convex quadratic optimization: Invariant active constraint set and invariant set intervals

Published in INFOR: Information Systems and Operational Research, 2006


Support set invariancy sensitivity analysis is concerned with the finding the range of parameter variation so thai the perturbed problem has still an optimal solution with the same support set that Ihe given optimal solution of the unperturbed problem has. This type of sensitivity analysis in linear and convex quadratic optimization has been recently studied by Ghaffari and Terlaky by restricting their interest on finding this range for primal optimal solutions of Ihese problems. They referred to the range of the parameter as inviiriant support set interval.

In this paper, we consider the question: “what the range of the parameter is. where for each parameter value in this range, a dual t)ptinial solution exists with exactly the same set of positive dual slack variables as for the current dual optimal solution.’”. Further, the concept of invariant set interval is introduced that is the parameter range, where both the primal variable and the dual slack variable in an optimal solution for each parameter value have invariant support .sets. We present computational methods to identify these intervals and investigate their interrelationship.