(430c) A Bayesian Optimization Framework for Solving Generic Inverse Optimization Problems

Data-driven inverse optimization (IO) is an emerging method for learning unknown decision-making processes [1]. The fundamental idea is to use mathematical optimization as the model for decision-making, where decisions can be viewed as the optimal or near-optimal solutions to an underlying optimization problem. Given observed decisions made by an agent, the goal of IO is to learn the unknown optimization model that best represents the agent’s decision-making process. The key advantage of the IO approach is that it can directly consider constraints, which allows us to leverage all the modeling flexibility of mathematical programming, incorporate domain knowledge, and hence obtain interpretable decision-making models [2].

An IO problem is typically formulated as a bilevel optimization problem with as many lower-level problems as the number of training data points. Here, each lower-level problem represents the parameterized forward optimization problem (FOP) for a given observed decision, and the objective of the upper-level problem is to find the model parameters that lead to optimal solutions of the FOP which best fit the observed decisions. IO problems are notoriously difficult to solve; common solution approaches include single-level reformulations [3, 4] and cutting-plane methods [5]. The computational complexity is exacerbated in cases where the FOP is nonconvex, which may render a single-level reformulation impossible and a cutting-plane approach inefficient.

In this work, we propose a Bayesian optimization (BO) approach [6] to solving IO problems by treating the lower-level FOPs as black-box functions. The major advantage of BO is that, at each iteration, we only need to evaluate the loss function with fixed model parameter values, which merely requires the solution of the FOP for each data point, as opposed to the solution to a bilevel optimization problem. As a result, BO can be applied even when the FOP is nonconvex. Also, it naturally allows decomposition as the FOPs can be solved independently in parallel. To assess the efficacy of the BO approach for various classes of FOPs, we perform computational case studies wherein we learn cellular objectives in flux balance analysis of metabolic networks as well as planner decision rules in pooling problems. For the flux balance problems, we consider both convex and non-convex objective functions subject to a large number of linear constraints. For the pooling problem, we consider continuous and mixed-integer quadratically constrained programs. The computational experiments show that BO can efficiently identify good estimates of the model parameters within a relatively small number of iterations, especially in cases where the size of the FOP is large relative to the number of model parameters.

References

[1] T. C. Y. Chan, R. Mahmood, and I. Y. Zhu, “Inverse optimization: Theory and applications,” arXiv Prepr. arXiv2109.03920, 2021.

[2] R. Gupta and Q. Zhang, “Efficient learning of decision-making models: A penalty block coordinate descent algorithm for data-driven inverse optimization,” Comput. Chem. Eng., vol. 170, no. October 2022, p. 108123, 2023.

[3] A. Keshavarz, Y. Wang, and S. Boyd, “Imputing a convex objective function,” IEEE Int. Symp. Intell. Control - Proc., pp. 613–619, 2011.

[4] T. C. Y. Chan, T. Lee, and D. Terekhov, “Inverse optimization: Closed-form solutions, geometry, and goodness of fit,” Manage. Sci., vol. 65, no. 3, pp. 1115–1135, 2019.

[5] L. Wang, “Cutting plane algorithms for the inverse mixed integer linear programming problem,” Oper. Res. Lett., vol. 37, no. 2, pp. 114–116, 2009.

[6] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. de Freitas, “Taking the Human Out of the Loop: A Review of Bayesian Optimization,” Proc. IEEE, vol. 104, no. 1, pp. 148–175, 2016.