On characterizing the “knee” of the Pareto curve based on Normal-Boundary Intersection

Abstract

This paper deals with the issue of generating one Pareto optimal point that is guaranteed to be in a “desirable” part of the Pareto set in a given multicriteria optimization problem. A parameterization of the Pareto set based on the recently developed normal-boundary intersection technique is used to formulate a subproblem, the solution of which yields the point of “maximum bulge”, often referred to as the “knee of the Pareto curve”. This enables the identification of the “good region” of the Pareto set by solving one nonlinear programming problem, thereby bypassing the need to generate many Pareto points. Further, this representation extends the concept of the “knee” for problems with more than two objectives. It is further proved that this knee is invariant with respect to the scales of the multiple objective functions.

The generation of this knee however requires the value of each objective function at the minimizer of every objective function (the pay-off matrix). The paper characterizes situations when approximations to the function values comprising the pay-off matrix would suffice in generating a good approximation to the knee. Numerical results are provided to illustrate this point. Further, a weighted sum minimization problem is developed based on the information in the pay-off matrix, by solving which the knee can be obtained.