From Inverse Optimization to Feasibility to ERM
Saurabh Mishra Anant Raj Sharan Vaswani
Inverse optimization involves inferring unknown parameters of an optimization
problem from known solutions, and is widely used in fields such as
transportation, power systems and healthcare. We study the contextual inverse
optimization setting that utilizes additional contextual information to better
predict the unknown problem parameters. We focus on contextual inverse linear
programming (CILP), addressing the challenges posed by the non-differentiable
nature of LPs. For a linear prediction model, we reduce CILP to a convex
feasibility problem allowing the use of standard algorithms such as alternating
projections. The resulting algorithm for CILP is equipped with a linear
convergence guarantee without additional assumptions such as degeneracy or
interpolation. Next, we reduce CILP to empirical risk minimization (ERM) on a
smooth, convex loss that satisfies the Polyak-Lojasiewicz condition. This
reduction enables the use of scalable first-order optimization methods to solve
large non-convex problems, while maintaining theoretical guarantees in the
convex setting. Finally, we experimentally validate our approach on both
synthetic and real-world problems, and demonstrate improved performance
compared to existing methods.