王 煒，陳 渺，李尚華

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院，遼寧 大連 116029)

0 引言

1 目標(biāo)函數(shù)的近似

設(shè)F(y)=λmax(A(y))+g(y)，Y∈Rn，假設(shè)

ri(domλmax(A(y)))∩ri(domg(y))≠φ，

β*Q(A(xi))ZQ(A(xi))T+si∈?λmax(A(xi))+?g(xi)=?[λmaxA(xi)+g(xi)]，

于是有

令線性化誤差

ei=F(xk)-F(xi)-〈β*Q(A(xi))ZQ(A(xi))T+si,xk-xi〉，

得F(y)的近似的具體形式為

2 帶有罰項(xiàng)的束方法算法

求解問(wèn)題的(P)帶有罰項(xiàng)的束方法的算法

Step 0 令ε≥0，m∈(0，1)為給定參數(shù)，選定x1，運(yùn)用黑盒子得到F(x1)和β*Q(A(x1))ZQ(A(x1))T+s1∈?[λmaxA(x1)+g(x1)]，構(gòu)造模型F1，令k=1，δ1=∞．

Step 1 若δk≤ε，則停止算法．

Step 2 求解

Step 3 將點(diǎn)x=yk+1代入黑盒子中，考察是否有

F(xk)-F(yk+1)≥mδk+1

(2.1)

若(2.1)成立，取xk+1=yk+1，并稱為下降步；若(2.1)不成立，取xk+1=xk，并稱為零步．

Step 4 添加yk+1至模型中，構(gòu)造Fk+1，令k=k+1，回Step 1.

在Step 2 中，候選點(diǎn)yk+1可通過(guò)求(P1)的對(duì)偶問(wèn)題得到，具體由以下定理所保證.

定理2.1若yk+1為(P1)的唯一解，則

的解，此外，還可以得到以下結(jié)論：

證明引入輔助變量r，(P1)等價(jià)于

npk(P2)的Lagrangian為

〈β*Q(A(xi))ZQ(A(xi))T+si,y-xk〉-r)，

為(P1)的解，所以(1)成立．

通過(guò)(P1)與(P1)的對(duì)偶問(wèn)題的最優(yōu)解均為yk+1，易知(2)成立．

在迭代過(guò)程中，束中的元素會(huì)不斷增加，此時(shí)，需要壓縮機(jī)制來(lái)控制束的大?。?dāng)束中當(dāng)前元素量npk超過(guò)束中可允許的最大元素量npmax時(shí)，Step 4變?yōu)槿缦滦问?

若nact≤npmax-1，則刪除不積極的指標(biāo)，nleft=nact，定義npk+1=nleft+1，然后，把(β*Q(A(xnpk+1))ZQ(A(xnpk+1))T+snpk+1，enpk+1)放入束中，其中

若nact>npmax-1，則刪除不積極的指標(biāo)，且去掉兩個(gè)或多個(gè)元素(β*Q(A(xi))ZQ(A(xi))T+si,ei)，將去掉的兩個(gè)或多個(gè)元素合成(即合成束，見(jiàn)注1)．此時(shí)，nleft=npmax-2或nleft

構(gòu)造Fk+1，令k=k+1，返回Step 1.

注1：當(dāng)束中當(dāng)前元素量npk超過(guò)束中可允許的最大元素量npmax時(shí)，將不積極的元素刪除，若余下的元素仍太多，則將必不可少的元素合成．即利用由定理2.1得到的

構(gòu)造集合線性化函數(shù)Fα(y)：

Fα(y)有如下性質(zhì)：

注2：當(dāng)束中元素量超過(guò)束中可允許的最大值npmax時(shí)，假設(shè)決定去掉x1,x2，…，xt，則新的模型為

3 收斂分析

假設(shè)停止準(zhǔn)則為δk+1≤ε，我們分ε>0為ε=0和兩方面進(jìn)行分析．

證明由于算法無(wú)限循環(huán)及ε≥0知δk>0，而k∈Ks，則xk+1=yk+1，則F(xk)-F(xk+1)≥0，令k′為Ks中k的下一個(gè)指標(biāo)k且k′與之間存在零步，則j=2,3,…，k′-k時(shí)不用移動(dòng)穩(wěn)定中心．即xk+1=xk+j且F(xk+1)-F(Xk′+1)=mδk′+1，則對(duì)?k′∈Ks，?ε>0，有

當(dāng)k″→∞時(shí)，結(jié)論成立． 證畢．

情況1.Ks中有無(wú)限元素

以下定理保證了以上兩種情況下算法的收斂性(證明過(guò)程類似于[4])．

定理3.2假設(shè)算法產(chǎn)生無(wú)限下降步xk，則下列兩種情況必有一種成立．

(i)原問(wèn)題無(wú)最優(yōu)解且{F(xk)}遞減趨近于-∞；

(ii)原問(wèn)題有最優(yōu)解，此時(shí)，若k∈Ks，k→-∞，有{δK}→0且{εk}→0，若0<ηk+1<ηk，則{xk}有界且收斂于原問(wèn)題的最小值點(diǎn)．

[1] Christoph Helmberg,Francois Oustry.Bundle methods to minimize the maximum eigenvalue function[J].Handbook of Semidefinite Progamming,2000,27:307～337.

[2]Claudia Sagastizabal,Mikhail Solodov.An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or filter[J].SIAM J.Optimization,2005,16(1):146～169.

[3]Oustry F.,Lemarchal C.Nonsmooth algorithms to solve semidefinite programs[J].Society for Industrial and Applied Mathematics Philadelphia,2000,57～77.

[4]J.Frederic Bonnans,J.Charles Gilbert,Claude Lemarechal,et al.Sagatizabal.Bundle methods.The quest of descent.Numerical Optimization,2003,117～136.

[5]周茂袁，王秀麗，李雪艷.特征函數(shù)的一種新解釋及其應(yīng)用[J].吉林師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2008，29(2)：45～48.

[6]初 麗.線性互補(bǔ)問(wèn)題的序列凸近似方法[J].吉林師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2013，34(4)：117～120.

[7]Claudia Sagastizábal,Mikhail Solodov.An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or filter[J].SIAM J.Optimization,2005,16(1):146～169.

[8]Ladislav Lukgan,Jan Vicek.A bundle-Newton method for nonsmooth unconstrained minimization[J].The Mathematical Programming Society,1998,373～391.

[9]Antonio Frangioni.Generalized bundle methods[J].SIAM J.OPTIM,2001,13(1):117～156.

[10]L.Luk?an,J.Vicek.Globally Convergent Variable Metric Method for Convex Nonsmooth Unconstrained Minimization.Journal of optimization theory and applications,1999,102(3):593～613.

[11]K.Kiwiel.A bundle Bregman proximal method for convex nondifferentiable optimization,Math.Program.,1999,85,241～258.