liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Affinely Adjustable Robust Linear Complementarity Problems
Friedrich-Alexander-Universität Erlangen-Nürnberg, Erlangen, Germany.ORCID iD: 0000-0001-8310-7724
Friedrich-Alexander-Universität Erlangen-Nürnberg, Erlangen, Germany.
Friedrich-Alexander-Universität Erlangen-Nürnberg, Erlangen, Germany.ORCID iD: 0000-0002-5415-1715
Department of Mathematics, Trier University, Trier, Germany.ORCID iD: 0000-0001-6208-5677
2022 (English)In: SIAM Journal on Optimization, ISSN 1052-6234, E-ISSN 1095-7189, Vol. 32, no 1, p. 152-172Article in journal (Refereed) Published
Abstract [en]

Linear complementarity problems (LCPs) are a powerful tool for modeling many practically relevant situations such as market equilibria. They also connect many subareas of mathematics like game theory, optimization, and matrix theory. Despite their close relation to optimization, the protection of LCPs against uncertainties---especially in the sense of robust optimization---is still in its infancy. During the last years, robust LCPs have only been studied using the notions of strict and -robustness. Unfortunately, both concepts lead to the problem that the existence of robust solutions cannot be guaranteed. In this paper, we consider affinely adjustable robust LCPs. In the latter, a part of the LCP solution is allowed to adjust via a function that is affine in the uncertainty. We show that this notion of robustness allows us to establish strong characterizations of solutions for the cases of uncertain matrix and vector, separately, from which existence results can be derived. Our main results are valid for the case of an uncertain LCP vector. Here, we additionally provide sufficient conditions on the LCP matrix for the uniqueness of a solution. Moreover, based on characterizations of the affinely adjustable robust solutions, we derive a mixed-integer programming formulation that allows us to solve the corresponding robust counterpart. If, in addition, the certain LCP matrix is positive semidefinite, we prove polynomial-time solvability and uniqueness of robust solutions. If the LCP matrix is uncertain, characterizations of solutions are developed for every nominal matrix; i.e., these characterizations are, in particular, independent of the definiteness of the nominal matrix. Robust solutions are also shown to be unique for a positive definite LCP matrix, but both uniqueness and mixed-integer programming formulations still remain open problems if the nominal LCP matrix is not positive definite.

Place, publisher, year, edition, pages
Society for Industrial & Applied Mathematics (SIAM) , 2022. Vol. 32, no 1, p. 152-172
Keywords [en]
linear complementarity problems; adjustable robustness; robust optimization; existence; uniqueness
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-213815DOI: 10.1137/20m1359778ISI: 000765866300007Scopus ID: 2-s2.0-85126118387OAI: oai:DiVA.org:liu-213815DiVA, id: diva2:1960777
Funder
German Research Foundation (DFG), A05German Research Foundation (DFG), B06German Research Foundation (DFG), B08Available from: 2025-05-23 Created: 2025-05-23 Last updated: 2025-06-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Rolfes, Jan

Search in DiVA

By author/editor
Biefel, ChristianRolfes, JanSchmidt, Martin
In the same journal
SIAM Journal on Optimization
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 32 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf