Structure of Efficient Sets for Convex Objectives

This paper considers multiple objective problems in which each objective is the minimization of a convex function defined over a convex solution space, and for which the number of objectives is greater than the dimension of the solution space. Such problems arise in location analysis, where the solution space of possible facility sites may be represented by a plane, but many location objectives may exist. We show that the set of efficient solutions to such problems exhibit structures similar to convex hulls. That is, the solutions on the boundary of the efficient set are efficient for “subproblems” obtained by considering only small subsets of objectives. The number of objectives in these subproblems is at most equal to the dimension of the solution space. When the objectives are continuous, and attain their minimum values in a bounded region over the solution space, the efficient set of the subproblems completely determine an efficient set for the larger problem.