Γ-robust linear complementarity problems. (4th March 2022)

• Record Type: Journal Article
• Authors: Krebs, Vanessa; Schmidt, Martin
• Is Part Of: Optimization methods and software. Volume 37:Number 2(2022)
• Page Start: 658
• Page End: 691
• Publication Date: 2022-03-04
• Subjects: Linear complementarity problems -- robust optimization -- optimization under uncertainty -- Γ-robustness -- tractable counterparts; 90C33 -- 91B50 -- 91A10 -- 90Cxx -- 90C34; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1825708
• Languages: English
• ISSNs: 1055-6788

Abstract

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 ℓ 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.