On robust solutions to uncertain linear complementarity problems and their variants
From MaRDI portal
Abstract: A popular approach for addressing uncertainty in variational inequality problems is by solving the expected residual minimization (ERM) problem. This avenue necessitates distributional information associated with the uncertainty and requires minimizing nonconvex expectation-valued functions. We consider a distinctly different approach in the context of uncertain linear complementarity problems with a view towards 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 amongst the first efforts to comprehensively address such problems in a distribution-free environment, we show that under specified assumptions on the uncertainty sets, the robust solutions to uncertain monotone linear complementarity problem can be tractably obtained through the solution of a single convex program. We also define uncertainty sets that ensure that robust solutions to non-monotone generalizations can also be obtained by solving convex programs. More generally, robust counterparts of uncertain non-monotone LCPs 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.
Recommendations
Cites work
- A class of gap functions for variational inequalities
- A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
- A note on the existence of traffic equilibria
- Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets
- Expected Residual Minimization Method for Stochastic Linear Complementarity Problems
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Hidden convexity in some nonconvex quadratically constrained quadratic programming
- scientific article; zbMATH DE number 1418964 (Why is no real title available?)
- scientific article; zbMATH DE number 2202840 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Nash Equilibrium Problems With Scaled Congestion Costs and Shared Constraints
- NP-completeness of the linear complementarity problem
- On global optimization with indefinite quadratics
- Randomized algorithms for probabilistic robustness with real and complex structured uncertainty.
- Robust integer programming
- Robust optimization
- Robust solution of monotone stochastic linear complementarity problems
- Robust solutions to uncertain linear complementarity problems
- Spatial oligopolistic equilibria with arbitrage, shared resources, and price function conjectures.
- Stochastic R₀ Matrix Linear Complementarity Problems
- Stochastic algorithms for exact and approximate feasibility of robust LMIs
- Stochastic variational inequalities: residual minimization smoothing sample average approximations
- The ellipsoid method and its consequences in combinatorial optimization
- Theory and applications of robust optimization
Cited in
(21)- Adjustable robust solutions of uncertain linear programs
- Two-stage stochastic variational inequalities: an ERM-solution procedure
- Expected residual minimization formulation for a class of stochastic linear second-order cone complementarity problems
- Nonconvex robust programming via value-function optimization
- Games with distributionally robust joint chance constraints
- Stability of the linear complementarity problem properties under interval uncertainty
- Stochastic R₀ matrix linear complementarity problems: the Fischer-Burmeister function-based expected residual minimization
- Robust solutions to uncertain linear complementarity problems
- Robust market equilibria under uncertain cost
- Semidefinite complementarity reformulation for robust Nash equilibrium problems with Euclidean uncertainty sets
- Γ-robust linear complementarity problems
- Affinely adjustable robust linear complementarity problems
- Uncertain linear systems of equations: strong solvability and strong feasibility
- The distributionally robust complementarity problem
- Robust weighted expected residual minimization formulation for stochastic vector variational inequalities
- Unconstrained optimization reformulation for stochastic nonlinear complementarity problems
- Distributionally robust stochastic variational inequalities
- Γ‐robust linear complementarity problems with ellipsoidal uncertainty sets
- Sample average approximation of conditional value-at-risk based variational inequalities
- Existence of solutions to \Gamma -robust counterparts of gap function formulations of uncertain LCPs with ellipsoidal uncertainty sets
- Linear complementarity problems with uncertain variables
This page was built for publication: On robust solutions to uncertain linear complementarity problems and their variants
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828336)
