Γ-robust linear complementarity problems

Abstract

Complementarity problems are often used to compute equilibria made up of specifically coordinated solutions of different optimization problems. Specific examples are game-theoretic settings like the bimatrix game or energy market models like for electricity or natural gas. While optimization under uncertainties is rather well-developed, the field of equilibrium models represented by complementarity problems under uncertainty – especially using the concepts of robust optimization – is still in its infancy. In this paper, we extend the theory of strictly robust linear complementarity problems (LCPs) to Γ-robust settings, where existence of worst-case-hedged equilibria cannot be guaranteed. Thus, we study the minimization of the worst-case gap function of Γ-robust counterparts of LCPs. For box and ${\ell }_1$-norm uncertainty sets we derive tractable convex counterparts for monotone LCPs and study their feasibility as well as the existence and uniqueness of solutions. To this end, we consider uncertainties in the vector and in the matrix defining the LCP. We additionally study so-called ρ-robust solutions, i.e. solutions of relaxed uncertain LCPs. Finally, we illustrate the Γ-robust concept applied to LCPs in the light of the above mentioned classical examples of bimatrix games and market equilibrium modelling.

Keywords:

• Linear complementarity problems
• robust optimization
• optimization under uncertainty
• Γ-robustness
• tractable counterparts

2010 Mathematics Subject Classifications:

• 90C33
• 91B50
• 91A10
• 90Cxx
• 90C34

Acknowledgments

We also thank the Deutsche Forschungsgemeinschaft for their support within project A05 and B08 in the ‘Sonderforschungsbereich/Transregio 154 Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks’. The authors also thank three anonymous reviewers for their valuable comments.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This research has been performed as part of the Energie Campus Nürnberg and is supported by funding of the Bavarian State Government.