(712e) BO4IO: A Bayesian Optimization Approach to Inverse Optimization with Uncertainty Quantification

Data-driven inverse optimization (IO) aims to learn the unknown optimization model that best represents a decision-making process [1]. A data-driven IO problem (IOP) is typically formulated as a bilevel program, featuring as many lower-level problems as there are observations. Each lower-level problem represents the parameterized forward optimization problem (FOP) for a given observed decision, and the upper-level objective is to find the optimal FOP parameters that minimize the decision loss between predictions and observations. Existing solution approaches involve single-level reformulations [2, 3], cutting plane algorithms [4], or tailored decomposition methods [5, 6]. However, these exact solution methods cannot be applied to all classes of IOPs, and designing such algorithms becomes particularly challenging when the FOP is nonconvex.

In this work, we propose a Bayesian optimization framework for solving general IOPs [7], which we call BO4IO. We treat the loss function of the IOP as a black box and approximate it with a non-parametric probabilistic surrogate using Gaussian process (GP) regression [8]. It looks to converge to the optimal parameter estimates that provide the minimum decision loss by iteratively selecting candidate solutions through the maximization of an acquisition function. Here, the key advantage of BO4IO is that, at each iteration, it only requires the evaluation of the loss function with the current parameter estimates; this can be achieved by directly solving the FOP for every data point, which circumvents the need for a complex reformulation or special algorithm. Consequently, BO4IO remains applicable even when the FOP is nonlinear and nonconvex, and it can consider both continuous and discrete decision variables.

BO4IO also enables us to address another major challenge in IO that is often overlooked, namely the quantification of uncertainty with respect to the estimated parameters. In IO, there are often multiple parameter estimates that lead to the same loss; these “equally good” estimates form the so-called inverse-feasible set, of which the size can be viewed as a measure of uncertainty. A common approach to uncertainty quantification in parameter estimation is to derive sample-based confidence intervals for the point estimates based on the profile likelihood method [9]. We find that in BO4IO, we can use the posterior of the GP surrogate to approximate the profile likelihood, which provides uncertainty quantification and insights into the identifiability of given model parameters.

To assess the efficacy of the proposed BO4IO approach, we perform computational case studies covering various classes of FOPs from convex nonlinear to mixed-integer nonlinear and nonconvex programs. The computational experiments demonstrate that BO4IO can efficiently identify estimates of the unknown model parameters with a relatively small number of iterations. In addition, using the approximate profile likelihood, we can assess how the identifiability of certain parameters changes with the number and quality of observations.

References

[1] T. C. Y. Chan, R. Mahmood, and I. Y. Zhu, “Inverse optimization: Theory and applications,” Oper. Res., 2023.

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

[3] 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.

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

[5] R. Gupta and Q. Zhang, “Decomposition and Adaptive Sampling for Data-Driven Inverse Linear Optimization,” INFORMS J. Comput., no. August, 2022.

[6] 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.

[7] 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.

[8] C. E. Rasmussen and C. K. I. Williams, “Gaussian Processes for Machine Learning.” The MIT Press, Nov. 23, 2005.

[9] A. Raue et al., “Structural and practical identifiability analysis of partially observed dynamical models by exploiting the profile likelihood,” Bioinformatics, vol. 25, no. 15, pp. 1923–1929, 2009.