徐軍委， 趙文玲， 王艷艷

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

?

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

徐軍委， 趙文玲， 王艷艷

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

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

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

鞍點(diǎ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)化為問題

由上式可得

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

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

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

1概念和符號

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

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

x到S的距離定義為

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

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時，有xk∈S.

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

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

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

(1)

(2)

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

即得

(3)

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

(4)

(5)

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

(6)

即得(4)式成立.

即(3)式成立.

且有

取tk→0,zk→z,即得

因此，對?b∈B,

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

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

(7)

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

由引理4.6[4]，對充分大的k有

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

得

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

4結(jié)束語

對于求解鞍點(diǎn)問題的算法，評價其優(yōu)劣的最重要指標(biāo)就是其迭代所產(chǎn)生的可行解序列是否收斂或有限收斂(有限終止). 本文對鞍點(diǎn)問題的解集給出了弱強(qiáng)的概念，當(dāng)其解集滿足弱強(qiáng)時，給出了對任意算法所產(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)問題迭代算法的進(jìn)一步研究[J]. 阜陽師范學(xué)院學(xué)報(自然科學(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

中圖分類號：O224

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

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

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

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

收稿日期：2015-09-10