互補問題與半定規(guī)劃算法研究.pdf

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

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

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

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

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