Inverse Optimization: Closed-Form Solutions, Geometry, and Goodness of Fit

• 成果类型: Article
• 署名作者: Chan, Timothy C. Y.; Lee, Taewoo; Terekhov, Daria
• 署名单位: University of Toronto; University of Houston System; University of Houston; Concordia University - Canada
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2017.2992
• 发表日期: 2019
• 页码: 1115-1135
• 关键词: Inverse optimization; Goodness of fit; linear programming; MODEL ESTIMATION

摘要

In classical inverse linear optimization, one assumes that a given solution is a candidate to be optimal. Real data are imperfect and noisy, so there is no guarantee that this assumption is satisfied. Inspired by regression, this paper presents a unified framework for cost function estimation in linear optimization comprising a general inverse optimization model and a corresponding goodness-of-fit metric. Although our inverse optimization model is nonconvex, we derive a closed-formsolution and present the geometric intuition. Our goodness-of-fit metric, rho, the coefficient of complementarity, has similar properties to R-2 from regression and is quasi-convex in the input data, leading to an intuitive geometric interpretation. While rho is computable in polynomial time, we derive a lower bound that possesses the same properties, is tight for several important model variations, and is even easier to compute. We demonstrate the application of our framework for model estimation and evaluation in production planning and cancer therapy.