Gradient projection and local region search for multiobjective optimisation

This paper presents a new method for multiobjective optimisation based on gradient projection and local region search. The gradient projection is conducted through the identification of normal vectors of an efficient frontier. The projection of the gradient of a nonlinear utility function onto the tangent plane of the efficient frontier at a given efficient solution leads to the definition of a feasible local region in a neighbourhood of the solution. Within this local region, a better efficient solution may be sought. To implement such a gradient-based local region search scheme, a new auxiliary problem is developed. If the utility function is given explicitly, this search scheme results in an iterative optimisation algorithm capable of general nonseparable multiobjective optimisation. Otherwise, an interactive decision making algorithm is developed where the decision maker is expected to provide local preference information in order to determine trade-off directions and step sizes. Optimality conditions for the algorithms are established and the convergence of the algorithms is proven. A multiobjective linear programming problem is taken for example to demonstrate this method both graphically and analytically. A nonlinear multiobjective water quality management problem is finally examined to show the potential application of the method to real world decision problems.