A geometric characterization of "optimality-equivalent" relaxations

An optimization problem is defined by an objective function to be maximized with respect to a set of constraints. To overcome some theoretical and practical difficulties, the constraint-set is sometimes relaxed and "easier" problems are solved. This led us to study relaxations providing exactly the same set of optimal solutions. We give a complete characterization of these relaxations and present several examples. While the relaxations introduced in this paper are not always easy to solve, they may help to prove that some mathematical programs are equivalent in terms of optimal solutions. An example is given where some of the constraints of a linear program can be relaxed within a certain limit.