On the Dimension of the Set of Rim Perturbations for Optimal Partition Invariance

H.J. Greenberg, A.G. Holder, C. Roos, and T. Terlaky

Two new dimension results are presented. For linear programs, it is shown that the sum of the dimension of the optimal set and the dimension of the set of objective perturbations for which the optimal partition is invariant equals the number of variables. A decoupling principle shows that the primal and dual results are additive. The main result is then extended to convex quadratic programs, but the dimension relationships are no longer dependent only on problem size. Further, although the decoupling principle does not extend completely, the dimensions are additive, as in the linear case. Futhermore, if a strictly complementary solution exists, all the results are completely analogous to the linear case.

Technical Report CCM No. 94, Center for Computational Mathematics, Mathematics Department, University of Colorado at Denver, Denver, CO 80217-3364

Contact: hgreenbe@carbon.cudenver.edu