TY - JOUR

T1 - On robust solutions to uncertain linear complementarity problems and their variants

AU - Xie, Yue

AU - Shanbhag, Uday V.

N1 - Publisher Copyright:
© 2016 Society for Industrial and Applied Mathematics.

PY - 2016

Y1 - 2016

N2 - 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 a fine 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.

AB - 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 a fine 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.

UR - http://www.scopus.com/inward/record.url?scp=85007173601&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85007173601&partnerID=8YFLogxK

U2 - 10.1137/15M1010427

DO - 10.1137/15M1010427

M3 - Article

AN - SCOPUS:85007173601

SN - 1052-6234

VL - 26

SP - 2120

EP - 2159

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 4

ER -