互補問題的乘子法.pdf

1、該文研究互補與混合互補問題的新算法.建立了互補和混合互補問題的一類新La-grange乘子法理論框架,該方法通過引入與互補和混合互補問題等價的非光滑方程組的向量Lagrange函數(shù),構(gòu)造了一類新的含乘子的處處光滑價值函數(shù),通過簡便易行的乘子修正新手段,克服了問題固有的非光滑性困難,為此類問題的數(shù)值求解提供了新途徑.基此提出了若干求解互補和混合互補問題的新算法.在較目前常用條件更弱的假定下,證明了算法的全局收斂性和局部超線性或二次收斂率.

2、對MCPLIB庫及其它大量算例且較其它文獻(xiàn)更多初始點的廣泛數(shù)值實驗,表明該方法具有與理論分析一致的高效可靠、令人滿意的實算性能,特別對一些典型算例具有優(yōu)于以往算法的突出數(shù)值表現(xiàn).1.對線性互補問題,首次得到一種乘子固定時具有分片二次凸性質(zhì)的光滑價值函數(shù),它在光滑條件下完好保持了原問題的線性性質(zhì),基此提出了Lagrange乘子法.(i)在P<,0>-矩陣且解集非空有界的弱條件下得到算法的全局收斂性;(ii)在P-矩陣且無須嚴(yán)格互補條件下得

3、到有限步收斂性,且方法避免了采用混雜開關(guān)技術(shù)或在Newton步之外增加修正步等額外耗費計算量的附加步驟,每次迭代只需求解一次Newton方程.2.對非線性互補問題,利用所構(gòu)造價值函數(shù)具有的特殊非線性最小二乘結(jié)構(gòu),成功實現(xiàn)了具有一般意義的構(gòu)造Newton方程時僅利用價值函數(shù)的一階導(dǎo)數(shù)且無須計算相應(yīng)殘量函數(shù)Jacobi矩陣乘積的Newton法.文中給出了形式不同的兩種Newton方程,同時提出了兩種計算量少、易于實現(xiàn)的乘子修正策略,并將其納

4、入了一個統(tǒng)一模式.在P<,0>-函數(shù)且解集非空有界的條件下得到算法的全局收斂性,在R-正則條件下得到超線性或二次收斂率,其中全局收斂性條件弱于目前常用條件:單調(diào)函數(shù)且有嚴(yán)格可行點或P<,0>+R<,0>-函數(shù).3.對于混合互補問題,以中間值函數(shù)為橋梁,給出了混合互補問題的Lagrange乘子法.在P<,0>-函數(shù)和可行域有界的條件下證明了相應(yīng)算法的全局收斂性,在R-正則條件下得到了相應(yīng)算法的超線性或二次收斂率.4.對于互補和混合互補問題

5、,通過消去乘子的技巧性工作,分別構(gòu)造了新的不含任何參數(shù)的一類光滑價值函數(shù),它們結(jié)構(gòu)簡單,在P<,0>-函數(shù)情形便可保證其穩(wěn)定點是互補問題之解,不僅具備類似著名Fischer-Burmeister函數(shù)的良好微分性質(zhì),且強制性方面更優(yōu),同時對線性問題也保持了其線性性質(zhì).特別對混合互補問題,據(jù)作者所知,該價值函數(shù)是迄今形式最為簡單的光滑價值函數(shù).基此構(gòu)造的互補和混合互補問題的算法,均具備在前述條件或比其更弱條件下的全局收斂性、局部超線性或二次