A post-optimality analysis algorithm for multi-objective optimization

Vandana Venkat, Sheldon H. Jacobson, James A. Stori

Research output: Contribution to journalArticlepeer-review

Abstract

Algorithms for multi-objective optimization problems are designed to generate a single Pareto optimum (non-dominated solution) or a set of Pareto optima that reflect the preferences of the decision-maker. If a set of Pareto optima are generated, then it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optima using an unbiased technique of filtering solutions. This suggests the need for an efficient selection procedure to identify such a preferred subset that reflects the preferences of the decision-maker with respect to the objective functions. Selection procedures typically use a value function or a scalarizing function to express preferences among objective functions. This paper introduces and analyzes the Greedy Reduction (GR) algorithm for obtaining subsets of Pareto optima from large solution sets in multi-objective optimization. Selection of these subsets is based on maximizing a scalarizing function of the vector of percentile ordinal rankings of the Pareto optima within the larger set. A proof of optimality of the GR algorithm that relies on the non-dominated property of the vector of percentile ordinal rankings is provided. The GR algorithm executes in linear time in the worst case. The GR algorithm is illustrated on sets of Pareto optima obtained from five interactive methods for multi-objective optimization and three non-linear multi-objective test problems. These results suggest that the GR algorithm provides an efficient way to identify subsets of preferred Pareto optima from larger sets.

Original languageEnglish (US)
Pages (from-to)357-372
Number of pages16
JournalComputational Optimization and Applications
Volume28
Issue number3
DOIs
StatePublished - Sep 2004

Keywords

  • Greedy reduction algorithm
  • Multi-objective optimization
  • Pareto optimality
  • Percentile levels
  • Post-optimality analysis

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A post-optimality analysis algorithm for multi-objective optimization'. Together they form a unique fingerprint.

Cite this