Theory and Algorithms for Finding Knees

A multi-objective optimization problem involves multiple and conflicting objectives. These conflicting objectives give rise to a set of Pareto-optimal solutions. However, not all the members of the Pareto-optimal set have equally nice properties. The classical concept of proper Pareto-optimality is a way of characterizing good Pareto-optimal solutions. In this paper, we metrize this concept to induce an ordering on the Pareto-optimal set. The use of this metric allows us to define a proper knee region, which contains solutions below a user-specified threshold metric. We theoretically analyze past definitions of knee points, and in particular, reformulate a commonly used nonlinear program, to achieve convergence results. Additionally, mathematical properties of the proper knee region are investigated. We also develop two multi-objective evolutionary algorithms towards finding proper knees and present simulation results on a number of test problems.