REVIEW 4 major objections 5 minor 31 references
Inverse Optimization via Learning Feasible Regions
T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read With a known linear objective, inverse optimization can learn the feasible region of a decision problem from observed input–decision pairs.
desk verdict A genuinely new hypothesis class for inverse constraint learning with tractable reformulations, but the paper doesn't secure the claim that it recovers the true feasible region. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the hypothesis class in Equation (7): $g_\theta(x,s)=\min_{z\in Z} \|x - A_\theta(s)z - b_\theta(s)\|$, with $Z=\{z\in\mathbb{R}^p: Hz-h\in K\}$ a fixed conic primitive set. The feasible region of the learned optimization model is exactly the affine image $A_\theta(s)Z+b_\theta(s)$, so the latent variable $z$ provides a switching mechanism that can select extreme points of a polytopic primitive and hence reproduce discontinuous policies. For a known linear objective $c(s)^\top x$, the suboptimality constraint is dualized by conic linear programming duality into the stationarity condition $c(s)^\top A_\theta(s)-\lambda^\top H=0$ and the inequality $c(s)^\top(x+\gamma-b_\theta(s))-\lambda^\top h\le 0$; this removes the inner optimization and leaves only the bilinear term $A_\theta(s_i)z_i$, which the algorithms handle by block coordinate descent, a convex restriction, or bilinear-term linearization for the MILP cases.
What would settle it
Run the method on data from a linear program whose feasible region is a polytope with seven extreme points while setting the primitive simplex to $p=3$. If the training loss stays strictly positive for arbitrarily many clean samples, the hypothesis class cannot represent the true feasible region; if it reaches zero, the learned region necessarily differs from the true one, so structural recovery is not identifiable.
Extended reading notes
Core claim
The central claim is that the hypothesis class $g_\theta(x,s)=\min_{z\in Z} \|x - A_\theta(s)z - b_\theta(s)\|$, with $Z$ a fixed conic primitive set and $A_\theta(s), b_\theta(s)$ affine in $s$, is rich enough to represent the feasible regions of a class of forward optimization problems with known linear objectives, while keeping training tractable. The paper proves an exact reformulation (Theorem 3.3) of the two proposed losses in which the suboptimality condition is dualized, leaving only the bilinear product $A_\theta(s_i)z_i$ as the nonconvexity; when $A_\theta$ is restricted to a positive scalar the training problem becomes convex (Proposition 3.7), and when $Z$ is discrete or $A_\theta$ is binary it becomes a mixed-integer linear program (Proposition D.1). On the power-system experiments, the learned feasible regions match or beat an objective-only quadratic-cost baseline and recover the network topology with four lines instead of five while still reaching zero training loss, illustrating both expressiveness and the absence of identifiability.
Load-bearing premise
Everything rests on the user choosing a primitive set $Z$ whose affine image can contain the true optimal-decision set of the forward problem; the paper gives no rule for picking $Z$'s shape or dimension, and the experiments hand-select a simplex or a box to match the known problem structure.
Editorial extensions
If this is right
- A user with a known linear objective can infer the constraint set, not just the objective, from observed decisions.
- Discontinuous, switching policies such as generator dispatch changing at a cost threshold become representable, which objective-only quadratic models cannot capture.
- For the scale-and-translate restriction of the hypothesis class, the training problem is exactly a convex program, and for binary primitive variables or binary matrices it is exactly a mixed-integer linear program, so off-the-shelf solvers can certify the training loss.
- In the network-recovery experiment, the approach identifies a compatible topology without enumerating all candidate networks, reducing the search time from about 45 minutes of enumeration to 23.5 seconds.
- When the primitive class contains the true optimal-decision set, zero training loss implies the learned model reproduces the observed optimal solutions, per the full-characterization property.
Reading between the lines
- A testable extension outside the paper: the binary-matrix MILP reformulation has complexity independent of dataset size, so the same machinery could serve as a structure-discovery tool for any linear-program-based decision process with unknown connectivity or logical constraints.
- The choice of primitive set is a model-selection problem analogous to choosing basis functions in regression; the paper's zero-loss recovery with a 4-line instead of 5-line network shows that training loss alone cannot certify structural identifiability, so consistency questions remain open.
- Because the true suboptimality loss coincides with the smart predict-then-optimize loss, learned feasible regions could be plugged into downstream predict-then-optimize pipelines where the optimization's feasible set is itself estimated from data.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a method for inverse optimization (IO) in which the feasible region, not only the objective, is learned from input-decision data. The constraint hypothesis class is g_theta(x,s) = min_{z in Z} ||x - A_theta(s)z - b_theta(s)||, where Z is a fixed conic primitive set and A_theta, b_theta are affine in the signal s. Two losses are introduced, a predictability loss and a suboptimality loss, and reformulated as lifted programs with bilinear terms for a known linear objective (Theorem 3.3). For restricted hypothesis classes, convex and mixed-integer linear reformulations are given. A block-coordinate gradient algorithm with adaptive smoothing is proposed, and numerical experiments on synthetic problems and power-system network-flow problems are reported, including recovery of a transmission network structure.
Significance. If the claims hold, this is a useful step beyond objective-only inverse optimization: the hypothesis class in (7) can represent policies with discontinuities, and the MILP/convex reformulations offer off-the-shelf training for restricted classes. The paper deserves credit for stating the full-characterization property in Proposition 2.1, for explicitly acknowledging the failure to recover the true 5-line network in Section 4.2, and for identifying the primitive-set relationship as a limitation. However, the exactness of the reformulation is conditional on an unstated constraint qualification, the convergence proof in Proposition 3.6 is not valid as written, and the identifiability gap means the phrase "learning the feasible region" is currently an overstatement.
major comments (4)
- [Theorem 3.3, Lemma B.1] The reformulation of the suboptimality condition J_theta(x,s) <= 0 via the conic dual of min_{z in Z} c(s)^T(A_theta(s)z + b_theta(s)) requires strong duality. No Slater condition or other constraint qualification is stated for the conic set Z = {z : Hz - h in K}. If K has empty interior or the affine image of Z is degenerate, the dual value can differ from the primal value, so the equivalences in (16a)-(16b) and hence the exactness claim in Theorem 3.3 are not established. This also affects the convex reformulation in Proposition 3.7 and the MILP reformulation in Proposition D.1, which inherit the same dualization. Please add an explicit constraint-qualification assumption, verify it in the examples, or reframe the reformulations as relaxations.
- [Proposition 3.6] The convergence proof applies gradient descent with Armijo steps to the loss as a function of the matrices A_k, but the loss is not shown to be differentiable or smooth. The gradient formula in (11) relies on KKT multipliers of the lifted problem, and for a nonsmooth nonconvex value function the Armijo rule is not defined and monotone decrease of the loss is not guaranteed. The fact that the z/block is solved by a convex program for fixed A does not by itself make the A-update a descent step. As written, the proposition claims convergence to a local optimum without supporting assumptions; it should either be weakened to a heuristic statement or proved under explicit regularity, boundedness, and differentiability assumptions.
- [Section 4.2, Remark 3.1] The identifiability of the feasible region is not addressed. Section 4.2 reports zero training loss while recovering a 4-line network instead of the true 5-line network, and the authors state that "even with 4 lines, the recovered problem is able exactly match the observed data and achieve zero loss." Thus zero loss is compatible with a structurally wrong feasible region. Remark 3.1 gives no rule for selecting the primitive set Z or its dimension p beyond increasing flexibility. Without an identifiability or consistency result specifying conditions on Z, the signal distribution, and the loss under which the affine image converges to the true optimal-decision set, the central claim that the method learns the feasible region is not supported. Please add such conditions or reframe the contribution as learning a feasible region that rationalizes the observed decisions.
- [Section 2.2, Tables 2-3] The statement "by definition ell^p_theta = ell^p" is not correct in general: ell^p_theta is the sample predictability loss evaluated with the learned constraint g_theta, while ell^p is the true predictability loss using the unknown true constraint. As Figure 2 itself notes, the two coincide only when optimal solutions are unique for both the true and recovered problems, a condition not verified in the experiments. The combined column "ell^p_theta/ell^p" in Tables 2 and 3 is therefore ambiguous and the out-of-sample comparison is partly unsupported; please report the two metrics separately or state and check the uniqueness condition.
minor comments (5)
- [Appendix E, Eq. (25)] The expression ||gamma_i^2|| is not well-formed, and the prox function d(beta) = (1/2)||beta + gamma_i/epsilon||^2 depends on the optimization variable gamma_i, which is not allowed in Nesterov's smoothing framework. The derivation should be corrected or explicitly labeled as a heuristic motivation.
- [Algorithm 2] Line 4 of Algorithm 2 uses the gradient formula (11) for the smoothed problem, but the dual multipliers beta* and mu* are not defined in the statement of (12); please define them or clarify that they are multipliers of the smoothed program.
- [Appendix H.1] There are several typographical errors, including "tje primitive set" in Appendix H.1 and "reformuation" in the title of Proposition D.1; the manuscript would benefit from a copyediting pass.
- [Section 4.2] The text refers to "Figure 3 (bottom) in the appendix," but Figure 3 appears in the main text; please make the cross-reference consistent.
- [Section 3.3] The McCormick inequalities used to linearize the bilinear terms are mentioned without a citation; a reference would help readers implement the MILP reformulation.
Circularity Check
No significant circularity; the training/evaluation loop is self-contained. The only definitional tautology is Proposition 2.1, where the loss is constructed so that zero loss is equivalent to model optimality; the central claim otherwise rests on independent reformulations and experiments.
-
self definitional
[Section 2.1, Proposition 2.1, around Eqs. (5a) and (5b)]
"The following proposition shows that the proposed loss functions (5) are well defined, in the sense that for any θ ∈ Θ and (x, s) in the training dataset, the loss ℓθ(x, s) is zero if and only if x is also an optimal solution of (2). ... We term this property as full characterization. ... ℓθ(x, s) = 0 ⇐⇒ x ∈ [arg min_{y∈R^n} fθ(y,s) s.t. gθ(y,s) ≤ 0]."
The predictability loss in (5a) is defined as min ∥γ∥ subject to gθ(x+γ,s) ≤ 0 and Jθ(x+γ,s) ≤ 0. Therefore ℓpθ(x,s)=0 holds exactly when γ=0 satisfies both constraints, i.e., exactly when x is feasible and optimal in the hypothesized model (2). The suboptimality loss (5b) has the same structure with slacks γf and γo. Proposition 2.1 thus restates the defining property of the loss rather than deriving an independent characterization. This is a useful sanity check but is not an external source of evidence; the 'full characterization' is encoded in the loss by construction.
full rationale
The core derivation chain is not circular. Theorem 3.3 obtains the training reformulations from the explicit definition of gθ in (7) and from dualization of the linear-objective optimality condition; Proposition 3.7 and Proposition D.1 are algebraic and MILP reformulations of those programs. Algorithm 2 is a standard coordinate-descent/smoothing scheme, and Proposition 3.6 is a monotone-convergence argument for that scheme. The losses are minimized on training data and evaluated on held-out data, so the reported out-of-sample quantities are not fitted values. Self-citations to Aswani et al. (2018) and Mohajerin Esfahani et al. (2018) are background attributions for the two loss constructions, not load-bearing derivations of the paper's results. The genuine weakness is the identifiability gap shown in Section 4.2, where a 4-line network achieves zero loss instead of the true 5-line network; that is underdetermination of the feasible region by the data, not circularity. The paper's own limitation (iii) acknowledges the nontrivial link between the primitive set and the induced policy. The only circular element is Proposition 2.1, which is a definitional tautology rather than a substantive theorem, and it does not by itself invalidate the learning framework.
Assumptions & free parameters
free parameters (3)
- Primitive set dimension p =
3, 6, 9 in experiments (user-chosen)
- Smoothing coefficients epsilon_1, epsilon_2 =
initial 1, doubled when slack change is small
- Step size eta and Armijo parameters =
not specified numerically
assumptions (4)
- domain assumption Strong duality holds for the inner linear program in the reformulations (Slater's condition or an equivalent cone qualification).
- domain assumption The forward and learned problems have known linear objectives and convex feasible sets.
- ad hoc to paper The chosen primitive set Z and affine map Aθ(s)z+bθ(s) can express the true optimal-decision set of the data-generating problem.
- ad hoc to paper The loss as a function of A is smooth enough for Armijo gradient descent to monotonically decrease it.
invented entities (1)
-
Latent variable z and primitive set Z
Cite this review
Pith. "Pith review of Inverse Optimization via Learning Feasible Regions." pith.science (2026). https://pith.science/paper/TY237Y62
@misc{pith2026250515025,
author = {Pith},
title = {Pith review of: Inverse Optimization via Learning Feasible Regions},
year = {2026},
howpublished = {\url{https://pith.science/paper/TY237Y62}},
note = {Machine review of arXiv:2505.15025}
}
read the original 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.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
-
[2]
Ajayi, T., Lee, T., and Schaefer, A. J. Objective selection for cancer treatment: An inverse optimization approach. Operations Research, 70 0 (3): 0 1717--1738, 2022
work page 2022
-
[3]
Akhtar, S. A., Kolarijani, A. S., and Esfahani, P. M. Learning for control: An inverse optimization approach. IEEE Control Systems Letters, 6: 0 187--192, 2021
work page 2021
-
[4]
Inverse optimization with noisy data
Aswani, A., Shen, Z.-J., and Siddiq, A. Inverse optimization with noisy data. Operations Research, 66 0 (3): 0 870--892, 2018
2018
-
[5]
Inverse optimization for assessing emerging technologies in breast cancer screening
Ayer, T. Inverse optimization for assessing emerging technologies in breast cancer screening. Annals of Operations Research, 230: 0 57--85, 2015
work page 2015
-
[6]
Bampou, D. and Kuhn, D. Scenario-free stochastic programming with polynomial decision rules. In 2011 50th IEEE Conference on Decision and Control and European Control Conference, pp.\ 7806--7812, 2011
work page 2011
-
[7]
Emulating the expert: inverse optimization through online learning
B \"a 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-Volume 70, pp.\ 400--410, 2017
work page 2017
-
[8]
Convex optimization algorithms
Bertsekas, D. Convex optimization algorithms. Athena Scientific, 2015
work page 2015
Show all 31 references
-
[9]
Bertsekas, D. P. Nonlinear programming. Athena Scientific Optimization and Computation Series. Athena Scientific, Belmont, MA, second edition, 1999
1999
-
[10]
Bertsimas, D., Gupta, V., and Paschalidis, I. C. Data-driven estimation in equilibrium using inverse optimization. Mathematical Programming, 153: 0 595--633, 2015
2015
-
[11]
Chan, T. C. and Kaw, N. Inverse optimization for the recovery of constraint parameters. European Journal of Operational Research, 282 0 (2): 0 415--427, 2020
2020
-
[12]
An inverse optimization approach for a capacitated vehicle routing problem
Chen, L., Chen, Y., and Langevin, A. An inverse optimization approach for a capacitated vehicle routing problem. European Journal of Operational Research, 295 0 (3): 0 1087--1098, 2021
2021
-
[13]
and Lohse, S
Dempe, S. and Lohse, S. Inverse linear programming. In Recent Advances in Optimization, pp.\ 19--28. Springer, 2006
2006
-
[14]
Offline reinforcement learning via inverse optimization
Dimanidis, I., Ok, T., and Mohajerin Esfahani, P. Offline reinforcement learning via inverse optimization. preprint available at arXiv:2502.20030, 2025
2025
-
[15]
Generalized inverse optimization through online learning
Dong, C., Chen, Y., and Zeng, B. Generalized inverse optimization through online learning. Advances in Neural Information Processing Systems, 31, 2018
2018
-
[16]
predict, then optimize
Elmachtoub, A. N. and Grigas, P. Smart “predict, then optimize”. Management Science, 68 0 (1): 0 9--26, 2022
2022
-
[17]
and Mahmoudzadeh, H
Ghobadi, K. and Mahmoudzadeh, H. Inferring linear feasible regions using inverse optimization. European Journal of Operational Research, 2020
2020
-
[18]
and Hamacher, H
G \"u ler, c. and Hamacher, H. W. Capacity inverse minimum cost flow problem. Journal of Combinatorial Optimization, 19 0 (1): 0 43--59, 2010
2010
-
[19]
Imputing a convex objective function
Keshavarz, A., Wang, Y., and Boyd, S. Imputing a convex objective function. In 2011 IEEE international symposium on intelligent control, pp.\ 613--619, 2011
2011
-
[20]
M., Bretas, A
Leon, L. M., Bretas, A. S., and Rivera, S. Quadratically constrained quadratic programming formulation of contingency constrained optimal power flow with photovoltaic generation. Energies, 13 0 (13): 0 3310, 2020
2020
-
[21]
Li, J. Y.-M. Inverse optimization of convex risk functions. Management Science, 67 0 (11): 0 7113--7141, 2021
2021
-
[22]
A data-driven stackelberg market strategy for demand response-enabled distribution systems
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, 10 0 (3): 0 2345--2357, 2018
2018
-
[23]
A., and Kuhn, D
Mohajerin Esfahani, P., Shafieezadeh-Abadeh, S., Hanasusanto, G. A., and Kuhn, D. Data-driven inverse optimization with imperfect information. Mathematical Programming, 167: 0 191--234, 2018
2018
-
[24]
Smooth minimization of non-smooth functions
Nesterov, Y. Smooth minimization of non-smooth functions. Mathematical programming, 103: 0 127--152, 2005
2005
-
[25]
Nesterov, Y. et al. Lectures on Convex Optimization, volume 137. Springer, 2018
2018
-
[26]
M., Zugno, M., and Madsen, H
Saez-Gallego, J., Morales, J. M., Zugno, M., and Madsen, H. A data-driven bidding model for a cluster of price-responsive consumers of electricity. IEEE Transactions on Power Systems, 31 0 (6): 0 5001--5011, 2016
2016
-
[27]
Learning linear programs from optimal decisions
Tan, Y., Terekhov, D., and Delong, A. Learning linear programs from optimal decisions. arXiv preprint arXiv:2006.08923, 2020
2006 arXiv
-
[28]
Data-driven pricing strategy for demand-side resource aggregators
Xu, Z., Deng, T., Hu, Z., Song, Y., and Wang, J. Data-driven pricing strategy for demand-side resource aggregators. IEEE Transactions on Smart Grid, 9 0 (1): 0 57--66, 2016
2016
-
[29]
Learning in inverse optimization: Incenter cost, augmented suboptimality loss, and algorithms
Zattoni Scroccaro, P., Atasoy, B., and Mohajerin Esfahani, P. Learning in inverse optimization: Incenter cost, augmented suboptimality loss, and algorithms. Operations Research, 2024
2024
-
[30]
Inverse optimization for routing problems
Zattoni Scroccaro, P., van Beek, P., Mohajerin Esfahani , P., and Atasoy, B. Inverse optimization for routing problems. Transportation Science, 59 0 (2): 0 301--321, 2025
2025
-
[31]
and Paschalidis, I
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
2017
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.