A Convergent Interactive Cutting-Plane Algorithm for Multiobjective Optimization

This paper presents an interactive cutting-plane algorithm for determining a best-compromise solution to a multiobjective optimization problem in situations with an implicitly defined utility function. We derive cutting planes that are based on suitable pairwise trade-offs between the objective functions, as prescribed by the decision maker at each iterate generated by the algorithm. The proposed algorithm requires no line searches, and generates iterates that are all contained in the efficient frontier. This feature facilitates the preference judgment of the decision maker, and permits an analyst to terminate short of optimality with an efficient near-optimal solution. A convergence analysis establishes that any accumulation point generated by the algorithm is a best-compromise solution. We also conduct an error analysis to point out the effect of inconsistencies in trade-off information provided by the decision maker. The algorithm may be extended to situations involving nonconvex feasible regions, as well as nonconcave (for a max problem) objective functions. We offer remarks for such cases, and describe an application to an urban runoff control-design problem.