文摘
水平分区数据的线性规划,等式约束矩阵分为组行。每一组向量矩阵的行和对应的右边是由不同的实体,这些实体不愿透露自己的行或右边向量组。计算线性规划的最优解在这种情况下,Mangasarian使用随机矩阵满秩的概率,但事件的概率1不是一个特定的事件,所以一个随机矩阵满秩的概率肯定不会发生。通过这种方式,解决原线性规划不等于安全线性规划的解决方案。我们使用了一个可逆的随机矩阵的缺点。可逆的随机矩阵原线性规划问题转化为一个安全的线性规划问题。这个安全的线性规划不会透露任何私人数据。
1。介绍
最近,人们已经变得对保护隐私感兴趣分类和数据挖掘1- - - - - -10),参与优化领域,特别是在线性规划(11- - - - - -15),数据分类或开采属于不同的实体,不愿意披露的数据。Mangasarian [13)提出了一种随机矩阵使原线性规划问题转化为一个安全的线性规划问题。当随机矩阵满秩(不是16),尤其是当实体相互碰撞,原线性规划问题并不等同于安全的线性规划问题。我们解决这个问题通过使用一个可逆矩阵乘以双方等式约束的线性规划。这个过程原线性规划转化为一个等价的线性规划,这安全线性没有透露任何私人数据。这个解决方案向量可以公开所有实体和应用。相反,这个算法可以防止实体相互碰撞。
在这里,我们定义一些符号。如果一个向量不是转置行向量的上标 ,向量将一个列向量。为一个向量 ,符号将代表th组件或th块组件。我们将定义两个向量的标量(内部)的产品和在 - - - - - -维真实空间作为 。符号 将代表一个真正的 矩阵。同样的,将代表的转置和将代表行或块的行和的th列或th块的列 。零矢量在真实空间的维度将用 。
2。保护隐私水平分区数据的线性规划
考虑下列线性规划:
在这里,由矩阵的 和右边的向量 ,分为水平块。的行数水平块记录 ,在哪里 。一个阶单位矩阵分为垂直的街区。的列数垂直块记录 ,在哪里 。每一块的行(一个b]对应指数集 , ,属于一个独特的实体,不愿意公开它的数据块或与其他实体分享它。我们将通过以下转换实现这个目标。
每个实体 ,选择自己的私有随机矩阵 ,相应的索引设置吗 。每个元素的值在时间间隔 。可以得到如下分解: 和 。定义
因为这个矩阵是一个严格对角占优矩阵,我们可以很容易得出结论,这个矩阵是一个可逆矩阵(17]。基于这一事实,我们定义以下操作:
根据上述讨论,最初的线性规划(1)转换成以下安全线性规划:
线性规划(1)和线性规划(4)有相同的解集自矩阵是可逆的。线性规划(4因为只有实体)是万无一失的知道 , 。其他实体无法计算和从 和 不知道随机矩阵 。我们把线性规划(4)作为一个安全的线性规划。是否线性规划(1)等价于线性规划(4)或不呢?让我们讨论下。
命题1。如果矩阵B是一个米可逆矩阵;然后,安全的线性规划(4)是解决当且仅当线性规划(1)是解决案例的解决方案集的两个线性程序是相同的。
证明。随着矩阵是一个
- - - - - -可逆矩阵,以下关系:
因此,可行区域的两个线性程序是相同的。再根据线性规划的目标函数(1)和线性规划(4),我们可以得出结论,两个线性程序有相同的解集。
下面的算法可以得到最好的解决线性编程(1没有透露任何私人数据。
3所示。制定保护隐私的算法
如部分所示2线性规划(1)是分给实体。我们提出了以下算法:步骤1。所有实体选择合适的实数 , 在一起。步骤2。假设矩阵有行, 。一个随机矩阵是生成的实体拥有矩阵 ,在哪里 。每个元素的值在区间(0,1),然后呢不是公开的。步骤3。实体拥有矩阵负责计算 和 ,结果传递到实体拥有矩阵 。然后,实体拥有矩阵负责计算 和 ,结果传递到实体拥有矩阵 。最后,实体拥有矩阵负责计算如下: 步骤4。利用线性规划(4计算最小值和目标函数的最优解,即最小值和最优解的线性规划的目标函数(1)。
备注1。通过该算法,解向量可以公开使用。然而,它没有透露任何实体的数据。
4所示。数值实验
线性规划:
我们能找到的最优解(8)是 。让 , , ,和 。
实体1生成一个随机矩阵这不是出版。请注意,
实体1公共矩阵乘积 和 。
实体2生成一个随机矩阵这不是出版。请注意,
实体2公开它的矩阵乘积 和 。
这些产品不透露任何私人数据,但是它可以用于计算约束矩阵和右边线性规划的安全。接下来,我们得到一个线性编程(11从线性规划)(4),相当于线性规划(8):
这个安全的线性规划的解决方案(11)是一样的,线性规划(8)。这个解决方案可以公开没有透露任何私人数据。
如果我们使用Mangasarian的研究(13水平分区)算法,提出了保护隐私的线性程序,线性规划(8)需要被转换成下列线性规划:
安全的线性规划的最优解(12)是 。这是不符合原来的线性规划的最优解(8)。这个错误的原因是随机矩阵 不是一个满秩矩阵。这样,最初的线性规划(8)不是相当于安全线性规划(12)。
数据可用性
使用的数据来支持本研究的结果包括在本文中。
的利益冲突
作者宣称没有利益冲突。
确认
这项工作是支持的铝铜带材料智能过程控制技术项目基于工业大数据(批准号2017 yfb0306404)。