Inverse Optimization via Learning Feasible Regions
Authors: Ke Ren
Peyman Mohajerin Esfahani
Angelos Georghiou
Venue: ICML 2025 poster (2025)
Keywords: Inverse Optimization
Non-convex Optimization
Data-driven Optimization
Primary area: optimization->everything_else

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.

Inverse Optimization via Learning Feasible Regions
Ke Ren' Peyman Mohajerin Esfahani?
Angelos Georghiou
Abstract
2021), roboties (Dimanidis al., 2025), healthcare (Ayer, 2015; Ajayi et al., 2022), and finance (Li, 2021). More recently, the IO framework has also been successfully ap- plied to the Amazon Last Mile Routing Research Challenge, where the goal is to learn and replicate human drivers' rout- ing preferences (Zattoni Scroccaro et al., 2025).
We study inverse optimization (IO) where the
goal is to use parametric optimization program as the hypothesis class to infer relationships be- tween 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, focus learning feasible regions for known linear objectives and introduce two training losses along with a hypothesis class to parameterize the constraint function. Our hy- pothesis class surpasses the previous objective- only method by naturally capturing discontinuous behaviors in input-decision pairs. We introduce customized block coordinate descent algorithm with a smoothing technique to solve the training problems, while for further restricted hypothe- sis classes, we reformulate the training optimiza- tion as a tractable convex program or mixed in- teger linear program. Synthetic experiments and two power system upplications, including compar- isons with state-of-the--e approaches, showcase and validate the proposed approach.
The IO model builds on parametric forward optimiza- tion model that represents the decision geeeeiatnnggnn process. Given an input signal E H the following optimization problem defined through J g : IR x I" + R. generates an optimal solution æ E IR" which is observed. however, it is possible that the observation is contaminated by noise.
min 22 EER"
f(x,)) s)
s.t. g(x, 8) S 0
(1)
In the most general case, decision makers have no knowl- edge of f and g but have access to N independent pairs of input/decisions {s } from problem (1). As the space of all possible objective and constraint functions is vast, the decision-make maker seeks to approximate f and by candidates from some parametric hypothesis spaces fo and ga. O E O, where represents a fimteedimeesional parameter set. Cor- respondingly, in IO, decision-maker aim to learn such that for each signal sn, F, is optimal (or approximately optimal) in the following problem:
1. Introduction
min #ER"
fo 8)
s.t.
go g0 8) S 0.
(2)
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 op- timal. Interest in IO has surged in recent years, leading to advancements in learning theory (Aswani et al., 2018; Moha- jerin Esfahani et al., 2018 8; Chan & Kaw, 2020) and recently in reinforcement learning (Zattoni Scroccaro et al., 2025), as well as applications such transportation (Zhang & Pascha- lidis, 2017; Chen et al., 2021), system control (Akhtar et al.,
Through supervised learning lens, the parameterized model (2) can be viewed as a hypothesis class for learning the mapping between the input s and the output decision 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 fo. the main objective is to learn the constraints function go. In this context, the paper has three main contributions:
Amazon University of Toronto and Delft University of Tech- nology University of Cyprus. Correspondence to: Ke Ren <renkea@ amazon.com>.
Loss functions compatible with 10 data: Generalizing existing literature, we introduce two loss functions Eg (æ, s) to evaluate model fit (2) with parameter on the input- output data pair (z, s) from (1) (Proposition 2.1). Regarding performance on unseen (test) data, we argue that the 10
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Inverse Optimization via Learning Feasible Regions
setting encompasses a "true" counterpart of these losses, unlike general supervised learning problems; see Figure 2 (bottom) for their geometric representation.
The work (Aswani et al., 2018) incorporates general con- straint parameters into their model, departing from the main- stream. However, their model encounters intractability is- sues, relying on enumerations to evaluate the problem. Sim- itarly, (Tan et al., 2020) faces tractability challenges, em- ploying 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 solu- tions, their settings impose some restrictions: (Chan & Kaw, 2020) does not consider data-driven setting and confines their analysis to 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 multiple points are merely feasible solutions, not necessarily optimal.
Hypothesis Classes with Convex and MILP Reformula- tions: We propose a new hypothesis class to parameterize the constraint function go. which is significantly richer than existing IO approaches (Example 3.2). However, it results in non-convex training problems. We demonstrate that spe- cial cases of this hypothesis class allow the optimization of the training loss tg to be exactly reformulated into tractable convex optimization (Theorem 3.3) and mixed-integs integer linear programs (MILP) (Proposition D.1), which can be solved efficiently with off-the-sheff solvers.
Smoothed block-coordinate descent algorithm: We fur- ther exploit the structure of the proposed losses and devise a tailored block coordinate descent algorithm together with 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.
2. Learning Frameworks
Inverse optimization as supervised learning. From a ma- chine learning perspective, the 10 problem can be cate- gorized as a supervised learning problem, where repre- sents the independent variable and represents the response. Therefore, it is natural to define loss minimization proce- dure (as shown in (3)) to find the unknown parameters O.
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 reformu- lations for specific cases. Section 4 covers computational studies. Limitations and future work are discussed in Sec- tion 5. Proofs and additional computational studies are in the appendix.
N to (zi 8.).
min
Σ
(3)
N
An appropriate loss required to measure both the feasibil- ity and optimality of any given solution xc
2.1. Loss Function
1.2. Related Works
In this section, we introduce two loss functions that relax feasibility and optimality in problem (2) while penalizing deviations. Two potential reasons why problem (2) might fail to replicate the feasibility and optimality of problem (I) are: (i) the hypothesis class used for the constraints ge and/or the objective So may lack the complexity to capture the behavior of (1), and (ii) the training data could be noisy, meaning the signal and/or the decisions æ may be influ- enced by unaccounted measurement noise. Typically, the degree of infcasibility of data point can be quantified by go (æ. s), with positive values indicating infeasibility, while suboptimality can be assessed via
Extensive studies have been carried out to estimate the ob- jective functions in data-driven IO. The various approaches primarily diverge in terms of the loss functions utilized to capture the disparity between predictions and observa- tions. These include the KKT loss (Keshavarz et al., 201 1),, first-order loss (Bertsimas et al., 2015), predictability loss (Aswani et al., 2018), and suboptimality loss (Mohajerin Eis fahani et al., 2018). The properties and relationships of these approaches are summarized (Mohajerin Esfahani et al., 2018). Other methodologies are also proposed under dif- ferent settings including online settings (Bärmann et al., 2017; Dong et al., 2018). In the landscape of IO for feasi- ble regions, the majority of existing works have tradition- ally 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, re- cent endeavors by (Aswani et al., 2018: Tan et al.. 2020: Ghobadi & Mahmoudzadeh, 2020) have expanded the scope by considering various aspects of constraint parameters.
min WER" s.t.
fo( 8) go( <0
]. (4)
Jo 8) = so(
For a fixed 0, Jo(x, 8) quantifies the difference between the objective value achieved by data point (I, s) under the hypothesized objective fe s) and the optimal value of (2) with signal 8. In frise-free scenarios, negative Jo (ax, s)
2

---

Inverse Optimization via Learning Feasible Regions
suggest over-constraint in (2), while positive values imply overly relaxed feasibility, rendering (ac, s) suboptimal.
0 E O and (ar, 8) in the training dataset, the loss (ar,, 8) is zero if and only if is also optimal solution of (2). In other words, given rich enough hypothesis class for ge and fe, the set of optimal solutions of (2) coincides with the set of observed optimal solutions of (1). Moreover, the statement implies that if the optimizer 0 of (3) does not achieve zero loss, i.e., there exists (æt, 8) in the training data such that Lg- (x, s) O, then there is no other in the hypothesis class that perfectly describes the measured pair (æ,, 8). We term this property as full characterization.
The loss functions are termed predictability and suboptimal- ity loss, respectively.
min s.t.
|| Y E R.
(3r, =
(5a)
g + 8) S 0 (0 7, 0
min
[1(T5:
Proposition 2.1 (Full characterization). For any 0 O and the 10 data pair (æ, s) generated by the forward model (1), both predictability fg fg(ar, s) and suboptimality eigh (ax s) loss defined in (5) satisfy
pau (x, 8)
s.t.
No: 7f E R+ g0 (0 xx < 7
(5b)
Jo 8) S %
Figure illustrates the two loss functions. The variable (red) in the predietability loss (²(2x,) 8) allows for reposi- tioning the observed æ to achieve feasibility and optimality while penalizing the extent of adjustment. Note that Y doesn't merely project into the feasible region go(:; s) but balances between infeasibility and suboptimality. In the suboptimality loss (a s). 7/ and To (light blue) act
arg min MERe s.t.
Soly, 8)
f0 8) =0 + x E
2o S
2.2. Measuring Performance
as slack variables, regulating the levels of infeasibility and suboptimaliit independently.
In this subsection, we define metrics for the goodness of fit in an out-of-sample evaluation. In general, there are two ways to measure the performance. The first method is to directly measure the feasibility and optimality of the opti- mal solutions generated by learned optimization problems. To this end, for fixed O' E O, define zg)(s) to be an op- timizer from problem (2). Thus we evaluate the true loss Ene Non (( (8:), s,) using the true predictability loss
-fo(,s s)
(a s) = |r ea (x, a) [1 %)ll
%
min || Y E R
30l:88 8) S 71 (0(
s.t.
((x
(6a)
9e(-,8) 0
g(x + 7. s) < 0 J(x + 7, 00
%0 sola,
fo(z, 8) fo((x((5).))
and true suboptimality loss
min
Figure I. Pictorial representation of the predictability and subopti- mality loss functions.
gaub (x, 8) =
s.t.
No E 1 Y3 E RR+ g(x, 8) S 7
(6b)
Jar 8) S %
The predictability loss was first proposed in (Aswani al., 2018) using slightly different formulation. The nam- ing convention can be explained by defining variable y + Y, where y shifts æ, leading to the objective func- tion mingex'(e), lly - æ=|. Here, X'(s) denotes the set of optimal solutions of problem (2). Consequently, the loss penalizes the discrepancy between the observed decision æ and the potential predicted decision y. Unlike the loss pro- posed in (Mohajerin Esfahani et al., 2018) which assumed known constraints, the suboptimality loss extends the loss to unknown constraints penalizing both infeasibility and suboptimality.
In most practical scenarios. we do not have access to the forward problem (1), preventing a direct evaluation of the true performance of O. Nevertheless, we often have addi- tional data {(z,, s;)) N that was not utilized during the training phase. As an alternative, we can straightforwardly compute Σ (xx s;) for a selected 0' E θ for both the predictability and suboptimality loss functions. We il- lustrate the relationships between these four metrics below in Figures 2. From Figure 2 (bottom), it can be seen that if the recovered optimal solution 2e coincide with the observed optimal æ;, all losses become zero. Additionally, the true predictability loss e and cumple-based loss lg are equivalent when optimal solutions are unique for both true
The following proposition shows that the proposed loss functions (5) are well defined, in the sense that for any
3

---

Inverse Optimization via Learning Feasible Regions
and recovered problems. It is also worth noting that the true suboptimality loss coincides with the "Smart Predict, then Optimize" (SPO) loss in (Elmachtoub & Grigas, 2022); see Remark 4.4 in (Zattoni Scroecaro et al., 2024) for more details.
can see that the constraint go (2r, 8) S 0 can be reformulated to Ao(s)z + (s), 2. In other words, for each pair (æ, 8) there exists z E Z that maps to æ through the linear map
Hence, through the choice of O the matrix Ao (8) can scale, rotate and project the primitive set Z, while vector bo(s) is responsible for translating the set. An alternative way to view the hypothesis that the learning model induces the policy x(s) (s)s)=(s) + (s(s) for some (s)) Z, hence problem (2) aims to learn the policy that best fits the training data. The choice of the primitive set 2 plays a crucial role in approximation highlighted in the next remark.
-fo(,.)
Ool: s) S
71
ot, a) s by s)
Remark 3.1 (Choice of primitive sets). When the primitive set Z is a p-dimensional simplex, the resulting policy can be seen as a switched version of p different policies, each represented by a column of Ao(s). The latent variable z; (s(s) acts as the switching mechanism. More broadly, the matrix Ag As(s) projects the high-dimensional simplex (or any other polytopic primitive set) onto the space of x. Increasing the dimensions of the primitive set enhances the flexibility of the hypothesis class. Conversely, if the constraints of the forward problem (1) are believed to be ellipsoidal, an appropriate choice is Z {z E TR. ||=||2 S 1}, with Ao (s) rotating and scaling the set accordingly.
1o M(za(s). s) [(ro(s)) 6) (((,.))
((zo(s), 6) 1->ll- = (g(,,s) (zo(s),)) ((.9 n-)1l
f6, 8)
so(:s)
c (x. 8)
goob (2)()) s)
The following example illustrates the richness of the 10 models with the constraint class (7) by demonstrating (i) how it can learn a forward problem with discontinuous policy, and (it) why no IO model with only objective learn- ing (e.g.. (Mohajerin Esfahani et al., 2018)) is sufficient to achieve the same.
8 (zo(s), 8) (2)2)))
(
Figure 2. Top: Pictorial representation of true predictability and suboptimality losses. Bottom: relationship between estimated outple loss (Eg. (agh) and true out-of-sample loss (f", gath).
Example 3.2 (Constraint vs. objective learning in IO). Mo- tivated by power systems, consider
3. Hypothesis Class for ge and Reformulations
88 + (1 - s))2 s.t. I1 + x2 arE 2
min
(8)
In this section, we restrict the admissible constraint func- tion de to a specific hypothesis class and reformulate the predictability and suboptimality losses. For the remainder of the paper, we assume the objective function is known and focus on the unknown constraints.
where Ti and d2 represent two generators output aiming to meet the demand 2 + 22 = 1 at the lowest possible cost. The signal s [0, 1] indicates the per-unit production cost of the first generator, while the cost of the other is proportional to 1 - 8. The optimal policy of (8) is
Let As(s) and (s) be matrix and vector with appropri- ate dimensions, and restrict the constraint to
(1,0)
ifs < 0.5,
(5)) =
(10,1), 1))
if = 0.5,
(9)
go (x, s) = min œ Ae(s) - (s)]
(7a)
10.
if > 0.5,
The function uses latent variable z, which resides in the predetermined conic primitive set
such that =0.5) + zz(0.5) 1. The hypothesis class (7) can recover the optimal policy by defining Z ={2 10. : e = 1} the evo-dimensional unit simplex, and selecting Ao(s) = I (the 2 x 2 identity) and bo(s) = O such that the resulting policy yields x1 21(s) = 21(s) and 22(3) = 22(s). Selecting 2 (s) and (2) as in (9) sat- isfies Z by construction. and recovers the optimal pol- icy. However, attempting to learn a quadratic function
==
Hz - h E KC}
(7b)
where matrices H E TRIPP and h E R² and the proper convex cone K.' are given.
Intuitively, the hypothesis class (7) controls the feasible region of x by manipulating the primitive set 2. Indeed, we
4

