A GEOMETRICAL ANALYSIS OF THE EFFICIENT OUTCOME SET IN MULTIPLE-OBJECTIVE CONVEX-PROGRAMS WITH LINEAR CRITERION FUNCTIONS

This article performs a geometrical analysis of the efficient outcome set Y-E of a multiple objective convex program (MLC) with linear criterion functions. The analysis elucidates the facial structure of Y-E and of its pre-image, the efficient decision set X(E). The results show that Y-E often has a significantly-simpler structure than X(E). For instance, although both sets are generally nonconvex and their maximal efficient faces are always in one-to-one correspondence, large numbers of extreme points and faces in X(E) can map into non-facial subsets of faces in Y-E, but not vice versa. Simple tests for the efficiency of faces in the decision and outcome sets are derived, and certain types of faces in the decision set are studied that are immune to a common phenomenon called ''collapsing.'' The results seem to indicate that significant computational benefits may potentially be derived if algorithms for problem (MLC) were to work directly with the outcome set of the problem to find points and faces of Y-E, rather than with the decision set.