Dimension of the Set of Rim Perturbations for Optimal Partition Invariance

摘要

Two new dimension results are presented. For linear programs, it is shown thatthe 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 not 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.