Approximate Bilevel Programming via Pareto Optimization for Imputation and Control of Optimization and Equilibrium Models

We consider the problem of imputing the function that describes an optimization or equilibrium process from noisy partial observations of nearly optimal (possibly non-cooperative) decisions. We generalize existing inverse optimization and variational inequality problems to construct a novel class of multi-objective optimization problems: approximate bilevel programs. In this class, the “ill” nature of the complementary condition prevalent in bilevel programming is avoided, and residual functions commonly used for the design and analysis of iterative procedures, are a powerful tool to study approximate solutions to optimization and equilibrium problems. In particular, we show that duality gaps provide stronger bounds than ℓp norms of KKT residuals. The weighted criterion method is in some sense equivalent to existing formulations in the case of full observations. Our novel approach allows to solve bilevel and inverse problems under a unifying framework, via block coordinate descent, and is demonstrated on 1) consumer utility estimation and pricing and 2) latency inference in the road network of Los Angeles.