鞍點(diǎn)問(wèn)題可行解序列的有限終止性

徐軍委， 趙文玲， 王艷艷

(山東理工大學(xué) 理學(xué)院， 山東 淄博 255049)

?

鞍點(diǎn)問(wèn)題可行解序列的有限終止性

徐軍委， 趙文玲， 王艷艷

(山東理工大學(xué) 理學(xué)院， 山東 淄博 255049)

摘要：鞍點(diǎn)問(wèn)題解集的弱強(qiáng)性對(duì)于研究其算法的有限終止性有重要的意義.對(duì)鞍點(diǎn)問(wèn)題的解集引入弱強(qiáng)的概念，給出解集是弱強(qiáng)的充分必要條件；并在解集是弱強(qiáng)的條件下，得到了任意算法所產(chǎn)生的可行解序列有限終止的充分必要條件.

關(guān)鍵詞：鞍點(diǎn)問(wèn)題； 解集； 弱強(qiáng)性； 有限終止

鞍點(diǎn)問(wèn)題即是

?(y1,y2)∈S1×S2，

其中，φ:Rn→R，S1?Rn1,S2?Rn2，n1+n2=n.S,S1,S2均為非空閉凸集.

令Φ(x,y)=φ(y1,x2)-φ(x1,y2)，

將其轉(zhuǎn)化為問(wèn)題

由上式可得

鞍點(diǎn)問(wèn)題(SPP)的解集為

穩(wěn)定點(diǎn)集為

鞍點(diǎn)問(wèn)題是在應(yīng)用數(shù)學(xué)領(lǐng)域經(jīng)常遇到的一類(lèi)問(wèn)題，分析其算法的有限終止性對(duì)解決實(shí)際問(wèn)題具有重要的意義,許多文獻(xiàn)對(duì)其算法的收斂性進(jìn)行了研究[1-3].解集的弱強(qiáng)極小性受到了廣泛的關(guān)注與研究，它在算法的收斂性與可行解序列的有限終止性中起了很重要的作用. 為了解決可能出現(xiàn)的非唯一解集的情況，Burke和Ferris在數(shù)學(xué)規(guī)劃問(wèn)題中提出了弱強(qiáng)極小的概念，繼而給出了數(shù)學(xué)規(guī)劃迭代算法有限識(shí)別的條件[4].PatriceMarcotte和DaoLiZhu將這一概念推廣到變分不等式中，并且在這一假設(shè)條件下，分析了求解變分不等式的下降算法有限收斂的條件[5].近年來(lái)，Xiu和Zhang對(duì)此進(jìn)行了改進(jìn)，在更弱的條件下，同時(shí)解集是弱強(qiáng)的假設(shè)下，給出了變分不等式逼近點(diǎn)算法的有限終止[6]. 有些文獻(xiàn)將解集的這種特性推廣到變分不等式和一般的光滑非凸規(guī)劃問(wèn)題中[7-9].本文在鞍點(diǎn)問(wèn)題中給出解集弱強(qiáng)的概念，在光滑的情況下，得到解集是弱強(qiáng)集的等價(jià)定義；在解集是弱強(qiáng)的條件下，研究了可行解序列有限終止的充分必要條件.

1概念和符號(hào)

Rn表示n維歐式空間，對(duì)任意的x,y∈Rn，其內(nèi)積定義為

設(shè)x∈Rn,S?Rn,x在S上的投影為

x到S的距離定義為

當(dāng)S是閉集時(shí)，則有

dist(x,S)=‖PS(x)-x‖.

S的極錐定義為

S在x處的法錐表示為

S在x處的切錐表示為

TS(x)=NS(x)°.

設(shè)函數(shù)ψ(·)在點(diǎn)x∈S的次微分?ψ(x)≠?,則ψ(·)在點(diǎn)x的投影次微分定義為

PTS(x)(-?ψ(x))=

我們稱序列{xk}?Rn有限終止于S，如果存在k0,當(dāng)k>k0時(shí)，有xk∈S.

2鞍點(diǎn)問(wèn)題解集的弱強(qiáng)性

在本節(jié)中，對(duì)鞍點(diǎn)問(wèn)題(SPP)的解集給出了弱強(qiáng)的概念，這個(gè)概念是凸規(guī)劃中弱強(qiáng)極小概念的推廣，并且在光滑的情況下給出了解集是弱強(qiáng)的等價(jià)定義.

定義1在鞍點(diǎn)問(wèn)題(SPP)中，假設(shè)對(duì)?x∈S,?yΦ(x,x)≠?.如果存在常數(shù)α>0,使得

(1)

(2)

