Learning Decision-Making Models Via Data-Driven Inverse Optimization

Process systems engineering (PSE) is to a large extent about the development of systematic and efficient tools for decision making, and as a community, we have established such tools in many diverse and complex applications. But we have rarely considered the inverse problem, which is: given decisions made by a decision maker or decision-making system, determine how it arrived at those decisions. This problem arises when one wants to learn about a decision-making process that is unknown. Examples include preference learning [1] and apprenticeship learning [2], which involve human decision makers, but similar questions can be asked about engineered and natural systems designed or evolved to make decisions. Various machine learning approaches have been applied to this problem; however, they typically can only address simple, usually unconstrained problems, where decision-making mechanisms can be modeled using simple decision rules, or require large amounts of data. As a result, they are not suited for complex systems involving many constraints and where obtaining data may be difficult or expensive, such as those common in PSE applications.

In this work, we conjecture that decision-making processes can be naturally modeled as mathematical optimization problems, and apply the concept of inverse optimization [3] to learn such decision-making models from data. We assume that observed decisions are optimal solutions (possibly with some noise) to a parameterized optimization model. Then, the data-driven inverse optimization problem is to determine the model parameters that minimize the difference between the observations and the model predictions obtained from solving the resulting learned optimization model. We formulate the problem as a bilevel program and apply a KKT-based reformulation to obtain a single-level optimization problem. The resulting nonconvex nonlinear problem is solved with an approximate block coordinate descent-based solution method.

The main advantages of the proposed data-driven inverse optimization method are threefold: (i) flexibility, i.e. the capacity to directly incorporate first-principles knowledge and constraints, (ii) interpretability, since clear cause-effect relationships are directly encoded in the model, and (iii) accuracy, as reflected in a high prediction quality relative to the amount of data required. We demonstrate the effectiveness of the proposed approach in computational experiments and show that it frequently, especially in problems involving more complex constraints, outperforms alternative machine learning methods.

References

1. Chu, W. & Ghahramani, Z. Preference learning with Gaussian processes. ICML 2005 - Proc. 22nd Int. Conf. Mach. Learn. 137–144 (2005).

2. Abbeel, P. & Ng, A. Y. Apprenticeship learning via inverse reinforcement learning. in Proceedings, Twenty-First International Conference on Machine Learning, ICML 2004 (2004).

3. Ahuja, R. K. & Orlin, J. B. Inverse optimization. Oper. Res. 49, 771–783 (2001).