On Robust Solutions to Uncertain Linear Complementarity Problems and their Variants

Abstract

A popular approach for addressing uncertainty in variational inequality problems requires solving the expected residual minimization problem [X. Chen and M. Fukushima, Math. Oper. Res., 30 (2005), pp. 1022--1038, X. Chen, R. J.-B. Wets, and Y. Zhang, SIAM J. Optim., 22 (2012), pp. 649--673]. This avenue necessitates distributional information associated with the uncertainty and requires minimizing a suitably defined nonconvex expectation-valued function. Alternatively, we consider a distinctly different approach in the context of uncertain linear complementarity problems (LCPs) with a view toward obtaining robust solutions. Specifically, we define a robust solution to a complementarity problem as one that minimizes the worst case of the gap function. In what we believe is among the first efforts to comprehensively address such problems in a distribution-free environment, under prescribed assumptions on the uncertainty sets, the robust solutions to the uncertain monotone LCP can be tractably obtained through the solution of a finite-dimensional convex program. We also characterize uncertainty sets that allow for computing robust solutions to certain nonmonotone generalizations through the solution of finite-dimensional convex programs. In addition, a similar tractability result is presented for general uncertainty sets characterized by efficient separation oracles. More generally, robust counterparts of uncertain nonmonotone LCPs with suitably prescribed uncertainty sets are proven to be low-dimensional nonconvex quadratically constrained quadratic programs. We show that these problems may be globally resolved by customizing an existing branching scheme. We further extend the tractability results to include uncertain affine variational inequality problems defined over uncertain polyhedral sets as well as to hierarchical regimes captured by mathematical programs with uncertain complementarity constraints. Preliminary numerics on uncertain linear complementarity and traffic equilibrium problems suggest that the presented avenues hold promise.