Inverse Optimization via Learning Feasible Regions

Ke Ren, Peyman Mohajerin Esfahani, Angelos Georghiou · 2025

Read Inverse Optimization via Learning Feasible Regions by Ke Ren, Peyman Mohajerin Esfahani, Angelos Georghiou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15025.txt.

Introduction

Ke Ren and co-authors tackle inverse optimization in 2025, where the aim is to learn why choices were made. A model is fit to pairs of inputs and choices. Most past work learns only the goal function, since learning the constraint set leads to hard, nonconvex training tasks.

The authors focus on that harder half: learning the feasible region when the goal is a known linear one. They offer two training losses and a class that can capture jumps in behavior that goal-only methods miss. A block method with smoothing solves the training tasks, and tighter classes yield convex or mixed integer forms. Tests on synthetic data and two power grid tasks back the method against top rivals.

Catalog record

CREATORKe Ren, Peyman Mohajerin Esfahani, Angelos Georghiou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15025

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Inverse Optimization via Learning Feasible Regions Ke Ren, Peyman Mohajerin Esfahani, Angelos Georghiou Abstract We study inverse optimization (IO) where the goal is to use a parametric optimization program as the hypothesis class to infer relationships between input-decision pairs. Most of the literature focuses on learning only the objective function, as learning the constraint function (i.e., feasible regions) leads to nonconvex training programs. Motivated by this, we focus on learning feasible regions for known linear objectives and introduce two training losses along with a hypothesis class to parameterize the constraint function. Our hypothesis class surpasses the previous objective-only method by naturally capturing discontinuous behaviors in input-decision pairs. We introduce a customized block coordinate descent algorithm with a smoothing technique to solve the training problems, while for further restricted hypothesis classes, we reformulate the training optimization as a tractable convex program or mixed integer linear program. Synthetic experiments and two power system applications, including comparisons with state-of-the-art approaches, showcase and validate the proposed approach. 1 Introduction Inverse optimization (IO) reverses traditional optimization. While classical optimization finds optimal decisions based on predefined objectives and constraints, IO takes decisions as inputs and identifies the objective and/or constraints that make these decisions either approximately or precisely optimal. Interest in IO has surged in recent years, leading to advancements in learning theory ( Aswani et al., 2018 ; Mohajerin Esfahani et al., 2018 ; Chan & Kaw, 2020 ) and recently in reinforcement learning ( Zattoni Scroccaro et al., 2025 ) , as well as applications such as transportation ( Zhang & Paschalidis, 2017 ; Chen et al., 2021 ) , system control ( Akhtar et al., 2021 ) , robotics ( Dimanidis et al., 2025 ) , healthcare ( Ayer, 2015 ; Ajayi et al., 2022 ) , and finance ( Li, 2021 ) . More recently, the IO framework has also been successfully applied to the Amazon Last Mile Routing Research Challenge, where the goal is to learn and replicate human drivers’ routing preferences ( Zattoni Scroccaro et al., 2025 ) . The IO model builds on a parametric forward optimization model that represents the decision-generating process. Given an input signal \bm{s}\in\mathbb{R}^{k} , the following optimization problem defined through f,g:\mathbb{R}^{k}\times\mathbb{R}^{n}\rightarrow\mathbb{R} , generates an optimal solution \bm{x}\in\mathbb{R}^{n} which is observed, however, it is possible that the observation is contaminated by noise. \begin{array}[]{cl}\displaystyle\min_{\bm{x}\in\mathbb{R}^{n}}&f(\bm{x},\bm{s})\qquad{\rm s.t.}\quad g(\bm{x},\bm{s})\leq 0\end{array} (1) In the most general case, decision makers have no knowledge of f and g but have access to N independent pairs of input/decisions \{\bm{s}_{i},\bm{x}_{i}\}_{i=1}^{N} from problem ( 1 ). As the space of all possible objective and constraint functions is vast, the decision-maker seeks to approximate f and g by candidates from some parametric hypothesis spaces f_{\bm{\theta}} and g_{\bm{\theta}} , \bm{\theta}\in\Theta , where \Theta represents a finite-dimensional parameter set. Correspondingly, in IO, decision-makers aim to learn \bm{\theta} such that for each signal \bm{s}_{n} , \bm{x}_{n} is optimal (or approximately optimal) in the following problem: \begin{array}[]{cl}\displaystyle\min_{\bm{x}\in\mathbb{R}^{n}}&f_{\bm{\theta}}(\bm{x},\bm{s})\qquad{\rm s.t.}\quad g_{\bm{\theta}}(\bm{x},\bm{s})\leq 0.\end{array} (2) Through a supervised learning lens, the parameterized model ( 2 ) can be viewed as a hypothesis class for learning the mapping between the input \bm{s} and the output decision \bm{x} generated by the forward optimization ( 1 ). 1.1 Contributions This paper studies the learning problem of IO where, unlike the majority of the literature that focuses on a parametric form for the objective function f_{\bm{\theta}} , the main objective is to learn the constraints function g_{\bm{\theta}} . In this context, the paper has three main contributions: Loss functions compatible with IO data: Generalizing existing literature, we introduce two loss functions \ell_{\bm{\theta}}(\bm{x},\bm{s}) to evaluate model fit ( 2 ) with parameter \bm{\theta} on the input-output data pair (\bm{x},\bm{s}) from ( 1 ) (Proposition 2.1 ). Regarding performance on unseen (test) data, we argue that the IO setting encompasses a “true” counterpart of these losses, unlike general supervised learning problems; see Figure 2 (bottom) for their geometric representation. Hypothesis Classes with Convex and MILP Reformulations: We propose a new hypothesis class to parameterize the constraint function g_{\bm{\theta}} , which is significantly richer than existing IO approaches (Example 3.2 ). However, it results in non-convex training problems. We demonstrate that special cases of this hypothesis class allow the optimization of the training loss \ell_{\bm{\theta}} to be exactly reformulated into tractable convex optimization (Theorem 3.3 ) and mixed-integer linear programs (MILP) (Proposition D.1 ), which can be solved efficiently with off-the-shelf solvers. Smoothed block-coordinate descent algorithm: We further exploit the structure of the proposed losses and devise a tailored block coordinate descent algorithm together with a smoothing technique to train our IO setting in for the generic hypothesis class (Algorithm 2 ). The smoothing technique provides an interesting insight into the relation between the two proposed loss functions, justifying why one often presents better computation results when optimized using vanilla gradient descent (Algorithm 1 ); see Remark 3.4 . The paper is organized as follows: Section 2 introduces two losses and explores their properties. Section 3 presents the hypothesis class together with the proposed coordinate descent algorithm with a smoothing technique to solve the general problem, along with convex and MILP reformulations for specific cases. Section 4 covers computational studies. Limitations and future work are discussed in Section 5 . Proofs and additional computational studies are in the appendix. 1.2 Related Works Extensive studies have been carried out to estimate the objective functions in data-driven IO. The various approaches primarily diverge in terms of the loss functions utilized to capture the disparity between predictions and observations. These include the KKT loss ( Keshavarz et al., 2011 ) , first-order loss ( Bertsimas et al., 2015 ) , predictability loss ( Aswani et al., 2018 ) , and suboptimality loss ( Mohajerin Esfahani et al., 2018 ) . The properties and relationships of these approaches are summarized ( Mohajerin Esfahani et al., 2018 ) . Other methodologies are also proposed under different settings including online settings ( Bärmann et al., 2017 ; Dong et al., 2018 ) . In the landscape of IO for feasible regions, the majority of existing works have traditionally concentrated on right-hand side parameters ( Dempe & Lohse, 2006 ; Güler & Hamacher, 2010 ; Xu et al., 2016 ; Saez-Gallego et al., 2016 ; Lu et al., 2018 ) . However, recent endeavors by ( Aswani et al., 2018 ; Tan et al., 2020 ; Ghobadi & Mahmoudzadeh, 2020 ) have expanded the scope by considering various aspects of constraint parameters. The work ( Aswani et al., 2018 ) incorporates general constraint parameters into their model, departing from the mainstream. However, their model encounters intractability issues, relying on enumerations to evaluate the problem. Similarly, ( Tan et al., 2020 ) faces tractability challenges, employing sequential quadratic programming within a bi-level optimization framework for solving constraint parameters in linear programming. While ( Chan & Kaw, 2020 ) and ( Ghobadi & Mahmoudzadeh, 2020 ) propose tractable solutions, their settings impose some restrictions: ( Chan & Kaw, 2020 ) does not consider a data-driven setting and confines their analysis to a single observation in linear programming. The paper ( Ghobadi & Mahmoudzadeh, 2020 ) extends this limitation to multi-point scenarios, but only for the linear programming case where the

Read the complete text