集群環(huán)境下的并行內(nèi)點(diǎn)最優(yōu)化算法研究與實(shí)現(xiàn).pdf

1、集群計(jì)算為求解大規(guī)模、超大規(guī)模的應(yīng)用問題提供了強(qiáng)有力的工具,是計(jì)算科學(xué)領(lǐng)域的研究重點(diǎn)。隨著集群計(jì)算技術(shù)的發(fā)展,近10年來,并行最優(yōu)化算法的研究與應(yīng)用引起了研究人員的廣泛關(guān)注,特別是對一些具有特殊結(jié)構(gòu)的最優(yōu)化問題的并行算法的探索和研究,已經(jīng)取得了豐碩的成果。
　　 具有多項(xiàng)式時間復(fù)雜度的內(nèi)點(diǎn)算法(InteriorPointMethod,IPM)建立了線性規(guī)劃問題(LinearProgramming,LP)和非線性規(guī)劃問題(Nonl

2、inearProgramming,NLP)在理論和算法上的聯(lián)系。IPM對于求解大規(guī)模問題具有很強(qiáng)的優(yōu)勢。若能充分利用當(dāng)前Cluster的體系結(jié)構(gòu)特征,挖掘大規(guī)模問題內(nèi)點(diǎn)最優(yōu)化算法的數(shù)據(jù)特征,并設(shè)計(jì)有效的消息傳遞與共享存儲混合模式的并行內(nèi)點(diǎn)最優(yōu)化算法,將可以大大減少并行算法的通信開銷,提高并行算法的加速比。因此,基于IPM理論和現(xiàn)有計(jì)算平臺的特征,研究并設(shè)計(jì)更加快速的內(nèi)點(diǎn)最優(yōu)化算法對于最優(yōu)化問題的并行算法研究和實(shí)際應(yīng)用具有十分重要的科學(xué)意

3、義。
　　 本文首先結(jié)合內(nèi)點(diǎn)算法框架,對分塊帶邊結(jié)構(gòu)線性規(guī)劃的修正方程進(jìn)行了分析,導(dǎo)出了其簡化和最簡修正方程,并證明了最簡修正方程的系數(shù)矩陣的正定性。再結(jié)合解耦技術(shù),給出了修正方程的并行分解回代解法,并將該求解過程集成入內(nèi)點(diǎn)算法框架,設(shè)計(jì)并實(shí)現(xiàn)了分塊帶邊結(jié)構(gòu)線性規(guī)劃問題的并行內(nèi)點(diǎn)算法,為內(nèi)點(diǎn)算法求解特殊結(jié)構(gòu)優(yōu)化問題的并行化設(shè)計(jì)提供了一種新的思路。接著,本文分析了結(jié)構(gòu)化二次規(guī)劃的修正方程結(jié)構(gòu),并對其系數(shù)矩陣進(jìn)行重新排列,形成分塊箭

4、形結(jié)構(gòu),并采用并行分解回代法求解,設(shè)計(jì)了結(jié)構(gòu)化二次規(guī)劃問題的并行內(nèi)點(diǎn)算法。最后,基于MatlabPCT,給出了分塊帶邊結(jié)構(gòu)線性規(guī)劃和結(jié)構(gòu)化二次規(guī)劃問題的并行內(nèi)點(diǎn)算法實(shí)現(xiàn),并進(jìn)行了數(shù)值測試。數(shù)值測試實(shí)驗(yàn)結(jié)果表明,這兩個算法具有很好的加速比和可擴(kuò)展性,適合求解具有分塊帶邊結(jié)構(gòu)的大規(guī)模線性規(guī)劃問題和結(jié)構(gòu)化大規(guī)模QP問題。
　　 綜上,本文闡述了具有特殊結(jié)構(gòu)的最優(yōu)化問題進(jìn)行并行化算法設(shè)計(jì)的可能性,并給出了兩類特殊問題的并行算法設(shè)計(jì)與實(shí)現(xiàn)