  In Inverse Optimization (IO), an expert agent solves an optimization problem
parametric in an exogenous signal. From a learning perspective, the goal is to
learn the expert's cost function given a dataset of signals and corresponding
optimal actions. Motivated by the geometry of the IO set of consistent cost
vectors, we introduce the "incenter" concept, a new notion akin to circumcenter
recently proposed by Besbes et al. (2023). Discussing the geometric and
robustness interpretation of the incenter cost vector, we develop corresponding
tractable convex reformulations, which are in contrast with the circumcenter,
which we show is equivalent to an intractable optimization program. We further
propose a novel loss function called Augmented Suboptimality Loss (ASL), a
relaxation of the incenter concept for problems with inconsistent data.
Exploiting the structure of the ASL, we propose a novel first-order algorithm,
which we name Stochastic Approximate Mirror Descent. This algorithm combines
stochastic and approximate subgradient evaluations, together with mirror
descent update steps, which is provably efficient for the IO problems with
discrete feasible sets with high cardinality. We implement the IO approaches
developed in this paper as a Python package called InvOpt. Our numerical
experiments are reproducible, and the underlying source code is available as
examples in the InvOpt package.
