Introduction
In the traditional paradigm of mathematical optimization, we begin with a well-defined objective function and a set of constraints to determine an optimal decision. This is known as "forward" optimization. However, in many real-world scenarios, the process is reversed: we observe a decision—such as a physician’s treatment plan or a supply chain manager’s production schedule—and seek to uncover the underlying objective function that motivated it. This is the domain of inverse optimization.
While theoretically powerful, classical inverse optimization faces a significant hurdle: it assumes the observed decision is perfectly optimal. In practice, data is often noisy, human decision-makers are boundedly rational, and mathematical models are simplifications of reality. When an observation is even slightly sub-optimal or falls within the interior of a feasible region, classical models often fail, yielding trivial solutions or becoming mathematically infeasible. This paper introduces a Generalized Inverse Optimization (GIO) framework that bridges the gap between optimization and statistical regression, providing a robust method for handling noisy, imperfect data.
The Generalized Inverse Optimization (GIO) Framework
The authors propose a shift from strict optimality to a "best-fit" approach. Instead of requiring the observed point ($x^0$) to be perfectly optimal, GIO introduces a perturbation vector ($\epsilon$). The goal is to find a cost vector ($c$) and a minimal perturbation such that the adjusted point ($x^0 - \epsilon$) is optimal for the given constraints. Essentially, the model minimizes the size of the error ($||\epsilon||$) required to make the observation make sense.
Closed-Form Solutions and Geometry
One of the paper's most significant contributions is the derivation of closed-form solutions for the GIO problem. Although the underlying mathematical formulation is non-convex—typically a barrier to efficient computation—the authors demonstrate that the problem has a beautiful geometric interpretation. Solving for the best-fit cost function is equivalent to projecting the observed data point onto the closest boundary (hyperplane) of the feasible region.
This geometric insight reveals a fundamental truth: the search space for the optimal cost vector is finite. Rather than searching an infinite parameter space, the optimal cost vector will always be proportional to the normal vector of one of the $m$ constraints defining the feasible region. This drastically simplifies the computational complexity of reverse-engineering objective functions.
Measuring Goodness of Fit: The $\rho$ Metric
To make inverse optimization as rigorous as statistical modeling, the authors introduce the coefficient of complementarity, denoted as $\rho$. This metric serves as the inverse optimization analogue to the $R^2$ value in linear regression.
The $\rho$ metric is calculated as: $$\rho = 1 - (\text{minimum error} / \text{average error})$$
In this formula, the "average error" acts as a baseline, representing the expected lack of fit if a cost vector were chosen at random from the constraints. The $\rho$ metric possesses several desirable properties that mirror $R^2$:
- Interpretability: It is bounded between 0 (complete lack of fit) and 1 (perfect fit).
- Monotonicity: Adding more variables or flexibility to the model will never decrease $\rho$.
- Invariance: The metric remains consistent regardless of how the input data is scaled.
Empirical Applications
The authors validated their framework on two real-world applications, demonstrating how GIO can be used for model refinement and variable selection.
Aggregate Production Planning
Using historical data from a production facility, the authors used $\rho$ to test various hypotheses about a manager's internal cost logic. An initial model based on standard assumptions yielded a $\rho$ of 0.426, suggesting a poor fit. By iteratively relaxing constraints—specifically those related to the costs of idle time and regular labor—the authors improved the fit to $\rho = 0.906$. This process effectively uncovered the actual implicit costs driving the historical decisions.
Radiation Therapy for Cancer
In clinical oncology, radiation plans must balance the destruction of tumor tissue with the preservation of surrounding healthy organs. By applying GIO to a prostate cancer treatment plan from the Princess Margaret Cancer Centre, the authors evaluated which clinical objectives were most influential. A baseline model achieved a $\rho$ of 0.737. By incorporating specific mean-dose objectives for the bladder and rectum, the goodness-of-fit jumped to 0.947. Notably, the GIO framework exhibited "natural sparsity," achieving a near-perfect fit using only 7 out of 18 possible clinical objectives, effectively performing automated variable selection.
Conclusion and Future Directions
This research transforms inverse optimization from a rigid mathematical exercise into a flexible tool for data science. By framing inverse optimization as a curve-fitting problem, the authors allow researchers to apply familiar statistical concepts—like model selection and goodness-of-fit—to complex operations research problems.
While the current framework is optimized for single observations within linear polyhedrons, it lays the groundwork for significant future study. Extending these closed-form solutions to handle multiple data points simultaneously and expanding the geometry to non-linear or conic optimization remains a vital frontier. Ultimately, this work provides a robust foundation for understanding the hidden objectives behind human and organizational decision-making.
Summary updated