On robust solutions to uncertain monotone linear complementarity problems (LCPs) and their variants

Abstract

Variational inequality and complementarity problems have found utility in modeling a range of optimization and equilibrium problems arising in engineering, economics, and the sciences. Yet, while there have been tremendous growth in addressing uncertainty in optimization, far less progress has been seen in the context of variational inequality problems, exceptions being the efforts to solve variational inequality problems with expectation-valued maps [1], [2]. Yet, in many instances, the goal lies in obtaining solutions that are robust to uncertainty. While the fields of robust optimization and control theory have made deep inroads into developing tractable schemes for resolving such concerns, there has been little progress in the context of variational problems. In what we believe is amongst the very first efforts to comprehensively address such problems in a distribution-free environment, we present an avenue for obtaining robust solutions to uncertain monotone affine complementarity problems defined over the nonnegative orthant. We begin with and mainly focus on showing that robust solutions to such problems can be tractably obtained through the solution of a single convex program. Importantly, we discuss how these results can be extended to account for uncertainty in the associated sets by generalizing the results to uncertain affine variational inequality problems defined over uncertain polyhedral sets.