接下來(lái)，給出在鞍點(diǎn)問(wèn)題中Φ(x,·)光滑的情況下，解集滿足弱強(qiáng)性的充分必要條件.

即得

(3)

證明首先證明包含關(guān)系

(4)

(5)

首先如果(4)式成立，則對(duì)?b∈B,有

(6)

即得(4)式成立.

即(3)式成立.

且有

取tk→0,zk→z,即得

因此，對(duì)?b∈B,

3鞍點(diǎn)問(wèn)題可行解序列的有限終止性

對(duì)鞍點(diǎn)問(wèn)題，在其解集滿足弱強(qiáng)的條件下，給出了由任意算法所產(chǎn)生的可行解序列有限終止的充分必要條件.

(7)

PNS(xk)(-yΦ(xk,xk)).

由引理4.6[4]，對(duì)充分大的k有

xk+PNS(xk)(-yΦ(xk,xk))∈

得

xk=PS(xk+PNS(xk)(-yΦ(xk,xk)))

4結(jié)束語(yǔ)

對(duì)于求解鞍點(diǎn)問(wèn)題的算法，評(píng)價(jià)其優(yōu)劣的最重要指標(biāo)就是其迭代所產(chǎn)生的可行解序列是否收斂或有限收斂(有限終止). 本文對(duì)鞍點(diǎn)問(wèn)題的解集給出了弱強(qiáng)的概念，當(dāng)其解集滿足弱強(qiáng)時(shí)，給出了對(duì)任意算法所產(chǎn)生的可行解點(diǎn)列具有有限終止性的充分必要條件. 因此，解集的弱強(qiáng)性在建立算法有限終止性方面起著關(guān)鍵作用.

參考文獻(xiàn)：

[1]HeB,YuanX.Convergenceanalysisofprimal-dualalgorithmsforasaddle-pointproblem:fromcontractionperspective.[J].siamjournalonimagingsciences, 2012, 5(1):119-149.

[2]王濤, 盛興平. 鞍點(diǎn)問(wèn)題迭代算法的進(jìn)一步研究[J]. 阜陽(yáng)師范學(xué)院學(xué)報(bào)(自然科學(xué)版), 2012,6(1):9-13.

[3]Jun-FengLU.ConvergenceanalysisofthecorrectedUzawaalgorithmforsymmetricsaddlepointproblems[J].AppliedMathematicsAJournalofChineseUniversities, 2014,29(1):29-35.

[4]BurkeJV,FerrisMC.Weaksharpminimainmathematicalprogramming[J].SiamJournalonControl&Optimization, 1993, 31(5):1 340-1 359.

[5]MarcotteP,ZhuD.Weaksharpsolutionsofvariationalinequalities[J].SiamJournalonOptimization, 1998, 9(1):179-189.

[6]XiuN,ZhangJ.Onfiniteconvergenceofproximalpointalgorithmsforvariationalinequalities[J].JournalofMathematicalAnalysis&Applications, 2005, 312(1): 148-158.

[7]WangC,LiuQ,YangX.Convergencepropertiesofnonmonotonespectralprojectedgradientmethods[J].JournalofComputational&AppliedMathematics, 2005, 182(1): 51-66.

[8]WangC,ZhaoW,ZhouJ,etal.Globalconvergenceandfiniteterminationofaclassofsmoothpenaltyfunctionalgorithms[J].OptimizationMethods&Software, 2013, 28(1): 1-25.

[9]ZhouJ,WangC.Newcharacterizationsofweaksharpminima[J].OptimizationLetters, 2012, 6(8):1-13.

[10]BurkeJV,FerrisMC.Characterizationofsolutionsetsofconvexprograms[J].OperationsResearchLetters, 1991, 10(1):57-60.

(編輯：劉寶江)

Finite termination of feasible solution sequence to saddle point problems

XU Jun-wei, ZHAO Wen-ling, WANG Yan-yan

(School of Science, Shandong University of Technology, Zibo 255049, China)

Abstract:Weak sharp solutions of saddle point problems have an important influence on the finite termination of the algorithm. We introduce the concept of weak sharpness to saddle point problem, and give necessary and sufficient conditions of the property. Under condition of solution set is weakly sharp, we obtain necessary and sufficient conditions of finite termination of a feasible solution sequence to saddle point problems.

Key words:saddle point problem; solution set; weak sharp; finite termination

中圖分類(lèi)號(hào)：O224

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-6197(2016)03-0025-04

作者簡(jiǎn)介：徐軍委，男，xjw_100@126.com； 通信作者： 趙文玲，女，zwlsdj@163.com.

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(11271233)； 山東省自然科學(xué)基金項(xiàng)目(ZR2012AM016)

收稿日期：2015-09-10