Method of Feasible Directions with Hit-and-Run Sampling for Solving Linearly Constrained Multi-Objective Optimization Problems

This paper proposes an extension of Zoutendijk’s Method of Feasible Directions (MFD) for solving linearly constrained multi-objective optimization problems. The approach integrates a Hit-and-Run sampling technique to generate a diverse set of feasible points and uses an iterative two-step process. This process involves determining an improving feasible direction by solving a quadratic subproblem and adjusting the step size using the multi-objective Armijo rule. As a result, the method generates a sequence of feasible points that converge to a critical Pareto point, and under convexity assumptions, to a Pareto-optimal point. The process is applied to all points in the generated population, enabling an adequate approximation of the Pareto front. The convergence of the method is proven. A comparative study, conducted in MATLAB on 25 linearly constrained multi-objective optimization benchmark problems, evaluates our MFD against the NSGA-II algorithm and another variant of MFD that uses a different direction search subproblem and sampling procedure. The quality of the approximated Pareto front is assessed using four metrics: purity, spacing, hypervolume, and generalized spread. The results show that our MFD outperforms the other methods in terms of both convergence speed and the quality of the Pareto front for the tested problems