Affinely Adjustable Robust Linear Complementarity Problems
Affinely Adjustable Robust Linear Complementarity Problems
复制标题
仿射可调鲁棒线性互补问题
DOI：
--
复制
发表时间：
2020
影响因子：
3.1
通讯作者：
Martin Schmidt
中科院分区：
文献类型：
--
作者：
Christian Biefel;F. Liers;J. Rolfes;Martin Schmidt
线性互补问题是模拟许多实际相关情况的有力工具，例如市场均衡。它们还连接了数学的许多子领域，如博弈论、最优化和矩阵理论。尽管它们与优化密切相关，但LCP对不确定性的保护--特别是在稳健优化意义上--仍处于初级阶段。在过去的几年里，人们只使用严格和{Gamma}-健壮性的概念来研究鲁棒LCP。不幸的是，这两个概念都导致了不能保证健壮解决方案的存在的问题。在这篇文章中，我们考虑了仿射可调的鲁棒LCP。在后者中，允许通过在不确定性中仿射的函数来调整LCP解的一部分。我们证明了这种稳健性的概念允许分别建立不确定矩阵和向量情形解的强特征，由此可以得到解的存在性结果。对于不确定的LCP向量，我们还在LCP矩阵上给出解唯一的充分条件。此外，基于仿射可调鲁棒解的特征，我们推导出了允许求解相应的鲁棒解的混合整数规划公式。如果LCP矩阵是不确定的，则对每个标称矩阵进行解的刻画，即这些刻画特别地与标称矩阵的确定性无关。对于正定LCP矩阵，稳健解也是唯一的，但如果标称LCP矩阵不是正定的，唯一性和混合整数规划公式仍然是公开的问题。
Linear complementarity problems are a powerful tool for modeling many practically relevant situations such as market equilibria. They also connect many sub-areas 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 {Gamma}-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 to establish strong characterizations of solutions for the cases of uncertain matrix and vector, separately, from which existence results can be derived. For an uncertain LCP vector, 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 to solve the corresponding robust counterpart. 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 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.