ABSTRACT

In this paper, we introduce the notion of robust solution of uncertain linear complementarity problems. We prove that, if robust counterpart to uncertain quadratic programming—a robust optimization problem, has a optimal solution, and the optimum value equals to zero, then is the robust solution of the uncertain linear complementarity problem. By probability theory, we discuss linear complementarity problems under a random symmetric uncertainty, and obtain sufficient and necessary conditions of almost reliable robust solution.

Keywords:Uncertain Linear Complementarity Problems, Robust Solution, A Random Symmetric Uncertainty

随机对称不确定集下的线性互补问题

吴 丹¹，韩继业²

¹河南科技大学，数学与统计学院，河南 洛阳

²中国科学院应用数学研究所，北京

收稿日期：2015年11月16日；录用日期：2015年12月6日；发布日期：2015年12月9日

摘 要

本文引入不确定线性互补问题鲁棒解的概念。而且，我们证明：如果不确定二次规划问题的robust Counterpart，这一鲁棒优化问题的存在最优解，并且最优值为0，那么就是不确定线性互补问题的鲁棒解。我们讨论当不确定集为随机对称分布时，线性互补问题的求解。借助于概率论知识，给出为almost reliable鲁棒解的充要条件。

关键词 :不确定线性互补问题，鲁棒解，随机对称不确定集

1. 引言

20世纪下半页以来，优化技术在自然科学、工程技术、经济管理、交通规划、网络设计等各个领域得到了广泛的应用。数学规划的经典范例是在输入数据准确知道并且等于某些额定值的假设条件下建立模型，并利用已有的数学规划方法求解模型得出最优解。然而，这种方法并没有考虑数据不确定性对模型的质量和可行性的影响[1] -[3] 。事实上，数据的不确定性是无处不在的。数据的不确定性会对优化问题的最优解和最优值造成一定的影响，那么这种影响是否会导致传统模型的解失去意义呢？Ben-Tal等人在中给了一个生产药品的线性优化问题实例，在该实例中，2%的数据扰动会使得最优值下降超过10%，这也说明在固定参数值后得到的最优解在这数据扰动下远远脱离可行性。类似地，Ben-Tal和Nemirovski曾对NETLIB线性规划问题库中的90个问题进行了数值实验，结果表明，0.01%数据扰动会使这90个问题当中的13个问题的最优解可行性遭到严重的破坏: 经过0.01%的数据变动后，最初的最优解不能满足某些约束，并且会超出这些约束的边界值50%甚至更多。这些实例说明，有些时候即使很小的数据扰动也会对优化问题带来较大的影响[4] -[7] 。本文以不确定线性互补问题为研究对象，借助于概率论知识，给出为almost reliable鲁棒解的充要条件。

2. 不确定线性互补问题

本文采用鲁棒优化技术研究不确定线性互补问题。首先，对于不确定线性互补问题：

(1)

给出鲁棒解的定义。

定义2.1令是一个实矩阵，是一个维向量，是一个不确定集，寻求，满足：

(2)

称上述问题的解为不确定线性互补问题的解。即若问题(2)的解存在，，则对任一，式子均成立。

显然，不确定线性互补问题已转化为对一系列，无数个线性互补问题的求解。对于这样的模型，像投影法、内点法、非光滑牛顿法以及光滑牛顿法等，这些常用的方法将不再适用。因此，我们的首要任务就是将这样一种未知的带有不确定集的线性互补问题转化为已知的拥有高效处理技术的最优化问题，甚至是互补问题来求解。

我们知道，对于线性互补问题的求解可以借助于二次规划问题：

(QP):

(3)

其中。

如果二次规划问题有解，并且最优值为0，即，那么最优解就是线性互补问题的解。

当为不确定输入数据元素，只知道它们属于某一不确定集合时，我们可得不确定二次规划问题：

(4)

根据鲁棒优化理论，定义问题(2)的robust counterpart (RC)。

定义2.2 确定一个不确定元素集合，我们称问题：

(RC)

(5)

其中为不确定二次规划问题的robust counterpart.称该问题的最优解为不确定二次规划问题的鲁棒最优解。

定理2.1 如果上述鲁棒优化问题(RC)的最优解存在并且最优值为0，则是不确定线性互补问题的鲁棒解。

3. 随机对称不确定集下的线性互补问题

定义3.1 不确定集的随机对称是指：不确定元素的真实值是由其额定值的随机对称扰动而获得的。

可以表示成：

.

其中，是上对称分布的相互独立的随机变量。

是上对称分布的相互独立的随机变量，为不确定水平。

如果问题含有随机变量，对于不确定线性互补问题解的理解，从以往对不等式确定性的满足转变为概率意义下的满足是十分必要的。特别是条件：

对于任一事件

和

即 (6)

的概率至多是，为给定的可靠水平。

定义 3.2：我们称满足条件(3)的解为不确定线性互补问题的almost reliable解。

令， (7)

，当时，。

其中，是上的相互独立的对称分布的随机变量。其中，的第列就是向量，，就是由转化而来。

那么，对于随机对称分布不确定集，问题(RC)就转化为：

(8)

其中，。

下面，我们将以问题(8)为模型，研究带有随机对称不确定集的线性互补问题。首先，给出如下著名结论。

引理3.1：设为给定的实数，为上对称分布的独立的随机变量。那么对于任意，有

(9)

利用上述引理，我们可得，当不确定集为随机对称分布时，线性互补问题的almost reliable鲁棒解的充要条件。

定理3.1：如果可以扩展为以下不等式组的解，

(10)

其中为一正系数。

那么，是不确定线性互补问题的almost reliable解，可靠水平。

证明 首先证明：如果可以扩展为以下优化问题的可行解，

(11)

其中为一正系数。

那么对于问题(8)，违反约束条件的概率至多为。

设为(2.29)的可行解，首先考虑违反约束条件的概率：

有引理3.1可知

同理，可得约束条件的违反概率。

由于，不妨设事件A：

事件B：

由

所以，

综上所述，对于问题(8)，由(10)得到的，违反约束条件的概率至多为。

由定理2.1和定义3.2可推得，如果存在可以扩展为下述不等式组的解，

(12)

则是不确定线性互补问题的almost reliable解，可靠水平为。

假设满足(12)条件②~⑥，则可推得

从而条件①为，也就是，并且。

，由，以及，，可得。

若，当然有。

若，由可得，即。

所以，可推得。再由(12)，就等价于

特别是，当，(10)就转化为

(13)

基金项目

国家自然科学基金资助项目(11426091, 11471102)。

文章引用

吴丹,韩继业. 随机对称不确定集下的线性互补问题
Linear Complementarity Problems under a Random Symmetric Uncertainty[J]. 应用数学进展, 2016, 05(01): 1-7. http://dx.doi.org/10.12677/AAM.2016.51001

参考文献 (References)