互補(bǔ)問(wèn)題的乘子法.pdf

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

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

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

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

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