Trade-off preservation in inverse multi-objective convex optimization

Timothy C. Y. Chan, Taewoo LeeEur. J. Oper. Res 2017

TL;DR

This paper introduces a novel inverse optimization framework for multi-objective convex problems that aims to find objective function weights that not only make a given (potentially non-optimal) solution optimal, but also preserve the original decision-maker's trade-offs between objectives. This is achieved through a new concept called "trade-off preservation," which is crucial for applications like treatment planning where replicating historical outcomes is key.

What Problem Does This Paper Address?

In multi-objective optimization, decision-makers often face a trade-off between competing objectives (e.g., maximizing treatment efficacy while minimizing damage to healthy tissue). Inverse optimization aims to infer the objective function weights that would have led to a given observed solution. However, traditional methods often assume the observed solution is already Pareto optimal. This paper addresses the challenge when the observed solution is not Pareto optimal, or when it's an approximation. In such cases, simply finding weights that make the solution optimal might drastically alter the original decision-maker's intended trade-offs. The authors propose a method to find weights that not only achieve optimality but also maintain the "spirit" of the original trade-offs, which is vital for applications where historical data represents accepted compromises.

Methods

The core of the paper is the introduction of "trade-off preservation," a concept that quantifies how well a new Pareto optimal solution (derived from inferred weights) maintains the relative or absolute differences between objective values compared to the original, non-Pareto optimal solution.

  1. General Trade-off Preservation: A formal definition is provided, relating the changes in objective values between the original and new solutions, scaled by problem-specific factors.
  2. Relative Trade-off Preservation: A specific case where the objective values of the new solution are proportionally adjusted from the original solution. This is geometrically interpreted as the new solution lying on the line connecting the original solution and the origin in the objective space.
  3. Absolute Trade-off Preservation: Another specific case where the objective values are adjusted by the same absolute amount.
  4. Inverse Optimization Models: The authors formulate convex optimization problems (IOP, IOPr, IOPa) to find weight vectors that satisfy these trade-off preservation criteria.
  5. Linear Approximation (LIOP): To improve computational efficiency, a linearized version of the general inverse optimization problem is proposed, leading to a successive linear programming (SLP) algorithm.

Datasets

The paper uses a dataset of 24 historical prostate cancer radiation therapy treatment plans from Princess Margaret Cancer Centre for retrospective analysis. This dataset is used to evaluate the performance of the proposed inverse optimization models against existing methods.

Key Insights and Ideas

  • Trade-off Preservation is Crucial: Simply finding weights that make a non-optimal solution optimal can lead to solutions that deviate significantly from the decision-maker's original intentions, which is problematic in fields like medical treatment planning.
  • Generalizing Inverse Optimization: The proposed framework extends inverse optimization to handle non-Pareto optimal input solutions while explicitly preserving trade-offs.
  • Connection to Duality Gap: The proposed trade-off preservation concepts are shown to be directly related to minimizing duality gaps (both relative and absolute), providing a theoretical link to existing inverse optimization ideas.
  • Computational Trade-offs: The proposed exact models (IOP) offer better trade-off preservation but are computationally more expensive than linearized versions (LIOP) or existing methods like KES. The SLP algorithm strikes a balance.

Key Results

  • The proposed inverse optimization models (IOP, IOPr, IOPa) can successfully determine weight vectors that preserve trade-offs encoded in a given solution.
  • The KES model (Keshavarz et al., 2011) was found to be highly sensitive to the normalization choice, often emphasizing only one objective and showing high variance in trade-off preservation.
  • The IOP model provided the best trade-off preservation (lowest variance in objective function ratios) but had the longest solution times.
  • The LIOP model and the SLP algorithm offered a good balance between computational efficiency and trade-off preservation.
  • In the prostate cancer radiation therapy application, treatments generated using trade-off preserving weights (specifically IOP) were shown to be more similar to historical clinical plans and maintained clinical quality metrics better than those generated by non-trade-off-preserving methods (like KES).

Limitations and Future Work

  • Computational Cost: The exact inverse optimization models (IOP) can be computationally expensive, especially for large-scale problems. The paper proposes linearization (LIOP) and SLP as solutions.
  • "Inferior" Objectives: In cases where an objective is significantly "inferior" (e.g., a very high dose for an organ-at-risk), the inverse optimization might assign a zero weight to that objective, meaning trade-off preservation might not be perfect for all objectives.
  • Future Work: The authors suggest that their framework is important for designing next-generation automated treatment planning systems, implying further research into integrating these models into clinical workflows. The connection to duality gap minimization also opens avenues for further theoretical exploration.

Summary updated

Abstract

We present a new inverse optimization methodology for multi-objective convex optimization that accommodates an input solution that may not be Pareto optimal and determines a weight vector that produces a Pareto optimal solution that approximates the input solution and preserves the decision maker's intention encoded in it. We introduce a notion of trade-off preservation, which we use as a measure of similarity for approximating the input solution, and show its connection with minimizing an optimality gap. Our inverse model maintains the complexity of the traditional inverse convex models. We propose a linear approximation to the model and a successive linear programming algorithm that balance between trade-off preservation and computational efficiency, and show that our model encompasses many of the existing models from the literature. We demonstrate the proposed method using clinical data from prostate cancer radiation therapy.
BibTeX
@article{chan2017trade,
  author = {Timothy C. Y. Chan and Taewoo Lee},
  title = {{Trade-off preservation in inverse multi-objective convex optimization}},
  journal = {Eur. J. Oper. Res.},
  year = {2017},
}
Figure