Goodness of Fit in Inverse Optimizaiton

Timothy C. Y. Chan, Taewoo Lee, Daria Terekhov

Abstract

The classical inverse optimization methodology for linear optimization assumes a given solution is a candidate to be optimal. Real data, however, is imperfect and noisy: there is no guarantee that a given solution is optimal for any cost vector. Inspired by regression, this paper presents a unified framework for cost function estimation in linear optimization consisting of a general inverse optimization model and a corresponding goodness-of-fit metric. Although our inverse optimization model is in general nonconvex, we derive a closed-form solution and present the corresponding geometric intuition. Our goodness-of-fit metric, $\rho$, termed the coefficient of complementarity, has similar properties to $R^2$ from regression and is quasiconvex in the input data, leading to an intuitive geometric interpretation. We derive a lower bound for $\rho$ that possesses the same properties but is more tractable. We demonstrate the application of our framework for model estimation and evaluation in production planning and cancer therapy.

Introduction

In the standard "forward" optimization problem, we begin with a known cost function and a set of constraints to determine an optimal decision. Inverse Optimization (IO) reverses this logic: given an observed decision, we aim to infer the underlying cost function that the decision-maker was likely attempting to minimize.

While IO is a powerful tool for understanding human behavior and automated systems, classical IO models possess a significant "Achilles' heel": they assume the observed data is perfectly optimal. In practice, real-world data is noisy, and human decision-makers are rarely perfect optimizers. If an observed solution $x^0$ lies even slightly inside the feasible region (an interior point), classical IO models often become infeasible or return trivial results, such as a zero-cost vector. This paper introduces a robust framework to handle such suboptimality and provides a statistically-inspired metric to evaluate how well an optimization model explains observed behavior.

The Generalized Inverse Optimization (GIO) Framework

The authors propose Generalized Inverse Optimization (GIO) to accommodate noisy observations. Rather than forcing the observed solution $x^0$ to be strictly optimal, GIO seeks the smallest possible perturbation ($\epsilon$) that would render the adjusted point $(x^0 - \epsilon)$ optimal for some cost vector $c$.

Mathematical and Geometric Foundations

One of the paper's primary contributions is the derivation of closed-form solutions. The authors prove that for a general class of these problems, the optimal cost vector $c^*$ is simply a normalized version of one of the vectors defining the problem's constraints. This discovery reduces what could be a complex, nonconvex optimization problem into a straightforward search over a finite set of constraints.

Geometrically, solving a GIO problem is equivalent to projecting a noisy observation onto the boundary of the feasible region. The "best" cost vector is the one perpendicular to the specific face of the polyhedron where the projected point lands. The framework is flexible, offering variants based on different norms (e.g., $L_1, L_2, L_\infty$) to measure error in either the decision space (physical distance) or the objective space (the duality gap).

Measuring Fit: The Coefficient of Complementarity ($\rho$)

To provide a standardized measure of model quality, the authors introduce the Coefficient of Complementarity ($\rho$). This metric is designed to be the optimization equivalent of the $R^2$ metric in linear regression. It quantifies the "proportion of complementarity" satisfied by the model, comparing the error of the best-fit model against a "null hypothesis" (the average error across all possible constraints).

Key properties of $\rho$ include:

  • Boundedness: It is strictly bounded between 0 and 1.
  • Monotonicity: The fit is non-decreasing as more variables or dimensions are added to the model.
  • Quasiconvexity: $\rho$ is a quasiconvex function of the input data, meaning that as an observation moves from the center of the feasible region toward the boundary, the goodness-of-fit naturally increases.
  • Tractability: The authors derive a lower bound ($\tilde{\rho}$) that is even more computationally efficient than the exact metric, enabling real-time model selection.

Applications and Results

The framework was validated across two distinct domains, demonstrating its utility in both industrial and clinical settings.

Aggregate Production Planning (APP)

Using a year of demand and production data, the authors demonstrated how a manager could iteratively refine cost estimates. An initial "managerial guess" for costs yielded a poor fit ($\rho_a = 0.426$). By applying the GIO framework to adjust and relax constraints, the fit improved to $\rho_a = 0.906$, providing a significantly more accurate model for future planning cycles.

Cancer Therapy (IMRT)

In Intensity-Modulated Radiation Therapy (IMRT), the goal is to spare healthy organs while delivering radiation to a tumor. The GIO framework was used to reverse-engineer the weights assigned to different organ-sparing objectives (e.g., bladder vs. rectum) from clinical prostate cancer treatment plans. The model achieved a $\rho$ of $0.948$. Furthermore, the recovered weights were used to generate new treatment plans that closely matched the actual clinical "Dose-Volume Histograms," validating that $\rho$ serves as a meaningful proxy for clinical quality.

Conclusion and Future Directions

This research bridges the gap between optimization and statistics by providing a robust methodology for inverse problems involving noisy data. While the current framework focuses on single observations and linear constraints, it sets the stage for "optimization regression" involving multiple data points. Future work will look to extend these geometric intuitions to conic or general convex problems and further develop the statistical foundations of the $\rho$ metric.

Summary updated

Abstract

The classical inverse optimization methodology for linear optimization assumes a given solution is a candidate to be optimal. Real data, however, is imperfect and noisy: there is no guarantee that a given solution is optimal for any cost vector. Inspired by regression, this paper presents a unified framework for cost function estimation in linear optimization consisting of a general inverse optimization model and a corresponding goodness-of-fit metric. Although our inverse optimization model is in general nonconvex, we derive a closed-form solution and present the corresponding geometric intuition. Our goodness-of-fit metric, $\rho$, termed the coefficient of complementarity, has similar properties to $R^2$ from regression and is quasiconvex in the input data, leading to an intuitive geometric interpretation. We derive a lower bound for $\rho$ that possesses the same properties but is more tractable. We demonstrate the application of our framework for model estimation and evaluation in production planning and cancer therapy.
BibTeX
@article{chan2019goodness,
  author = {Timothy C. Y. Chan and Taewoo Lee and Daria Terekhov},
  title = {{Goodness of Fit in Inverse Optimizaiton}},
  journal = {Manag. Sci.},
  year = {2019},
  doi = {10.1287/mnsc.2017.2992},
}
Figure