求解互補(bǔ)問題的光滑牛頓算法.pdf

1、在優(yōu)化的研究領(lǐng)域中,有一類基本和重要的問題一互補(bǔ)問題(Complementarity Problems).這類問題發(fā)展非常迅速,且出現(xiàn)了各種各樣的互補(bǔ)問題.許多實際問題,例如力學(xué)、交通、經(jīng)濟(jì)、金融、控制等諸多領(lǐng)域的許多問題最終都可以轉(zhuǎn)化為互補(bǔ)問題.對互補(bǔ)問題的研究包括理論和算法兩個方面.前者主要研究問題解的存在性、唯一性、穩(wěn)定性以及靈敏度分析等性質(zhì);后者集中在如何設(shè)計有效算法并且進(jìn)行理論分析.然而,在20世紀(jì)90年代之前,這類問題一直是

2、難求解的問題.到了20世紀(jì)90年代中期,求解互補(bǔ)問題的各種重構(gòu)方法相繼被提出,很好地解決了互補(bǔ)問題求解難的問題.特別是在這些方法中,光滑牛頓算法尤為突出.本文旨在對求解幾類互補(bǔ)問題的光滑牛頓算法進(jìn)行研究.具體如下:
　　 首先,針對現(xiàn)在國際上研究非常熱的對稱錐互補(bǔ)問題(SCCP),利用歐氏若當(dāng)代數(shù)技術(shù),做了以下兩個研究工作.第一,定義了歐氏若當(dāng)代數(shù)上的正則化CHKS光滑函數(shù),在適當(dāng)?shù)臈l件下,這個光滑函數(shù)具有強(qiáng)制性.基于這個光滑函

3、數(shù),提出了光滑效用函數(shù)法和光滑型算法的一般框架.特別地,設(shè)計了一個具體的光滑牛頓算法,并且證明了它具有全局收斂性和局部二次收斂性.針對隨機(jī)產(chǎn)生的二階錐規(guī)劃問題,利用光滑牛頓算法做了若干數(shù)值試驗,得到了令人滿意的數(shù)值效果.第二,基于上面給出的正則化CHKS光滑函數(shù),提出了一類新的帶有參數(shù)的光滑函數(shù)族.而且在適當(dāng)?shù)臈l件下,這類光滑函數(shù)族同樣具有強(qiáng)制性.利用這類光滑函數(shù)族,設(shè)計了一種帶有參數(shù)的光滑牛頓算法,且在給定的條件下,此類算法具有全局收

4、斂性和局部二次收斂性.同時,算法對隨機(jī)產(chǎn)生的二階錐規(guī)劃問題以及著名的DIMACS測試題庫中實際的二階錐規(guī)劃問題進(jìn)行了數(shù)值試驗.試驗表明,隨著選擇參數(shù)的不同,計算的結(jié)果有著很大的差異.與相關(guān)文章設(shè)計的算法進(jìn)行比較,計算效果在某種程度上是非常有效的.
　　 其次,對標(biāo)準(zhǔn)的非線性互補(bǔ)問題(NCP)設(shè)計了一種非單調(diào)線搜索的正則化光滑牛頓算法,并且證明了這個算法是適定的.在適當(dāng)?shù)臈l件下,算法具有全局收斂性和局部超線性收斂性.使用Matla

5、b7.0編程做了若干數(shù)值試驗.數(shù)值效果表明這種非單調(diào)線搜索技術(shù)比單調(diào)線搜索技術(shù)更有效.
　　 最后,對于標(biāo)準(zhǔn)的線性互補(bǔ)問題(LCP),基于Huang-Qi-Sun[Math.Program.,99:423-441,2004]給出的光滑牛頓算法,提出了這個算法的修改算法.這個新的算法不僅與Huang-Qi-Sun[Math.Program.,99:423-441,2004]算法具有相同的全局收斂性,而且擁有下面更好的局部快速收斂性