Research map / Learning theory and algorithms / Combinatorial and search optimization
Inverse Optimization via Learning Feasible Regions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Learns linear-objective inverse optimization constraints via a latent-primitive-set hypothesis class, with predictability/suboptimality losses, adaptive-smoothing block coordinate descent, and convex/MILP reformulations.
Problem
Inverse optimization typically learns only objective functions because learning constraints (feasible regions) yields nonconvex training programs; the paper targets learning feasible regions for known linear objectives from input-decision pairs.
Approach
Parameterize the constraint function as a distance to an affine image of a conic primitive set with latent variable z, define predictability and suboptimality losses, and train via block coordinate descent with Nesterov-style adaptive smoothing; special cases admit exact convex or MILP reformulations.
Key results
- On the 5-region power system, the Algorithm 2 (adaptive smoothing) with p=6 simplex achieves out-of-sample true suboptimality loss 0.42 versus 4.96 for Gurobi p=6 subopt. (Table 1).
- For learning the power network structure, the MILP recovers a 4-line network achieving zero training loss, solved in 23.5 seconds versus an estimated 2.64 x 2^10 seconds for enumeration.
- Convex formulation (p=3) is fastest (0.31 s) but yields higher out-of-sample losses than the smoothed block coordinate descent.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the simplex primitive dimension from p=3 to p=6 (ablation) | Adaptive smoothing with predictability loss · 5-node power system test | predictability loss ℓθp / ℓp: 3.20 -> 1.91 | Helped |
| Increase the simplex primitive dimension from p=6 to p=9 (ablation) | Adaptive smoothing with predictability loss · 5-node power system test | predictability loss ℓθp / ℓp: 1.91 -> 1.58 | Helped |
| Increase the simplex primitive dimension from p=6 to p=9 (ablation) | Adaptive smoothing with suboptimality loss · 5-node power system test | true suboptimality loss: 0.42 -> 0.50 | Hurt |
| Learn a quadratic cost instead of the constraints | Inverse optimization for generation policy · 5-node power system test | predictability loss ℓθp / ℓp: 1.58 -> 2.58 | Hurt |
| Use the restricted convex formulation instead of the general hypothesis class | Inverse optimization for generation policy · 5-node power system test | predictability loss ℓθp / ℓp: 1.58 -> 3.36 | Hurt |
| Use adaptive smoothing rather than the unsmoothed algorithm (ablation) | Training with predictability loss · Noiseless power-system training example | training loss: 1.90 ± 0.36 -> (2.5 ± 7.2) × 10^{-4} | Helped |
| Use adaptive smoothing rather than the unsmoothed algorithm (ablation) | Training with suboptimality loss · Noiseless power-system training example | training loss: 0.03 ± 0.05 -> (8.6 ± 2.1) × 10^{-4} | Helped |
| Increase the number of noisy training examples from N=100 to N=1000 (ablation) | Convex formulation with predictability loss · Synthetic noisy test | true predictability loss ℓp: 0.03 -> 0 | Helped |
| Increase the simplex primitive dimension from p=1 to p=2 (ablation) | Proposed method with predictability loss · IEEE 14-bus test | predictability loss ℓθp / ℓp: 0.83 -> 0.43 | Helped |
| Use adaptive smoothing rather than Gurobi | Inverse optimization for generation policy, p=9 · 5-node power system test | predictability loss ℓθp / ℓp: 6.66 -> 1.58 | Helped |
| Learn the binary network structure with inverse optimization | Power network structure recovery · 5-node power system training data | predictability loss: zero loss | Helped |
Surprising findings
- The suboptimality loss performs better than predictability loss under vanilla gradient descent, which the authors attribute to it being a smoothed version of predictability loss.
- The recovered network has 4 lines versus 5 in the true network yet still achieves zero training loss.
Limitations
- Supports only known linear objectives, not quadratic or more complex objectives.
- Gradient-based algorithm relies on local search and may be trapped in local minima.
- Relationship between primitive set choice and resulting policy behavior is not well understood.
Experimental setup
Datasets: synthetic power network flow data (5-region and IEEE 14-bus) synthetic optimization data
Benchmarks: synthetic simplex/convex IO experiments 5-node power network IEEE 14-bus system
Metrics: predictability loss suboptimality loss true predictability loss true suboptimality loss training time
Baselines: quadratic objective learning Gurobi nonconvex solver enumeration-based network structure learning
Builds on: Nesterov smoothing predictability loss (prior IO work) SPO loss
Closest papers by meaning
- From Inverse Optimization to Feasibility to ERM (ICML 2024 · similarity 0.87)
- Scalable Kernel Inverse Optimization (NeurIPS 2024 · similarity 0.86)
- Conformal Inverse Optimization (NeurIPS 2024 · similarity 0.85)
- Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound (NeurIPS 2025 · similarity 0.85)
- Inverse Optimization Latent Variable Models for Learning Costs Applied to Route Problems (NeurIPS 2025 · similarity 0.84)
- Tight Generalization Bounds for Noiseless Inverse Optimization (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.