互補(bǔ)問(wèn)題與半定規(guī)劃算法研究.pdf

1、本文對(duì)互補(bǔ)問(wèn)題與半定規(guī)劃問(wèn)題的數(shù)值解法進(jìn)行了研究。主要研究?jī)?nèi)容及結(jié)果如下：
　　 ⑴提出無(wú)約束最優(yōu)化共軛梯度法參數(shù)βκ修正的兩種新形式.與經(jīng)典共軛梯度法的區(qū)別是新方法中體現(xiàn)了函數(shù)值下降量信息，提出這兩種方法的改進(jìn)形式，證明了這四種方法的全局收斂性.數(shù)值實(shí)驗(yàn)表明了算法的有效性。
　　 ⑵提出求解大規(guī)模非線性互補(bǔ)問(wèn)題(NCP(F))的共軛梯度法。(i)利用Fischer-Burmeister NCP-函數(shù)，將NCP(F)轉(zhuǎn)化

2、為非線性方程組，基此提出PRP-型共軛梯度法。算法的突出特點(diǎn)是在不需要額外假設(shè)及線搜索的輔助下滿足充分下降條件，在F是連續(xù)可微P0+R0函數(shù)且F'(x)在水平集上全局Lipschitz連續(xù)條件下，算法全局收斂；(ii)利用光滑F(xiàn)ischer-Burmeister函數(shù)，將NCP(F)轉(zhuǎn)化為光滑非線性方程組，基此對(duì)大規(guī)模非線性互補(bǔ)問(wèn)題提出光滑PRP-型共軛梯度法。算法執(zhí)行一步需進(jìn)行兩個(gè)Armijo線性搜索既確保光滑參數(shù)μ的非負(fù)性又極小化由光

3、滑F(xiàn)ischer-Burmeister函數(shù)所形成的光滑價(jià)值函數(shù)。在F為P0+R0連續(xù)可微函數(shù)時(shí)，算法全局收斂.數(shù)值實(shí)驗(yàn)表明了這兩種算法的數(shù)值有效性。
　　 ⑶提出半定規(guī)劃的半定互補(bǔ)解法.首先考慮一類特殊的半定規(guī)劃問(wèn)題(即在對(duì)偶問(wèn)題中加入約束條件y≥0)，將其最優(yōu)性條件等價(jià)轉(zhuǎn)化為半定互補(bǔ)問(wèn)題(SDCP)，藉此提出預(yù)估-校正光滑牛頓法，證明了牛頓方向的存在性、迭代點(diǎn)列的有界性及算法的全局收斂性。在解點(diǎn)處廣義導(dǎo)數(shù)可逆的假設(shè)下得到算法的

4、超線性收斂率。然后推廣這一思想，將標(biāo)準(zhǔn)半定規(guī)劃的最優(yōu)性條件轉(zhuǎn)化為廣義半定互補(bǔ)問(wèn)題(GSDCP)，提出預(yù)估-校正光滑牛頓法。該方法是非線性互補(bǔ)問(wèn)題(NCP(F))算法的推廣。同樣證明了牛頓方向的存在性、迭代點(diǎn)列的有界性及算法的全局收斂性。在解點(diǎn)處廣義導(dǎo)數(shù)可逆的假設(shè)下得到算法的二次收斂率。不需要任何對(duì)稱化技巧，此二方法自動(dòng)產(chǎn)生對(duì)稱搜索方向。
　　 ⑷提出半定規(guī)劃的非內(nèi)點(diǎn)連續(xù)化方法。該方法是求解半定互補(bǔ)問(wèn)題(SDCP)算法的推廣。證明

5、了牛頓方向的存在性.在中心路徑鄰域有界的假設(shè)下得到迭代點(diǎn)列的有界性，進(jìn)而證明了算法的全局收斂性.在解點(diǎn)處廣義導(dǎo)數(shù)可逆的假設(shè)下算法局部二次收斂.給出了數(shù)值實(shí)驗(yàn)結(jié)果。
　　 ⑸提出半定規(guī)劃的PRP+共軛梯度法.基于Fischer-Burmeister SDCP-函數(shù)，對(duì)SDP的最優(yōu)性條件提出一梯度具有全局Lipschitz連續(xù)性的價(jià)值函數(shù)，從而將半定規(guī)劃轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，進(jìn)而用PRP+共軛梯度法求解。為得到PRP+共軛梯度法的收