云計(jì)算中大型線性規(guī)劃問題的外包方案研究.pdf

1、隨著云計(jì)算的快速普及和廣泛應(yīng)用，如何安全高效的將繁重的計(jì)算任務(wù)外包給云服務(wù)器已經(jīng)越來越受到人們的關(guān)注，尤其是那些計(jì)算資源有限的用戶。本文中，我們探討的是云計(jì)算中大型線性規(guī)劃的安全外包問題。線性規(guī)劃（LP）已經(jīng)在科學(xué)領(lǐng)域的各種場(chǎng)景中得到了廣泛的應(yīng)用，比如，網(wǎng)絡(luò)流問題、數(shù)據(jù)包路由、投資組合優(yōu)化和財(cái)務(wù)數(shù)據(jù)管理等方面。對(duì)資源有限的用戶來，求解大型的線性規(guī)劃問題是一筆非常大的計(jì)算開銷。因此，研究一種能夠安全高效的大型線性規(guī)劃問題的外包方案非常必要

2、。本文主要有以下幾個(gè)方面的工作：
　　1.研究了現(xiàn)有的線性規(guī)劃問題的外包方案，重點(diǎn)研究了基于轉(zhuǎn)換方法的安全外包方案，總結(jié)了現(xiàn)有方案的不足之處。
　　2.在完全惡意模型下，我們首次利用稀疏矩陣技術(shù)提出了一種大型線性規(guī)劃的外包算法。該算法能夠適用于任何類型的線性規(guī)劃問題，包括有可行解、無可行解和無界等三種情況。與目前最優(yōu)的算法相比（O(nρ),2<ρ≤3），我們所提出的算法只需要復(fù)雜度為O(n2)的計(jì)算開銷。
　　3.對(duì)上