---

Inverse Optimization via Learning Feasible Regions
fo( 8) x T0x xx Ags results in the linear policy 1) while saturating at the boundary for any 0 or = 1, indicating that learning a quadratic cost is indeed insufficient to capture the optimal policy.
of constraint æ + Ao(s)= + bs)s), and 1² the opti- mal dual multipliers of constraint c(s) Ao(s) + A H 0. The gradient of the loss function is
2ss) = 20 Ags for any E (0,1)
Cg(x, s) sy aA
Ak= = O..... K
(11)
3.1. Reformulation for Linear Objective Functions
where so = 1. In practice, the step size r of the gradient descent can by dynamically updated at each iteration by performing backtracking such as Armijo's rule or other criteria.
For the remainder of the paper, and without loss of gener- ality, we make the assumption that we can express As(s) and be (s) as affine functions of s through As(s) = Ao + A|51 +...+ AKSK and by (s) = by + b1s1 +....... .....+bbre bKoK where A& E Raxp and by E IF" for k O...., K, i.e., 0 ({As, bx) The following theorem provides the reformulation for the learning problem (3).
Algorithm Gradient descent based algorithm for (10) us- ing predictabilityy loss
1: Initialization: { T,
T.n. m.. t = 1;
Theorem 3.3 (Exact reformulation). Let fo(zz c(s) a and go given in (7). The learning problems can be reformulated as follows, using the predictability loss
while t - T do
3: Solve (10) and denote by ( (1,11))))) the opti-
mal solution and dual multipliers.
4: A A
>i su( -
N
5: +
min
Im:ll
N
6: end while
s.t.
A E RTxp, by E R", Vk < K,
% E R", 2, EERO X; K
2; + 7= =Ao(8:)z; +bb))i+bb()))) (8:)
3.2. Adaptive Smoothing
Hz, - -hEK
ViS N
One can inspect that the optimum of these programs (10) is typically a nonsmooth function in the variable [A due to the inner optimization over the multiplicative decision variable { This observation motivates us deploy smoothing techniques (c.g.. Nesterov's 's smoothing (Nesterov et al., 201 8)) to improve our algorithm performance. With this in mind, the next remark provides a connection between the two optimization programs (10) (i.e., predictability vs suboptimality loss), which intuitively sheds light on why the suboptimality loss has often better numerical performance from computational viewpoint, see numerical experiments in Table 1 and more details in Appendix H.2.
c(s;) As(s:)= A1 11 00
)
c(s;) (I; + 7/- -a--bo bo - X h 5
(10a)
and using the suboptimality loss
N
1
min
N
A Raxp, by E ER, Vk & K,
Mf. Yo. E RR, 7/8 E RR", zi E EP
2 + 7/ = =o(ss)z; + -b((s))
1T/ S71
Vi V
Hz: -h hEK,AiEN
Remark 3.4 (Suboptimality loss as smoothed predictabil- ity loss). Consider the suboptimality problem (10b). The feasibility variable T, of (10b) coincides with Nesterov's 's smoothing counterpart (Nesterov, 2005) of the predictability objective function in (10a) when the distance function is con- sistent with the underlying norm in these programs with an appropriate smoothness parameter. We refer to Appendix E for the details to formalize this discussion.
c(s:) Aa(s:) X H
c(s:) ( bs:):) - A7 h %0.5
(10b)
Both problems (10) share similar complexity in the sense that the constraints are linear except for the bilinear term Ae (s) The problem can be efficiently approximated in practice by performing block coordinate descent (Bert- sekas, 1999) on matrices {Ax] and vectors {z: [ sequentially until convergence. The gradient descent-basee algorithm for the predictability loss in (10) is outlined in Algorithm 1. A similar algorithm can be derived for the sub- optimality loss. It updates {A with gradient descent and solves (10) to compute { for fixed {Aa} JKK The gradient of the predictability loss (10) with respect to {AA o is as follows: For some (z, s), denote x as the optimal latent variables, 9" as the optimal dual multipliers
Inspired by Remark 3.4, we define smoothed predictability by relaxing the hard constraint involving {Ax K and pe- nalizing them in the loss function. This is formally defined in the next definition (suboptimality loss follows the same logic and will be presented in Appendix E). For clarity, we assume fo fz s) c(s) and go as given in (7).
Definition 3.5 (Smoothed predictability loss). The e- smoothed counterpart of the predictability loss (10a) is de-
5

---

Inverse Optimization via Learning Feasible Regions
fined through the optimization program
We illustrate the difference between Algorithms 1 and 2 through noiseless example where the true hypothesis class is covered by the primitive set. The final results are reported in Table I; see also Appendix H.2 for further related details. It is worth mentioning that when using the vanilla gradient decent Algorithm 1, the suboptimality loss has much bet- ter performance (since it has better smoothness), whereas leveraging the smooth counterpart of Algorithm 2 achieves competitive performance with both loss functions (see also Figure 5 for more details concerning the relevant statistics).
min
1
Σ
7all
t
n Σ
1 c2
7
N
s.t. A 1=1
i=1
E Rx by: ER, Vk = I....,K, K,
E R", 2: ER, E K
E + 7/1 = =o(ss) + bo(s:) + 7Ysl
Hz:- - h
Vi N.
c(s;) (x; + Y: - -bo(s:) - h 50
c(8:) Ag(s:) - X; H + 7a2 =
(12)
In order optimize the smoothed losses (12), choose to adaptively increase the penalizing coefficients (2),
Table 1. Training loss of Algorithms and 2 on different losses, where the global optimal is zero
This allows the magnituee of the slack variables Ya1 and %/2
loss
Alg 1
Alg 2
to diminish to zero, thus solving the original predictability loss in (10). With this in mind, we present the final algorithm in Algorithm 2.
Predictability
1.90 + 0.36
(2.5 + 7.2) 10
Suboptimality
0.03 + 0.05
(8.6 + 2.1)
10-4
Algorithm 2 Adaptive smoothing algorithm
3.3. Convex and Mixed-integer Reformulations
1: Initialization: { T, n, t = 1, and c2 for
predictability loss;
In this section, we discuss choices of go for which prob- lems (10) can be cast as convex or mixed-integer programs which can be solved using off-the- ( = a R4,, i.e., 0 (a, (bx ) will achieve convex reformulation. This approximation only allows for scaling and translation of the primitive set Z and does not permit rotation or projection. The following proposition provides the convex reformulation of the predictability loss. The suboptimality loss can be reformulated a similar way.
2: while S T do
3: Solve (12) and denote by {27, ,i Y. Y LNN the optimal solution, dual multipliers, and smoothing variables.
solvers. Restricting
4: A A 1 (x(((s:) T)
5: Re-solve problem (12) to get new values of 11 6: If the change in En I1 E She is small enough, increase the value of ej 62.
Proposition 3.7 (Tractable convex reformulation). Let fo 8) = c(s) T x and ge defined in (7) with As(s) = a E R.,, and 0 (a,, (o)) Then, the predictability loss (10) can be reformulated as the convex optimization
7: t= 1.
8: end while
We use simple updating rules for adjusting (e), 62) in Algo- rithm 2: The initial values are E1 E2 1, and every time the change in the values of EN
1 N
min
Σ Iml
N
i=1 |1a 2 and Σx ls I|? are less than 0.01/ 11000100000/ (eg (+)) we multiply the parame- ters E and E2 by 2.
N
s.t. a..cC
R4, by E ER" VK S K,
%i E Rh, Si GERP RR A
2; + Y: = bo(:))
The convergence property of Algorithms and 2 is formally summarized in the following proposition.
HQ: ah EK
Vi S N.
ac(s;) T - -X, HT =0
Proposition 3.6 (Convergence),, Let 0- = K where (= is the outcome of Algorithu (Algorithm 2, re- spectively) after I iterations with the Armijo rule step- size, and {= be the solution of the proposed pre- dictability or suboptimality loss function defined in (10) (the smoothed version (27) in Section E.1 in the supplemen- tary, respectively) when the matrices As are set to the pro- posed algorithm outcome. Then, the loss function value is monotonically decreasing, ie., for any pair (a, s) we have Eg (x, 8) 2 Eg (2, 8) 2 O, and hence, it convergences to a finite nonnegative value (local optimal).
c(s,) (I. + 7/s bo(ss)) - X 5
(13)
The auxiliary variable Ç replaces az in constraints x + az + b(s) and Haz ah E K. where the latter stems from multiplying Hz h K. by E R4- Despite its limitations, this choice of hypothesis class can enhance computational efficiency for large-scale problems.
Restricting either 2 or Ap(s) to be binary, allows to refor- mulate the bilinear term (s)x using linear inequalities (McCormick inequalities) and formulating the problem as
6

---

Inverse Optimization via Learning Feasible Regions
mixed-interge linear program. The application domain will dictate which of the two will be binary, with two inter- esting examples emerging. For the first, notice that setting Zoin := 2 n {0, 1)" constitutes a restriction to the hypoth- esis class. The next observation provides conditions under which the restriction to the integer Z is done without loss of optimality.
ing and Nes = 200 data points for testing, by generating
signals uniformly at random from si [0.2, 11. x2
[0.2, 0.5], sgme E [1, 2] and st sqemand [0.3, 1.5,, $2
demund E
[0.36. 1.8), $3 sqemand E. [0.42, demand E [0.48, 2.4] and
domand E [0.54, %
and solving problem (14) to obtain
pairs {s,, z; i= 1N=100 Notice that the flow decisions fm are treated as lurking variables and are not observed.
Observation 3.8 (Discrete vs. continuous primitive sets). TTx x and ge given in (7) with Zoin eTz = 1}, and let 0" be the optimal
Let fe 8) = =c())
4.1. Problem 1: Inferring Generation Policy without Knowing Constraints
{ E {0, value of problem (10) using the predictability loss. If c(s)T AoTTAg((g (s) is not parallel to any of the facets of the simplex for all 8, then the optimal value of the problem will coincide with the optimal value of the predictability loss problem (10) where 2 (= E Rd_ e =1.=
In the first experiment, we assume the decision-maker is aware of the objective function of the forward problem but lacks knowledge of the constraint's structure. This scenario intuitively represents a situation where decision-makers aim to minimize total costs without being aware of any spe- cific business rules. We compare four policies: (i) We use the hypothesis (7) where 2 is the unit simplex of di- mension p E {3, 6, 9} using the Adaptive Smoothing Al- gorithm 2 with limit of 3000 iterations, (tt) we use the convex formulation discussed in Section 3.3 using the unit simplex of dimension p = 3. (iit) we compare against the linear policy induced by learning the quadratic func- tion fe (ax, s) = x Qeæ + x Ags, see Example 3.2, and (iv) we use the hypothesis (7) where Z is the unit sim- plex of dimension p E (3, 6,9) and solve problems (10) using the non-convex quadratic solver of Gurobi v1 v11.0.3 with a time limit of 1800 seconds. We note that pol- icy (dit) will coincide with the linear regression policy minøeo Enen ||æ; (s:) - bø (o(s)))ll since the con- straints of the problem are assumed unknown. For all meth- ods, we solve both the corresponding predictability and sub- optimality loss problems. Table 2 shows the out-of-sample performance of each method using the predictability 4g and suboptimality egub losses, as well as the true predictability @ and suboptimality guub losses. As discussed in Section 2.2. by definition eg = EP. We observe the following: (i) The convex formulation is the most computationally efficient but may yield lower quality solutions compared to other meth- ods. (di) Learning quadratic cost is significantly inferior to other methods. (dit) Increasing the dimension p of the unit simplex enhances the hypothesis class flexibility, improving out-of-sample performance for both the predictability and suboptimality loss. (iv) Algorithm 2 performs significantly better compared using Gurobi in almost all cases, par- ticularly the most complex ones. We further investigate the performance of the proposed approach using the larger IEFE 14-bus system (I (Leon& et al., 2020). The results are presented in Appendix F.
For the second case, assume that ge given in (7) with As(s) A [-1,0, O, 1]axp and (s)s) O + R for all 8. This choice of the hypothesis class can be useful for learning equality constraints, for example, learning the phys- ical links in a network where A dictates the connectivity of the network. Notice that the number of binary variables needed for the reformulation of the problem independent to the size of the dataset. We will see an example of this hypothesis class used in Section 4.2 to learn the structure of power network.
4. Numerical Experiments
We apply our methods on an instance of a power system de- scribed (Bampou & Kuhn, 2011). Both problems have the same forward problem, i.e., network flow problem with the following formulation. We consider a power system consists of set of regions R = {1,- 5) with electricity demands st ddemand E R. Demands are satisfied by set V = {1, 2, 3 of power plans, where each plant n E / produces on units of energy at costs s Regions are con- nected by a set M = [1,-.., 5) of directed transmission lines. Each line m E . has a capacity of fm units of energy. A pictorial representation of the network is given in Figure 3 (top).
The forward problem is formulated as follows where (r) denotes the set of generators in node r, with (+) and M_ (r) denoting the sets of incoming and outgoing flows from node r, respectively.
min S.t.
goost T
xc
In E R4,, In S On, AN,
fm R. 15ml S sm, Vm M,
(14)
EneN(e) In + EmeM-(r) I' Emem (r) s' + o gdemnnd Vr R.
4.2. Problem 2: Learning Power Network Structures
In the second experiment, we assume the decision-maker knows the capacity constraints and demand locations but
We set Cn = 3.5 for all n E N and fm = 3.5 for all
m E M. We generate Niain = 100 data points for train-
7

---

Inverse Optimization via Learning Feasible Regions
Table 2. Summary of out-of-sammpl performances.
demaadd
demaadd
Hypothesis Class and Loss
Evaluation methad
loss
Eg
g
time
3
predict.
3.20
0.17
0.83
569.0s
Alg 2.p =
fi
subopt.
5.50
0.18
2.45
430.8s
predict.
1.91
0.05
0.51
1159.6s
$2
cost
Alg 2.p 6
subopt. 1.50
0.03
0.42
754.1s
predict. 1,58
0.05
0.69
591.7s
Alg 2,p= =
subopt. 1.61
0.04
0.50
590.6s
denaadd
Gemaand
demandd
5
Convex, = 3
predict. 3.36
2.07
0.34
0.31s
Original Network
subopt.
10.75
0.31
7.72
0.15s
quadratic cost
predict.
2.58
2.56
0.63
2.54s
deraaadd
denaard
2
predict.
6.32
4.44
0.49
1800s
Gurobi p 3
subopt.
3.36
0.05
1.30
1800s
predict.
6.54
4.31
0.76
1800s
Gurohi p = 6
predict.
subopt. 7.76
6.66
0.15
4.25
0.77
4.96
1800s
1800s
fa
f1
f
23
Gurohi p 9
subopt.
11.00
4.63
5.19
1800s
x2
fz
unaware of the transmission line positions. The goal is to recover the network structure using inverse optimization, in effect learning the last constraint of problem (14). In network with 5 nodes, there are 10 possible transmission line connections, and we aim to identify the configuration that best fits the data. Using the same experimental setup as the previous example, we treat the flow decisions as latent variables. Leveraging the structure of (7), we can re-express the policy a=)) Ao(s)=(( + bo (s), 2s) Z as the following 5 constraints, each corresponding to node in the network
demand
slemaadd
demand
%g
$4
$6
Recovered Network
Figure 3. Top: Power network topology used in the forward prob- lem in Section 4. Bottom: Recovered network from inverse opti- mization in Section 4.2.
even with 4 lines, the recovered problem is able exactly match the observed data and achieve zero loss. Finally, we compare our approach with the state-of-the-an method for learning problem constraints proposed by (Aswani et al., 2018), which also utilizes predictability loss. Their method involves enumerating all potential solutions, assessing the loss for each configuration. It is worth noting that there are 10 potential line connections, each of which can either be absent or present, resulting in 210 configurations. We esti- mated that evaluating each configuration takes on average of 2.64 seconds, thus enumerating all possibilities would take approximately 2.64 x 2nd seconds to find the global op- timum. In contrast, our proposed method solves the training problem in just 23.5 seconds
(s)) As)s) demmand 2s)) 2 1- Fm 10
0, where a(s) = (s), 0, 0,,)),, [s}) denotes the in- jection of energy in the network. Notice that generators exist in nodes 3, and 5, see Figure 3 (top). The decision matrix A E {0, _ controls the connectivity of the net- work, e.g., if 11,2 = 1, transmission line 2 emanates from node 1. Note that A is subject to additional constraints to en- sure that there are only C3 = 10 potential line connections. The auxiliary vector =(s) represents the energy flow in the transmission lines. Therefore, we define the primitive set as a hyper-rectangle 2 |-fm, f..)' which mirrors the transmission capacities. Since we assume that the locations of the generators are known, the given matrix G' dictates their position in the system. The inverse optimization prob- lem is presented in Appendix G and optimizes over matrices A. As discussed in Section 3.3, the problem can be cast as a mixed-integee linear program for both the predictability and suboptimality losses. Both approaches achieved zero loss indicating that the recovered problem is able to exactly de- scribe the training data. The recovered network is presented in Figure (bottom) in the appendix. It is interesting to note that the two networks have different transmission line configuration, with the recovered network having 4 lines instead of that the original network has. Nevertheless,
5. Limitations and Future Work
In closing, we acknowledge several limitations: (i) Our method supports only known linear objectives, excluding more complex structures like quadratic objectives which will be interesting to examine further. However, as shown in Example 3.2, the proposed approach does creates com- plex policy structures, unlike the linear policy induced from learning quadratic objective. (fi) It is worth exploring further cases where the hypothesis class leads to convex and MILP formulations (similar to Section 3.3), reducing reliance on local search algorithms. (iii) Our hypothesis class induces non-trivial relationship between the choice
8

---

Inverse Optimization via Learning Feasible Regions
of the primitive set and resulting policy behavior. Future
Chan, T. C. and Kaw, N. Inverse optimization for the re- covery of constraint parameters. European Journal of Operational Research, 282(2):415-477, 2020.
work will focus on understanding the impact of the primitive set the policies it generates, akin to the choice of basis functions in classical linear regression.
Chen, L.,, Chen, Y., and Langevin, A. An inverse optimiza- tion approach for a capacitated vehicle routing problem. European Journal of Operational Research, 295(3): 1087- 1098, 2021.
Acknowledgements
This work was partly supported by the European Research Council (ERC) project TRUST-949796.
Dempe, S. and Lohse, S. Inverse linear programming. In Recent Advances in Optimization, pp. 19 28. Springer, 2006.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Dimanidis, Ok, T., and Mohajerin Esfahani, Offline reinforcement learning via inverse optimization, preprint available at arXiv:2502.2003 2025.
Dong, C.,, Chen, Y., and Zeng, B. Generalized inverse optimization through online learning. Advances in Neural Information Processing Systems, 31, 2018.
References
Ajayi, T., Lee, T., and Schaefer, A. Objective selection for cancer treatment: An inverse optimization approach. Operations Research, 7033):717-1178,, 2022.
Elmachtoub, A. N. and Grigas, P. Smart "predict, then optimize". Management Science, 68(1):9-26, 2022.
Ghobadi, K. and Mahmoudzadeh, H. Inferring linear feasi- ble regions using inverse optimization. European Journal of Operational Research, 2020.
Akhtar, S. A., Kolarijani, A. S., and Mohajerin Esfahani, Learning for control: An inverse optimization approach. IEEE Control Systems Letters, 6:187-192, 2021.
Güler,, e. and Hamacher, W. Capacity inverse minimum cost flow problem. Journal of Combinatorial Optimiza- tion, 19(1):43-5, 2010.
Aswani, A., Shen, Z.-J,, and Siddiq, A. Inverse optimization with noisy data. Operations Research, 66(3):870-892 2018.
Keshavarz, A., Wang, Y., and Boyd, S. Imputing a convex objective function. 201 IEEE international sympo- sium on intelligent control, pp. 613-619, 2011.
Ayer, T. Inverse optimization for assessing emerging tech- nologies in breast cancer screening. Annals of Operations Research, 330:57-85, 2015.
Leon, L. M., Bretas, A. S., and Rivera, S. Quadratically con- strained quadratic programming formulation of contin- gency constrained optimal power flow with photovoltaic generation. Energies, 13(13)33310, 2020.
Bampou, D. and Kuhn, D. Scenario-fre stochastic pro- gramming with polynomial decision rules. In 201 / 50th IEEE Conference on Decision and Control and European Control Conference, pp. 7806-7812, 2011.
Li, J. Y.-M. Inverse optimization of convex risk functions. Management Science, (711))7113-71411 2021.
Bärmann, A., Pokutta, S., and Schneider, O. Emulating the expert: inverse optimization through online learning. In Proceedings of the 34th International Conference on Machine Learning- searning-Volume 70, pp. 400-410, 2017.
Lu, T. Wang, Z., Wang, J., Ai, Q., and Wang, C. A data- driven stackelberg market strategy for demand response- enabled distribution systems. IEEE Transactions on Smart Grid, 1033):334-23377, 2018.
Bertsekas, D. Convex optimization algorithms. Athena Scientific, 2015.
Mohajerin Esfahani, P., Shafieezadeh-Abader S., Hana- susanto, G. A., and Kuhn. D. Data-driven inverse op- timization with imperfect information. Mathematical Programming, 167:191-234, 2018.
Bertsekas, D. P. Nonlinear programming. Athena Scientific Optimization and Computation Series. Athena Scientific, Belmont, MA, second edition, 1999.
Nesterov, Y. Smooth minimization of non-smooth functions.
Mathematical programming, 103:127-152, 2005.
Bertsimas, D., Gupta, V., and Paschalidis, I. C. Data- driven estimation in equilibrium using inverse optimiza- tion. Mathematical Programming, 153:595 633, 2015.
Nesterov, Y. et al. Lectures on Convex Optimization, volume 137. Springer, 2018

---

Inverse Optimization via Learning Feasible Regions
Saez-Gallego, J., Morales, J. M., Zugno, M., and Madsen, H. A data-driven bidding model for cluster of price- responsive consumers of electricity. IEEE Transactions on Power Systems, 3106):5001-5011, 2016.
Tan, Y., Terekhov, D., and Delong, A. Learning linear programs from optimal decisions. Advances in Neural Information Processing Systems, 33:19738-19749 2020.
Xu, Z., Deng. T., Hu, 7., Song, Y., and Wang, J. Data-driven pricing strategy for demand-side resource aggregators. IEEE Transactions Smart Grid, 9(1):57-66, 2016.
Zattoni Scroccaro, P., Atasoy, B., and Mohajerin Esfahani, P. Learning in inverse optimization: Incenter cost, aug- mented suboptimality loss, and algorithms. Operations Research, 2024.
Zattoni Scroccaro, P., van Beek, P., Mohajerin Esfahani, P., and Atasoy, B. Inverse optimization for routing problems. Transportation Science, 59(2):301-321, 2025.
Zhang, J. and Paschalidis, I. C. Data-driven estimation of travel latency cost functions via inverse optimization in multi-class transportation networks. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC). pp. 6295-6300, 2017.
10

---

Inverse Optimization via Learning Feasible Regions
A. Proof of Proposition 2.1
Proof. We first prove the statement for the predictabilily loss. Assume that there exists and (æ, 8) in the training dataset such that (x. s) = This implies that there exists 7 since the objective of the predictability loss (5) |hil Thus, the constraints are satisfied with go (x. 8) < 0 which implies that æ is feasible (2). Moreover, by construction it implies that
min
faly. 8)
fa( 2
yE s.t.
(15)
go 8) S
In addition, since 7 it implies that Jo 8) S O. which combined with (15) imply that indeed is an optimizer of (2).
To prove the reverse implication, consider any optimal æ from (2). Since a: is feasible and optimal in (2) it implies that
= 0 is feasible in (5). Moreover, since the objective function in (5) is | there does not exist another y E IR" that
achieves a lower objective, thus 7 = also optimal, hence tg (z, 8) = 0, which concludes the proof. The proof for the suboptimality loss follows similar arguments.
B. Proof of Theorem 3.3
The proof of Theorem 3.3 can be obtained from the following lemma. Lemma B.1. Let fe 8) c(s) x. The constraints of the predictability loss in (5) can be reformulated as follows
{
3z Z x Ao(s)= bo(s)
go + 7,8 50 0
(16a)
00
( - <
A(s) - -
and the constraints of the suboptimality loss in (5) can be reformulated as follows
3 E 2, E R x Ao(s) bo(s) [h STf
g0 5
(16b)
EX e K c(s)T(x (x bo - X < % c(s) Ao(s) A
Jo(x, 8) 5070
where the norm used is the same in the definition of ge.
Proof. Recall that the definition of go (a, s) is
( s) min x62
| Ao(s) bo(s)]l-
(17a)
The function uses a latent variable z, which resides in the predetermined conic primitive set
Z (=ER" - E
(17b)
Plug the above definition into (0 + 8) < 0 gives:
3z E 2, 7 I
+ As(s) bo(s).
The reformulation of Jo is done via the dualization.
Jo + 8) 5 50

---

Inverse Optimization via Learning Feasible Regions
equivalent to
min c(s) s.t.
y E R",
((s) (
0O
y As(s) + bo(s) Hz K, y R
After dualizing the second term, we obtain:
c(s) T (x: + 7) c(s) bg X 0 c(s) =H
(18)
(19)
The proof of suboptimality follows the same procedure.
C. Proof of Proposition 3.6
Proof. The proof for both Algorithms and 2 follows the arguments. First, that the monotonicity of the proposed algorithms' outcome is straightforward consequence of its coordinate descent nature; see (Bertsekas, 2015, Section 6.5) for similar techniques. More specifically, classical result of gradient decent algorithms with several popular stepsizes, including the Armijo rule used in this work, ensures that the desired loss function is monotonically decreasing over the iterations (Bertsekas, 2015, Section 2.1). This observation of the gradient descent over the coordinate A of along with solving the convex optimization in (10) over the coordinate and the fact that loss function is uniformly nonnegative (bounded from below), concludes that the loss function remains monotonically non-increasing across the iterations.
D. MILP formulation and Proposition D.1
Proposition D.1 (MILP reformuation). Let fe( The predictability loss in (5) can be reformulated as
s) c(s) and given in (7) with Z = {= E 10, : ee = 1}.
min Mrll
s.t.
Y E RD E (0, AER
x - +
(20)
e 2 =
c(s) (x + 7) -c(s) b(s) + +
c(s) Ao(s) -e
Proof. The predictability loss with fo(2, 8) = c(s) x and go given in (7) with 2 {z E R.. Te = 1) can be written
as
min ||
s.t.
7 E 1 E R.
x . A(s)=
b(s).
e ===1 c(s) y
min
(21)
s.t.
E R" e R = A(s)= b(s)) e =z=1
c
It is clear that the optimal value of (20) constitutes an upper bound on the optimal value of (21) since z E {0, 1)2 is restriction to z E R.. Let 7" be an optimal solution problem (21). We next show that 7" is feasible (20) which will conclude the proof.
From problem (21), since + y is feasible solution + Y A(s)= b(s), eT 1, implies that > also feasible in
Vo(s) min
c(s) y y m. 2 R
s.t.
(22)
y= A()) + b(s) e =z=1
12

---

Inverse Optimization via Learning Feasible Regions
The last constraint in (21) also implies that + + optimal in (22). Additionally, notice that since (22) is linear program and c(s) T (s)) is not parallel to any of the facets of the simplex, there exists unique corner point in the simplex e 1, i.e., z' E {0, 1 J., such that As))z =' + b(s) achieves the optimal value. Hence, constraint c(s) (x + 7) S Ve(s)
ensures that only z' is feasible, thus + Y is feasible in problem (21), which concludes the proof.
E. Smoothing
Despite that both the predictability and suboptimality loss are non-convex for the hypothesis class ge given in (7) with and arbitrary choice of 2, Algorithm tends be trapped in local minima much more often for the predictability than the suboptimality loss. In this section, explain this fact by showing that suboptimality loss be viewed smoothed version of predictability loss in the sense of the so-called Nesterov's smoothing. Inspired by this technique, we propose an adaptive smoothing algorithm to potentially escape the local optimum, hence improving the performance.
Definition E.1 (Nesterov's ss smoothing (Nesterov et al., 2018)). Consider the function in the form of (xx) maxyey b. v) d(y) where & is a convex function. We define the smooth counterpart of Se as
( (Ax
Je (x) = max Ax + b. y) x(y) ed(y), DEy
where e > 0 the smoothing parameter, and d(y) is called a prox function that (i) is continuous and 1-strongly convex on y and (ii) mintey d(y) 0. Then, Je(x)) is 1/e-smooth (i.e., its gradient V.c(()) is 1/e-Lipschitz continuous), and Je(x) S (xx < (x) + e/2 for all x E V.
Suboptimality loss as smoothed predictability loss.
Considering the optimization problems (10), we define B, as the dual multiplier of the equality constraints æ; + % Ao(s;)z: + bo (s;), and the respective penalization Lagrangian function
J(0, Z)= == max Σ
3. (z, + = - bo():) where Z = 17 Rile
(23)
Dualizing this linear constraint in the predictability loss program (10a) reformulates the program to
1
Ihll + J(0,
s.t. A Ruxp by E R", Vk S K,
Yi R", 2, Zi RD, Xj ECK
(24)
Hz, -
ViSN
c(s;) Ag(ss) X A =0
c(s;) T(x, +% -bo(s:)) x
Considering the prox function d(B) 1 | r//ell2 the smoothed version of the function J is
J. 2)
Σ 2 | Ao(8,)2 (0))11
_ ln2-l-
1
(25)
26
Replacing the above smoothed term in the predictability loss (24) yields the objective function
N
2c xr Ag(a.)z, bo(s,))12 + (+ 1 2z l1/ll-
(26)
If the smoothing level is e = N/2, and the norm in the objective (10b) is separable (i.c., [1(T), Yo.)1l = 1 + ho D. one can then see that the second term in (26) is cancelled and the first term coincides with the optimal solution Y/ in the objective the suboptimality loss in (10b). In other words, the variable penalizing the feasibility of each data point effectively is smoothed version of the corresponding term in the predictability loss.
13

---

Inverse Optimization via Learning Feasible Regions
E.1. Adaptive smoothing
We presented the complete version with suboptimality loss in the following.
Definition E.2. Inspired by the results above, we define smoothed predictability and suboptimality loss in the following. Again, for clarity, we assume Jo(æ, 8) e(s) and go given in (7). The learning problem using the predictability loss can be reformulated as follows
a mrll + E1
a
Σ 11 |1 + 62 Σ Iaal
min
N
A i=1
i=1
s.t.
R bk E R", Vk _....,,, K,
Y E RR" 2, E RR. X Kt
(27a)
2; 1=%%=App8
ba(s:) + 7sl
Hz- h
ViSN
c(s, (x; + - bg (s.)) - - h 0
(x,
c(s,) Ao(s;) X, H + =
while the learning problem using the suboptimality loss can be reformulated as follows
1
min
7o,33l +
Σ I
N
1=1
2=1
s.t.
A& E Roxp, be E ER", vk= 1,.... K.
Ys YoR E ER+
% E R", 2, E X; EK*
(27b)
+ AAo(si)z; bo(:))
Ihall STf
Vi S N
Hz: -hEK
c(s; T(x; bo bo(s:)) - x h To,
c(s,) Ag(s:) A, H + Y/1 =
E,2. Convergence behavior of adaptive smoothing
In this section, we study the convergence behavior of Algorithm 2 using the experiment setting described in Section H.2. We plot the values of training loss and the four metrics defined in 2.2 to validate that the proposed method improves the performance of the solution. The plots are shown in Figure 4, where the training loss increases more regularization is added to the optimization. However, the true losses keep decreasing implying better optimal solutions are being found each time.
Finally, is worth noting that utilizing the algorithm without smoothing leads to inconsistent outcomes, particularly concerning predictability losses. Conversely, employing an adaptive smoothing algorithm here ensures consistent results are obtained. We record this behavior via an example in Figure The experiment settings follow the descriptions introduced in Appendix H.2, where p 5.
F. Problem 1: IEEE 14-Bus System
We also apply our methods on IEEE 14-bus system. This power system consists of set of regions R = {1, 14] with electricity demands gdomand r E R. Demands are satisfied by a set three power plans attached to node 2, node 8, and node 13 respectively. Each plant n E A produces In units of energy at costs 600
We set Cn 3.66 for all generators and fm 3 for all transmission lines. We generate Nirain 100 data points for training and Nus 200 data points for testing, by generating signals uniformly random from senst [0.2, 1). coss E [0.2, 0.5). .gast E 21, and 8f gdemand E [0.14, 0.7], s2 ddemand E (0.14, 0.7]. 2g sdemand E [0.16, 0.8), sgemand E (0.16, 0.8). .emand E 00.14, 0.7]. demand E [0.1, 0.5), sdemand [0.16, 0.8), ag
sdomand E 0,.1, 8 sdemand demaand E [0.1, 0.5). and sdemand E [0. 0.6), solving problem (14) to
ddemandd E [0.54, 2.7]. sg
28
[0.12, 0.6]. demaand E 10.12, 0.6). ydemand E [0.1, 0.5), $13
obtain pairs {s, x, T 1000
We apply the same method introduced in Section 4.1 and summarize the results in Table 3.
14

---

Inverse Optimization via Learning Feasible Regions
0.8
0.7
0.3
02
0.5
0.1
0.0
100
200
300
400
Aigl-pre
Algl-sub sub
Alg2-pre
Aig2-sub
terations
Figure 4. Training loss and test metries. Blue: Training (predictability) Red: Out-of-sample predictability loss. Cyan: True predictability loss. Green: True suboptimality loss. Yellow: Out-of-sample suboptimality loss.
Figure 5. Comparison between convergence behaviors of pre- dictability and suboptimality losses via both Algorithm
2. The y-axis represents the achieved training loss. Each box plot based on the same 10 randomly generated datasets.
12
B19
B20
14
13
B12
B13
B17
B11
11
Bis
10
B16
Bio
By
By
9
4
Bs
B1s
B2
B4
Bg
B14
Bs
7
8
3
B
B3
2
Figure 6. IEEE 14-bus system (Leon al., 2020). Rectangles denote nodes, arrows denote loads, and circles denotes generators.
Table 3. Summary out-of-sample performances on IEEE 14-bus system
Hypothesis Class and Loss
Evaluation method
Cg/e" 6
gaub
time
Algo 2,p =
predictability
0.83
0.68
0.12
3.5s
Algo 2,p 2
predictability
0.43
0.06
0.20
148.8s
Algo 2.p
predictability
0.51
0.24
157.8s
quadratic cost
predictability
2.58
2.56
0.63
2.54s
15

---

Inverse Optimization via Learning Feasible Regions
G. Reformulation of Problem 2
Recall that the primitive set is chosen as a box, i.e., = {z E 1 S 2m S Jms Vm E M). where M {I. [R] = = ([R) is the total number of the demand locations). For the hypothesis class, we use Ag E {0. 1 and bg 8. Matrix Ag are binary matrices indicating the connections of power networks (C) = 10 power lines at most). We denote the capacity constraints of the power plants. For clarity, denote the power generation plan and costs by two 5-dimensional vectors and Each dimension corresponds to one node in the graph. For nodes that have no power plant, we simply set its value to zero. Then, the forward problem can be written as:
Ga 9
min c x
8.l. x Ag z + 8 gommand
(28)
H= h E K, (equivalently = - Jm S am S Sm, vm E M))
Gæ g E g, (equivalently 0 0 x v 3.5).
Then, the predictability loss can be formulated binary problem as shown in (29).
N l
min Ao,
A..
s.t.
x; + 7/- Agz; + 8,
demand Vi,
Hz, - E Ki
G( + 7) 9 G, Vi,
(29)
a (s:) + +%,) - (8; domand - A, h. + BT g- B G < 0, Vi,
demand
A E K" 3 E eg",ve Vi,
c As X A, H - B. GAo = 0, Vi,
As (0, 1) 1xx10
H. Further Numerical Experiments
In this section, we conduct experiments on synthetic optimization problems to validate the proposed reformulations under both noiseless and noisy scenarios. We consider the following forward problem.
min c
x, s.t.
|| e/l S h.
(30)
We assume the objective coefficients are input signals, which follow uniform distributions. The goal is to recover the feasible region based on the observed values of e and æ. Notice that choices of distance metrics of the objective functions for both predictability and suboptimality loss do not affect any of the reformulations or algorithms proposed. Throughout the subsequent experiments, square loss will be employed for the sake of simplicity.
H.1. Convex Reformulations
In this part, we assume G ~ U[-1, < =i i 2,
and we set tje primitive set: = f2 E |=]1 < 1} in the hypothesis class. For the training data, we randomly generate N cost coefficients and calculate the corresponding optimal solutions of the forward problem. Experiments under noise or no noise are both conducted. If the training set contains noise. add Gaussian noise N N(0, 0.2) each of its dimensions. The performance is evaluated based test set that also contains 500 randomly generated coefficients and solutions.
When there is no noise, we achieved zero loss for all metrics. The performance summary for the noisy case is summarized in Table 4. It can be seen that the performance for predictability loss improves with the increasing number of training data under i..d. noises. This phenomenon arises due to the statistically consistent nature of estimates generated by predictability loss, as also highlighted in (Aswani et al., 2018).
16

---

Inverse Optimization via Learning Feasible Regions
Table 4. Out-of-sample Performance of Convex formulation with Gaussian noise.
loss
g"
Eg
Predictability
0.54
0.03
0.29
0.05
N 100
suboptimality
0.66
0.14
0.35
0.28
predictability
0.52
1.7e 3
0.31
3.3e 3
N 500
suboptimality
0.61
0.09
0.34
0.17
predictability
0.51
0
0.32
0
1000
suboptimality
0.59
0.07
0.34
0.13
H.2. Bilinear Reformulations with Simplex Primitive Set
In this section, we showcase the performance of our bilinear reformulation, where the primitive set is defined high- dimensional space. More specifically, we assume, i.e, c ~ U[0, 1], i S n 5, and consider the following simplex 3 { D.= 24 } in p-dimensional space as the primitive set. For this bilinear reformulation, can both apply Algorithm 2 or MILP reformulation to find the optimal solutions.
Experiment setting: We randomly generate N cost coefficients and calculate the corresponding optimal solutions. We consider both predictability loss and suboptimality loss. We use backtracking to adjust the step length according to the Armijo rule.
We first apply Algorithm 2 optimize the predictability and suboptimality loss. The optimization is stopped after 500 iterations. We record the performance of the proposed two losses under noiseless and noisy scenarios. For noisy cases, Gaussian noise (0,00.2 is added to each of the dimensions of the original solutions. We also vary the number of observed samples under noisy cases to check the changes in performances. In noiseless cases, we also apply MILP reformulation to obtain the optimal solutions.
Table Noiseless
n=5
N=100
train
Eg
guub
Euuh
time
Predictabilityy
0.32
1.04
1.04
0.44
0.10
174.6s
p
Suboptimality
0.33
1.04
1.04
0.44
0.10
48.3s
MII.P
0.25
0.99
0.99
0.45
0.07
901. 12..2
Predictability
= 5
Suboptimality
0
0
52.3s
MILP
0
0
902.7s
Predictability
0
21.6s
p 6
Suboptimality
0
42.3s
MILP
543.5s
Table 6. Noisy case with 100 training samples.
T
N 100
train
g
gr
gaub
time
Predictability
0.52
1.17
0.97
0.60
0.10
87.4s
p
Suboptimality
0.43
1.42
1.22
0.57
0.91
85.0s
Predictability
0.14
0.42
0.24
0.18
0.11
110.9s
p = 5
Suboptimality
0.11
0.68
0.49
0.14
0.84
101.28
Predictability
0.13
0.50
0.31
0.19
0.07
131.0s
= 6
Suboptimality
0.11
0.65
0.46
0.14
0.72
121.9s
Table 7. Noisy case with 200 training samples.
5
N = 200
train
Cg
g
geub
goub
time
Predictability
0.52
1.17
0.97
0.58
0.10
170.4s
=
Suboptimality
0.44
1.46
1.26
0.56
0.97
208.3s
Predictability
0.16
0.37
0.18
0.17
0.05
259. 2s
5
Suboptimality
0.11
0.78
0.58
0.14
0.89
222. 4s
Predictability
0.14
0.37
0.19
0.16
0.10
257. .2s
p
Suboptimality
0.11
0.74
0.54
0.13
0.84
236.2s
17

---

Inverse Optimization via Learning Feasible Regions
Results. The results are summarized in Table 5, 6, and In scenarios without noise, the forward problem is accurately restored when the hypothesis class encompasses the true feasible region. In such instances, this requirement is equivalent having p 2 5 since the original feasible region comprises five extreme points. In noisy scenarios, noticed enhanced performance with an enlarged sample size for predictability loss, with no corresponding improvement observed for suboptimalitt loss. was also noted that the MILP reformulation exhibited superior overall performance in contrast to the gradient-descent-busee algorithm. Nonetheless, in instances characterized by noise, the inherent complexity of MILP formulations renders them challenging (number of binary variables proportional to data size) to resolve within one-hour timeframe. Finally, visual representation of feasible region gø (a, s) S 0 as the parameters l are updated using Algorithm 2 is presented in Figure for the noiseless case. We observe that the hypothesis class is able to rotate, scale, project and translate the primitive set by updating 0 (A',b').
2.0
15
0.5
iteration
iteration Iteration
iteration 16 iteration 22 iteration 30 iteration
1
2
Figure 7. Visualization of get (zx, s) for Algorithm 2. The feasible region of the forward problem given || ell s 1, and the learning algorithm recovers it by iteration 200.
18


Reviews:
[{"review_id": "bXc0rabFxX", "reviewer": "Reviewer_FgZm", "summary": "The paper proposes a novel inverse optimization (IO) framework to learn feasible regions (constraints) from observed decisions. Key contributions:\n\nTwo Loss Functions:\nPredictability Loss: Minimizes the perturbation required to make observed decisions feasible and near-optimal.\nSuboptimality Loss: Penalizes violations of feasibility and optimality using slack variables.\n\nHypothesis Class: Models feasible regions through a parametric function $g_theta(x, s) = min_z ||x - A_theta(s) z - b_theta(s)||^2$, where z belongs to a primitive set Z (e.g., hypercube), and A_theta(s), b_theta(s) are learnable parameters.\n\nAlgorithms:\nBlock coordinate descent with adaptive smoothing for general cases.\nConvex and mixed-integer linear program (MILP) reformulations for specific primitive sets Z.\nResults: Recovers synthetic constraints (e.g., polygons, Lp-balls) and power grid topologies with 0% violation in noiseless cases, outperforming baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments/questions. Here is our response:\n\n__[Q1: Implication of nonpositive loss]__ \n\nThe reviewer is indeed correct that for the function $J_\\theta$ defined in (4), the condition $J_{\\theta}(\\boldsymbol{x}, \\boldsymbol{s}) \\leq 0$ does not necessarily imply that the point $\\boldsymbol{x}$ meets both optimality and feasibility conditions. However, there may be a misunderstanding between $J\\_\\theta(\\boldsymbol{x}, \\boldsymbol{s})\\le 0$ and $\\ell\\_\\theta(\\boldsymbol{x}, \\boldsymbol{s})\\le 0$. In this regard, let us note that considering $\\ell^{\\rm p}\\_\\theta$ and $\\ell^{\\rm sub}\\_\\theta$ introduced in (5a) and (5b), if these loss functions at a given point are nonpositive (e.g., $\\ell^{\\rm p}\\_\\theta(\\boldsymbol{x},\\boldsymbol{s}) \\le 0$, which by definition implies $\\ell^{\\rm p}\\_\\theta(\\boldsymbol{x},\\boldsymbol{s}) = 0$), then not only we have $J\\_{\\theta}(\\boldsymbol{x}, \\boldsymbol{s}) \\leq 0$ but we also have $g\\_{\\theta}(\\boldsymbol{x}, \\boldsymbol{s}) \\leq 0$ because of the constraints of the function $\\ell^{\\rm p}$ in (5a). This combination imposed in (5a) guarantees both feasibility and optimality of $\\boldsymbol{x}$. \n\nAn identical line of argument can be applied for the suboptimality loss $\\ell^{\\rm sub}$ defined in (5b). This discussion is formally provided in Proposition 2.1 in the main body and its respective proof in the supplementary. \n\n__[Q2: Adverserial inputs]__ \n\nThere are two possible interpretations of adversarial inputs:  \n\n(i) One interpretation is that the input $\\boldsymbol{s}$ lacks sufficient exploration, making it impossible to uncover the ground truth even when the correct hypothesis class is chosen. However, our proposed method can still provide out-of-sample guarantees (or generalization bound) if the data are i.i.d. However, this out-of-sample bound is perhaps less significant, as it readily follows under some mild assumption, such as boundedness of the training parameter~$\\theta$, thanks to the classical covering techniques and the finite exact reformulation in Theorem 3.3, see Section 13.3 \"VC-Dimension and Uniform Convergence\" in [Shalev2014].\n\n(ii) Another interpretation is that adversarial inputs refer to input-output pairs corrupted by noise. To better understand their impact, we have conducted several numerical experiments presented in Appendix H. A classical approach to mitigating this effect is to apply generic distributionally robust optimization techniques similar to those in [Mohajerin2018]. However, we have chosen not to include this discussion, as it would require introducing a new hypothesis class for learning constraints, analyzing its interaction with the loss function, and presenting the associated solution method.     \n\n**References:**\n\n[Shalev2014] Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.\n\n[Mohajerin2018] Mohajerin Esfahani, P., Shafieezadeh-Abadeh, S., Hanasusanto, G. A., and Kuhn, D. Data-driven inverse optimization with imperfect information. Mathematical Programming, 167:191–234, 2018.\n\n__[Q3: Main contributions]__ \n\nThe referee is correct in noting that the main contribution of the paper is the hypothesis class for $g_\\theta$ in (7). To the best of our knowledge, this is the first attempt to incorporate constraint learning within the inverse optimization framework (Thm. 3.3), which, in a special case, yields a finite tractable convex optimization problem (Prop. 3.7). To establish these results properly, we revisited the existing predictability and suboptimality loss functions in the objective function learning case and extend them to the case of constraints learning (cf. loss functions (5a) and (5b), see also Prop. 2.1). Additionally, the resulting learning optimization problems are challenging to solve. As such, we also consider the proposed tailored solution method (Algorithms 1 and 2) as a contribution of this study.\n\n__[Q3: MILP part]__ \n\nThere are two distinct cases in which the learning problem can be formulated as a MILP:   \n\n(i) Binary matrix $\\boldsymbol{A}\\_\\theta(\\boldsymbol{s})$: As the reviewer noted, when the matrix $\\boldsymbol{A}\\_\\theta(\\boldsymbol{s}) = A \\in \\\\{0,1\\\\}^{n \\times p}$ is binary (example in Sec. 4.2 where $A$ representing network connectivity), the bilinear problems (10a) and (10b) can be reformulated as MILPs by leveraging McCormick inequalities to linearize the bilinear terms $\\boldsymbol{A}_\\theta(\\boldsymbol{s})\\boldsymbol{z}_i$.  \n\n(ii) Discrete Primitive Set $\\mathcal{Z}$ and continuous Matrix $\\boldsymbol{A}\\_\\theta(\\boldsymbol{s})$: As discussed in Observation 3.8, when $\\mathcal{Z}$  is discrete, the bilinear problems (10a) and (10b) can be reformulated as MILPs because the bilinear terms $ \\boldsymbol{A}\\_\\theta(\\boldsymbol{s})\\boldsymbol{z}_i$ can be linearized using the same techniques as in McCormick inequalities.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Proposition 2.1: L=0 iff x is optimal.\nTheorem 3.3: Reformulates learning into tractable programs.", "experimental_designs_or_analyses": "Synthetic Tests: Simple 2D regions\nPower Systems: Realistic DC optimal power flow task.\nLimitation: No high-dimensional/complex tests on conic primitive set.", "relation_to_broader_scientific_literature": "Extends prior work (e.g., Aswani et al., 2018) by avoiding constraint enumeration.\nAdvances IO by shifting focus from objective learning to constraint learning.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is well written and structured\n2. First framework for learning feasible regions in IO.\n3. Handles discontinuous/nonconvex regions.\n\nWeaknesses:\n1. Relies on predefined primitive sets Z (e.g., hypercube).\n2. Limited to linear objectives; nonlinear cases untested.", "other_comments_or_suggestions": "The figures are hard to understand. I would suggest the authors to prepare a better illustration", "questions_for_authors": "1. In predictability loss, why J_{\\theta}<=0 implies optimality? As J_{\\theta}<=0 only imply the constraints set learned is tightened and exclude x as the optimum \n2. How would the model perform with adversarial inputs?\n3. What is the main contribution in the paper? Is it the new design of the approximation function g_theta (x,s)? In addition, I don't quite understand the MILP part, does the integer comes from the binary variables in A?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ppikzj52nc", "reviewer": "Reviewer_1GDE", "summary": "The authors derive a method based on inverse optimization to learn the feasible region of an optimization model. To this end, they use two loss functions, incorporating infeasibility and suboptimality of the solutions over the hypothesized feasible region. Besides, they set a parametrized hypothesis class for the constraint functions. The problem can be approximated in this setting by performing block coordinate descent, for which an algorithm is given. Adaptive smoothing techniques are given to improve the algorithmic performance. Theoretically, it is discussed that for certain restrictions to the hypothesis set, the problem can be reformulated into a convex problem or MILP. The authors apply their method to a network flow problem for power systems. A comparison to other methods is made when learning the constraint’s structure. Also, an experiment is conducted in which the goal is to learn the structure of the power network.\n\n\"## update after rebuttal\nNo update.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments/questions. We will address all minor points in the revision. Please find all the code used for the paper in https://github.com/orRepo/InverseOptimization. Below is our response:\n\n__[Q1: Main contributions]__ \n\nThe primary contribution is the hypothesis class (7), which transforms constraint learning in inverse optimization into a finite structured optimization problem (Thm. 3.3) that, in a special case, yields the first finite tractable convex formulation (Prop. 3.7). Prior work results in unstructured nonconvex programs or relies on enumeration in discrete cases [Aswani2018]. To reach this end, we extended the predictability and suboptimality losses from [Mohajerin2018], previously limited to objective function learning, to constraint learning (loss functions (5a) and (5b), see also Prop. 2.1). Given the complexity of the resulting optimization problems, we also introduce tailored solution methods (Algorithms 1 and 2).\n\nIn summary, the hypothesis class is the main contribution, with loss functions and solution methods serving a secondary and supporting role.\n\n__[Q2: Benchmarking]__ \n\nTo our best knowledge, the only existing approach for learning constraints under similar settings (1. observing signal-(optimal) solution pairs, 2. a non-fixed objective function varying with signals, 3. allowance for noise) within inverse optimization is [Aswani2018]. However, this lacks a tractable solution method, relying instead on enumeration, which, as noted in Section 4.2, becomes impractical even for small problems.\n\n__[Q3: Zero training loss]__ \n\nThe synthetic data generated by the forward problem (14) can be explained by multiple network configurations. Specifically, both networks in Figure 3 can exactly reproduce the training data, meaning there is no single \"right\" network structure, i.e., multiple structures can be consistent with the observed input-output pairs. Without additional information beyond the training data, inverse optimization cannot differentiate between these structures. However, this also presents an opportunity: One can design simpler network structures, such as those with fewer connections, that perform equally well. This is precisely the case demonstrated in Section 4.2.\n\nAdditionally, in response to the comment: \"It is unclear which methods are used as a benchmark, especially for Experiment 2,\" we clarify that, as discussed at the end of Section 4.2, the enumeration approach proposed by [Aswani2018] can also achieve zero loss. However, this approach requires exponential computational effort to reach the same result. Moreover, it does not circumvent the existence of multiple optimal network structures, meaning it faces the same fundamental challenge discussed above.\n\n**References:**\n\n[Aswani2018] Aswani, A., Shen, Z.-J., and Siddiq, A. Inverse optimization with noisy data. Operations Research, 66(3):870–892, 2018.\n\n[Mohajerin2018] Mohajerin Esfahani, P., Shafieezadeh-Abadeh, S., Hanasusanto, G. A., and Kuhn, D. Data-driven inverse optimization with imperfect information. Mathematical Programming, 167:191–234, 2018.\n\nWe would also like to address the referee's other concerns below.\n\n**[Proof of Theorem 3.3]** \n\nThank you for pointing out this concern. We kept the proofs short due to lack of space. We will make sure that both Theorem 3.3 and Lemma B.1 are fully shown in the revision, elaborating further on the dualization trick.\n\n**[Proof of suboptimality loss]** \n\nYes, they are the same. We will modify the text of the existing proof to be applicable for both losses to improve clarity.\n\n**[Algorithm 1 in Experiment 1]** \n\nThe numerical results in Table 1 indicate that Algorithm 1 can become trapped in local optima, whereas Algorithm 2, due to its smoothing properties, is better able to escape these local optima and generally performs better. For this reason, Algorithm 1 was not included in the extended numerical experiments.\n\n**[Quadratic Cost Performance]** \n\nIn Example 3.2, it is mathematically demonstrated that learning a quadratic objective effectively results in a linear policy. In contrast, the proposed hypothesis class induces a richer policy class with piecewise behavior, leading to improved performance. However, there is indeed a trade-off between loss and runtime among the methods.\n\n**[Repeated Gurobi approach numbers in Table 2]** \n\nThanks a lot for catching this copy error; the correct values for the rows related to \"predict.\" are as follows:\n\n| Method        | Loss     | \\$\\ell_\\theta^p /\\ell^p\\$ | \\$\\ell_\\theta^\\text{sub}\\$ | \\$\\ell^{\\text{sub}}\\$ | time     |\n|---------------|----------|-------------------------|--------------------------|---------------------|----------|\n| Gurobi \\$p=3\\$  | predict. | \\$6.32\\$                  | \\$4.44\\$                   | \\$0.49\\$              | \\$1800\\$s  |\n| Gurobi \\$p=6\\$  | predict. | \\$6.54\\$                  | \\$4.31\\$                   | \\$0.76\\$              | \\$1800\\$s  |", "claims_and_evidence": "Overall, the claims made about the numerical experiments are justified by the results presented. However, there is no reference to the code, resulting in a lack of reproducibility.\n\nThe authors' claims regarding their contributions are mostly convincing but are limited:\n- The hypothesis class of the g functions and the corresponding solution algorithm are new approaches and, therefore, are relevant contributions\n- The claim on the novelty of the loss functions is unconvincing as the authors refer to literature where these losses are introduced. It seems like a generalization rather than a novel contribution.", "methods_and_evaluation_criteria": "- In experiment 1, there is a nice comparison of different methods (convex, Gurobi, algorithm 2).\n- It is unclear which methods are used as a benchmark, especially for experiment 2.\n- Both runtime and loss are considered.", "theoretical_claims": "A few concerns regarding the theoretical claims:\n\n- The proof of Theorem 3.3 is not referring to any results/shows no derivatives. It is just Lemma B.1, which is not properly proved? For the overall comprehensibility of the paper it would be good to show the reformulation steps and why dualization leads to the final reformulation. The latter is not directly obvious and uses a nice trick to get rid of the minimization problem in the constraints.\n\n- The proof of Proposition 2.1 states that a proof for the suboptimality loss follows similar arguments. This makes sense, but why is it not added? What is different, or is it completely the same?\n\n- Corollary E.2.: There is no proof, derivation, or reference to support this claim mentioned.", "experimental_designs_or_analyses": "A few concerns regarding the Experimental Designs Or Analyses:\n\n- The code of the experiments is not shared, so reproducing the results is difficult.\n- The illustrative experiment to compare Algorithms 1 and 2 has no set-up discussed. The plausible description in Appendix H is not referenced. The results of this experiment in Table 1 are mildly convincing as the details of the setup are unknown.\n- Experiment 1 compares a decent number of methods, except Algorithm 1. The reason for this is not mentioned.\n- For Experiment 1, in Table 2, the Gurobi approach seems to have always the same loss for predictability and suboptimality, except for p=9. The reason for the noticeable result is not discussed.\n- The claim “(ii) Learning a quadratic cost is significantly inferior to other methods” (around line 367, second column) in the experiments is too intense; there is a decent trade-off between loss and runtime between the methods.\n- In Experiment 2, the method achieves zero loss, a perfect fit for the train set. However, Figure 3 shows that the method does not find the original structure. This is a major problem, the method is not suited to recover networks even in small settings. It is not mentioned why this occurs or in which setting this can be prevented. As it is presented, it seems this method is not the right approach for this problem.\n- Experiment 2 has no benchmark, only an estimated comparison on runtime\n- Experiments in both the paper and the appendix are mainly limited to network flow problems for power systems. It would be interesting to see experiments for other applications and problem structures.", "relation_to_broader_scientific_literature": "This research focuses on learning the feasibility region contrary to other works that focus on learning the objective function. Also, this work considers specific hypothesis classes for this problem, which is a novel approach for learning the feasibility region.", "essential_references_not_discussed": "No comment", "other_strengths_and_weaknesses": "No Comment", "other_comments_or_suggestions": "- Nowhere is it mentioned that bold notation is used for vectors/matrices.\n- N_out is used but not properly defined. Line 153, column 2.\n- “Let A_(s) and b_(s) be a matrix and vector with appropriate dimensions…” I would recall these dimensions formally. Line 200-201, column 1.\n- In Line 12, column 2, signal s is in R^k. In Line 224-226, column 1, we have k=0,…, K. These notations are confusing as signal s first has k components and later in the paper K components.\n- Calligraphic K^* is not defined. Is it the dual cone? Line 236, column 1.\n- Armijo’s rule is mentioned, but there is no citation or explanation. Line 222, column 2.\n- gamma_{s1*} and gamma_{s1}^* are both used in Algorithm 2 which is inconsistent.\n- R and calligraphic R are both used in Lines 361-362, column 1, which is inconsistent.\n- It is not known what C_n represents. Line 380, column 1.\n- Experiment/Problem 2 assumes the capacity constraints are known. Which ones, the C_n , the bar(f)_m, or both? Line 380, column 2.\n- The actual problem using an input signal and output was abstract until Example 3.2. The relevance would have become more apparent if a tangible example had been discussed in the introduction and perhaps outside of the domain of power systems.", "questions_for_authors": "- The proposed loss functions seem to be known in the literature: What are the main contributions of this paper?\n- What are the common benchmark methods for learning feasible regions which could compete with you?\n- What is the reason for the method finding zero loss experiment 2 while not finding the right network structure, and how can this issue be resolved?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iDAr85vgwc", "reviewer": "Reviewer_esGE", "summary": "This paper investigates inverse optimization, with a particular focus on learning feasible regions in optimization problems with linear objectives. The authors introduce two loss functions, propose a hypothesis class for the constraint function, and develop reformulations and smoothing techniques to address the inverse optimization problem.\n\nIn particular, Section 2 presents two loss functions, termed predictability loss and suboptimality loss. Section 3 introduces a hypothesis class for the constraint function, along with an adaptive smoothing technique to reformulate the loss functions under the assumption of a linear objective. Section 4 reports numerical experiments conducted to assess the efficiency of the proposed techniques.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments/questions. Here is our response:\n\n__[Contributions of loss functions:]__  \n\nWe agree that introducing the loss functions is not a major contribution. However, their combination in (5a) and (5b) with the hypothesis class in (7) enables reformulation into finite optimization problems (10a) and (10b) (Thm. 3.3). More importantly, when $A\\_{\\theta}(s)$ is a positive scalar, it admits a finite convex reformulation (13) (Prop. 3.7). To our knowledge, no existing inverse optimization or imitation learning approach achieves convex training in such cases.\n\n__[Concerning the theoretical guarantees:]__  \n\nThere are two key considerations: \n\n(i) **Out-of-sample performance** (generalization error), which bounds the loss on unseen/test data based on training loss.  \n(ii) **Suboptimality bound** of the training loss, crucial when the loss is nonconvex in model parameters $\\theta$.  \n\nThe out-of-sample bound (i) is straightforward under mild assumptions, such as bounded $\\theta$, using classical covering techniques and the finite reformulation in Theorem 3.3 (see [Shalev2014], Section 13.3).  However, the suboptimality bound (ii) is more interesting, as most cases in Theorem 3.3 are nonconvex in $\\theta$, except for Proposition 3.7. We derive an a-posterior bound for (ii) in both (10a) and (10b) as follows (we refrain from using bold symbols to economize on characters):  \n \n**Proposition (Training suboptimality bound):**\n_The optimal value of problem (10a) associated with the suboptimality loss is bounded from below by the optimal value of the finite tractable convex problem_ \n$$\\max\\_{||\\alpha_i||\\_*\\leq 1}  \\min\\_{z\\_i\\in\\mathcal{Z}}\\max  \\displaystyle\\frac{1}{N} \\sum_{i = 1}^N  \\alpha\\_i^\\top (A\\_{\\theta}(s\\_i)z\\_i + b\\_{\\theta}(s\\_i) - x\\_i) + \\gamma_{o,i} + \\nu\\_i( c(s\\_i)^\\top(x\\_i-b\\_{\\theta}(s\\_i)) + \\lambda\\_i^\\top h - \\gamma\\_{o,i}) +  ( c(s\\_i)^\\top A\\_{\\theta}(s\\_i) + \\lambda\\_i^\\top H)\\tau\\_i + \\lambda\\_i^\\top \\mu\\_i$$\n_where maximization of the innermost max is done over $A\\_k\\in\\mathbb{R}^{n\\times p},b\\_k\\in\\mathbb{R}^{n}$, for all $k=1,\\ldots,K$, and $\\gamma\\_{o,i}\\in\\mathbb{R}\\_+$, $\\nu\\_i\\in\\mathbb{R}\\_+$, $\\tau\\_i\\in\\mathbb{R}^p$, $\\mu\\_i\\in\\mathcal{K}$ for all $i=1,\\ldots,N$._\n\n**Sketch of the proof:** To save space, we outline the intuition behind the proof rather than the full derivation. The first constraint of the suboptimality problem is $\\gamma\\_{i} = A\\_{\\theta}(s\\_i)z\\_i + b\\_{\\theta}(s\\_i) - x\\_i$. Substituting this into the objective function, we rewrite it as $\\frac{1}{N} \\sum\\_{i = 1}^N \\|A\\_{\\theta}(s\\_i)z\\_i + b\\_{\\theta}(s\\_i) - x\\_i\\| + \\gamma\\_{o,i}$. Using the dual norm, this is equivalent to  \n\n$$\\max_{|| \\alpha\\_i ||\\_{*}\\leq 1} \\frac{1}{N} \\sum\\_{i = 1}^N  \\alpha\\_i^\\top (A\\_{\\theta}(s\\_i)z\\_i + b\\_{\\theta}(s\\_i) - x\\_i) + \\gamma\\_{o,i}.$$  \n\nInterchanging minimization and maximization leads to  \n$$\n\\max\\_{||\\alpha\\_i||\\_*\\leq 1} \\min \\frac{1}{N} \\sum\\_{i = 1}^N  \\alpha\\_i^\\top (A\\_{\\theta}(s\\_i)z\\_i + b\\_{\\theta}(s\\_i) - x\\_i) + \\gamma\\_{o,i}.\n$$ \nThe optimal value provides a lower bound on (10a). Since the inner problem is bilinear in $A\\_k$ and $z\\_i$, but their constraints are disjoint, we can dualize with respect to $A\\_k$ and $\\lambda\\_i $, yielding the proposed formulation.\n\nFor clarity:  \n(i) $\\mu\\_i$ are dual variables for $-\\lambda\\_i \\in \\mathcal{K}^*$.  \n(ii) $\\tau\\_i$ are dual for $c(s\\_i)^\\top A\\_{\\theta}(s_i) + \\lambda\\_i^\\top H = 0$.  \n(iii) $\\nu\\_i$ are dual for $c(s\\_i)^\\top(x\\_i-b\\_{\\theta}(s\\_i)) + \\lambda\\_i^\\top h \\leq \\gamma\\_{o,i}$.  \n\nThe lower-bounding problem is a two-stage robust optimization problem solvable via column-and-constraint generation [Zeng2013] or affine policies [Kuhn2011], ensuring a valid lower bound.\n\nA similar bound can be derived for the predictability loss (10b). If needed, we can provide it. Given an extra page in the final version, we believe we can incorporate these details in the final version.  \n\n**References:**\n\n[Shalev2014] Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.\n\n[Zeng2013] Zeng, Bo, and Long Zhao. \"Solving two-stage robust optimization problems using a column-and-constraint generation method.\" Operations Research Letters 41.5 (2013): 457-461.\n\n[Kuhn2011] Kuhn, Daniel, Wolfram Wiesemann, and Angelos Georghiou. \"Primal and dual linear decision rules in stochastic and robust optimization.\" Mathematical Programming 130 (2011): 177-209.}", "claims_and_evidence": "The claims made in the submission are clear and also supported by proposed numerical experiments.", "methods_and_evaluation_criteria": "The reformulation for linear objective functions and the convex/mixed-integer reformulation appear relatively straightforward. The adaptive smoothing technique is well-integrated into the optimization framework, though its convergence analysis is not appealing. But, of course, we cannot assume too much for this type of inverse optimization. \n\nThe numerical experiments are conducted on two types of applications with relatively small dimensions (less than 10), which might weaken the reformulations and theoretical results provided before.", "theoretical_claims": "Proofs in this paper are okay on my side.", "experimental_designs_or_analyses": "Experimental designs are sound. As mentioned above, it is better to discuss how dimension $p$ influences the numerical performances.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The paper is clearly written and well-organized. The authors effectively introduce the geometric interpretation of the two loss functions, provide insights into their hypothesis class through the primitive set representation, and elaborate on the block coordinate descent algorithm in detail.\n\nHowever, while the introduction of the loss functions is straightforward and has an intuitive geometric interpretation, it remains unclear whether minimizing these loss functions guarantees a meaningful solution to the inverse optimization problem. A comparison with commonly used suboptimality metrics in inverse optimization would strengthen the work. Additionally, theoretical guarantees, such as error bounds under mild assumptions, would enhance the paper’s rigor.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DnX4NcXDrc", "reviewer": "Reviewer_dJRX", "summary": "This paper proposes an inverse optimization approach to learn parameters in an optimization problem using historical decision data. Specifically, the authors adapt the predictability and sub-optimality losses, previously used in the literature for learning objective functions, to the context of constraint learning. The resulting inverse problems are non-convex due to the presence of bilinear terms. To address this, the authors propose two algorithms: one based on gradient descent and the other on mixed integer programming reformulation. These algorithms are tested on two synthetic problem instances.\n\nOverall, this paper introduces a novel approach to the challenging problem of constraint learning. While I do not find any technical flaws in the paper, I have some concerns regarding its exposition and positioning. If these concerns are addressed during the rebuttal phase, I would be willing to increase my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments/questions. Here is our response:\n\n**[Q1: Loss functions meaning]** \n\nTable 2 presents the performance of different methods across four metrics: true predictability loss $(\\ell^\\text{p})$, true suboptimality loss $(\\ell^\\text{sub})$, estimated predictability loss $(\\ell^\\text{p}\\_\\theta)$, and estimated suboptimality loss $(\\ell^\\text{sub}\\_\\theta)$. As discussed in Section 2.2, $\\ell^\\text{p}\\_\\theta$ and $\\ell^\\text{p}$ are identical, a result also illustrated in Figure 2 (bottom). Therefore, Table 2 includes a single column for both, denoted as $\\ell^\\text{p}\\_\\theta/\\ell^\\text{p}$. We will clarify this in the revision.\n\n**[Q2: Binary matrix $A$]** \n\nIn Section 4.2, we consider a network with five nodes (Figure 3), allowing up to $\\binom{5}{2} = 10$ potential transmission lines, with the original network containing five of them. The equation $\\boldsymbol{x}(\\boldsymbol{s}) = \\boldsymbol{A} \\boldsymbol{z}(\\boldsymbol{s}) + \\boldsymbol{s}^{\\text{demand}}$  models the network, where $\\boldsymbol{x}(\\boldsymbol{s}) \\in \\mathbb{R}^5$ represents generation decisions, $\\boldsymbol{z}(\\boldsymbol{s}) \\in \\mathbb{R}^{10}$ represents flow decisions, and $\\boldsymbol{A} \\in \\\\{0,1\\\\}^{5 \\times 10}$ defines network connectivity (1 indicating a connection, 0 indicating absence).  We do not aim to model all possible connection configurations, as $\\boldsymbol{A}$ is subject to constraints. As discussed later, $\\boldsymbol{A}$ only indicates 10 potential connection lines, yielding up to $2^{10}$ possible connection patterns. We will clarify this in the revision to avoid confusion.\n\n**[W1: Remark regarding positioning]**  \n\nThe referee raises an important point. Indeed, inverse optimization is widely used in econometrics to estimate specific parameters. However, in such cases, the optimization model is typically assumed to be known up to certain parameters and often results in highly nonlinear problems. In contrast, our approach, particularly in learning network structures, offers scalability by leveraging off-the-shelf solvers.  \n\nWe however respectfully disagree that our method is unsuitable for future decision-making. Inverse optimization serves as a hypothesis class in a supervised setting, learning the input-output mapping much like any supervised learning method such as neural networks. In this view, one can apply the classical generalization bounds under some mild assumption, such as boundedness of the training parameter $\\theta$, thanks to the classical covering techniques and the finite exact reformulation in Theorem 3.3; see for instance, Section 13.3 \"VC-Dimension and Uniform Convergence\" in [Shalev2014]. Moreover, by leveraging problem structure (e.g., knowing the objective), we systematically control model complexity. For instance, in Section 4.1, we increase hypothesis flexibility by varying the primitive set $\\mathcal{Z}$, where choosing the unit simplex and expanding its dimension improves out-of-sample performance (see Table 2), keeping the complexity of the problem under control.  \n\nIt is important to note that, as the reviewer mentioned, these generalization bounds do not provide a feasibility guarantee for the original/true sub-optimality. However, instead, the forward problem’s optimal value provides an upper bound on the out-of-sample values of these true losses. This motivates our inclusion of both estimated losses $(\\ell^{\\text{p}}\\_\\theta, \\ell^{\\text{sub}}\\_\\theta)$ and true losses $(\\ell^{\\text{p}}, \\ell^{\\text{sub}})$ in Section 2.2. We agree with the reviewer on this point, and following his/her request for clarification, we will ensure these points are addressed in the final version of the paper.\n\n**[W2: Remark regarding interpretability]** \n\nOur hypothesis class, $\\boldsymbol{x} = \\boldsymbol{A}\\_\\theta(\\boldsymbol{s})\\boldsymbol{z} + \\boldsymbol{b}\\_\\theta(\\boldsymbol{s})$, was designed with the following rationale. When $\\boldsymbol{A}\\_\\theta(\\boldsymbol{s}) = \\boldsymbol{A}$ and $\\boldsymbol{b}\\_\\theta(\\boldsymbol{s}) = \\boldsymbol{b}$, it maps the primitive set $\\mathcal{Z}$ to $\\boldsymbol{x}$, where $\\boldsymbol{A}$ enables rotation, scaling, or projection, and $\\boldsymbol{b}$ allows translation (see Section 3, lines 212–Remark 3.1). Allowing $\\boldsymbol{A}\\_\\theta(\\boldsymbol{s})$ and $\\boldsymbol{b}\\_\\theta(\\boldsymbol{s})$ to depend on $\\boldsymbol{s}$ makes this transformation signal-dependent.  The choice of a linear form, $\\boldsymbol{A}\\_\\theta(\\boldsymbol{s}) = \\boldsymbol{A}\\_0 + \\sum_{k=1}^{K} \\boldsymbol{A}\\_k s\\_k$, was inspired by linear regression. If $\\mathcal{Z}$ is a singleton, the hypothesis class reduces to standard linear regression. While we kept the discussion brief, we agree that a more detailed explanation would be beneficial.  \n\n**References:**\n\n[Shalev2014] Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.", "claims_and_evidence": "The claims are generally well supported. However, as detailed in weaknesses, the authors might consider clarifying that the proposed method is only applicable to one type of inverse problems, i.e., those intended to provide insights into the system of interest, and can not be used to support future decision making (due to the lack of feasibility guarantees).", "methods_and_evaluation_criteria": "The evaluation makes sense. However, again, it only makes sense for one type of inverse problems.", "theoretical_claims": "I check the proofs and did not identify major flaws.", "experimental_designs_or_analyses": "The experimental design is sound. Yet the presentation can be improved (as detailed below).", "relation_to_broader_scientific_literature": "This is of interest to the inverse optimization (and potentially econometrics) community because it is a new method to learn parameters in constraints, which is known to be a hard problem.", "essential_references_not_discussed": "Not really.", "other_strengths_and_weaknesses": "**Strengths**\n- The proposed approach is novel (to the best of my knowledge)\n- The research question is challenging.\n- The computational performance is good\n\n**Weaknesses**\n- Exposition. While I appreciate the authors' effort in writing a highly technical paper, I believe the current exposition does not effectively convey the intended message. \n\n    - First, Figures 1 and 2 are interesting and informative, but their presentation is quite messy. Clearer illustrations are needed to help readers better digest the information presented.\n\n    - Second, the optimization models presented in this paper lack clear explanations. Specifically, the constraints in (10a) and (10b), which are key contributions, need to be thoroughly clarified. Additionally, Problem (14) could have been better explained. As it stands, the descriptions of Problems 1 and 2 are somewhat difficult to understand.\n    \n    - Third, related to the previous point, Problem 1 (Section 4.1) is particularly difficult to follow. Specifically, what does \"lacks knowledge of the cosntraint' structure\" mean? \n\n- Positioning. Inverse optimization can serve two main purposes: (1) inferring parameters to gain insights into the system of interest, and (2) using the learned parameters to support future decision-making. The proposed method is suitable only for the first purpose because (a) the learned parameters do not guarantee feasibility for future decisions, and (b) the evaluations are based on out-of-sample loss, which measures goodness of fit rather than the quality of prescribed decisions. The authors should consider clarifying this in the paper. Alternatively, they might add theoretical/empirical insights into the feasibility and quality of the prescribed decisions.\n\n- Building on the previous point, it is crucial for the estimated parameters to be interpretable in order to gain insights into the system of interest. In lines 223--225 on page 5, the authors introduce a fairly complex parameterization, which helps to address the computational challenges. However, this complexity may hinder the interpretability of the parameters. The authors should consider clarifying why this parameterization remains interpretable (i.e., what do the parameters stand for in practical terms?).", "other_comments_or_suggestions": "- Page 8, lines 403--405. \"In a network with 5 nodes, there are 10 possible transmission line connections\" is confusing. The authors should refer to Figure 3 before presenting this sentence.", "questions_for_authors": "- Table 2. What does $\\ell^p_\\theta / \\ell^p$ mean?\n\n- Page 8, line 417. Why is $A \\in \\{0, 1\\}^{5\\times 10}$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper provides an approach for learning constraint functions in inverse optimization, with a focus on the constraint hypothesis class $g_{\theta}(x,s) = \min_{z \in \mathcal{Z}} \|\| x - A_{\theta}(s)z - b_{\theta}(s)\|\|$ motivated by the two-generator economic dispatch problem in electric power systems. The reviewers acknowledged the relevance of the contribution and the difficulty of the problem being solved by the submission (though with a request that the authors reframe the paper to highlight that the main contribution is the analysis/algorithm in the context of the hypothesis class studied, rather than the loss functions or the solution method in and of themselves) as well as the reasonable experimental results. However, the reviewers also raised concerns with the small scale and somewhat toy nature of the experiments, the incompleteness of some of theoretical proofs, experimental reproducibility, interpretability, and several aspects of the presentation, which are limitations/aspects that should be addressed.
Decision: Accept (poster)