唐春明,律金曼

(廣西大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,廣西南寧　530004)

?

基于非精確數(shù)據(jù)的非光滑優(yōu)化強(qiáng)次可行方向法*

唐春明,律金曼

(廣西大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,廣西南寧530004)

(College of Mathematics and Information Science,Guangxi University,Nanning,Guangxi,530004,China)

摘要:本研究針對(duì)一類(lèi)目標(biāo)函數(shù)非光滑優(yōu)化問(wèn)題,提出一個(gè)基于非精確數(shù)據(jù)的強(qiáng)次可行方向法.通過(guò)構(gòu)造新的尋找搜索方向子問(wèn)題和新型線(xiàn)搜索,該算法能夠保證迭代點(diǎn)的強(qiáng)次可行性,且具備全局收斂性.

關(guān)鍵詞：非光滑優(yōu)化強(qiáng)次可行方向法非精確數(shù)據(jù)

0　引言

考慮如下非線(xiàn)性不等式約束優(yōu)化問(wèn)題

(0.1)

s.t.ci(x)≤0,i∈I?{1,…,m},

其中f:Rn→R是凸函數(shù)但不一定光滑,ci(i∈I):Rn→R是連續(xù)可微的凸函數(shù).

在一些實(shí)際問(wèn)題中,有時(shí)很難精確計(jì)算f的函數(shù)值.例如,f是如下max-型函數(shù)

f(x)=max{Fu(x):u∈U},

(0.2)

其中對(duì)任意給定的u∈U,Fu:Rn→R是凸函數(shù),U是一個(gè)無(wú)限集,此時(shí)無(wú)法計(jì)算f的精確值.然而,對(duì)于任意正數(shù)ε,可以在有限的時(shí)間內(nèi)找出(0.2)的一個(gè)ε-解,即找出一個(gè)uε∈U滿(mǎn)足Fuε(x)≥f(x)-ε,從而得到f(x)的近似值.因此,研究基于非精確數(shù)據(jù)的優(yōu)化方法具有重要的意義[1-3].

文獻(xiàn)[4]基于精確數(shù)據(jù),提出一個(gè)求解問(wèn)題(0.1)的強(qiáng)次可行方向法,其優(yōu)點(diǎn)在于能接受不可行的初始點(diǎn),且一旦產(chǎn)生一個(gè)可行迭代點(diǎn),即自動(dòng)變?yōu)榭尚邢陆邓惴?此外,算法可保證迭代點(diǎn)的強(qiáng)次可行性,同時(shí)能防止目標(biāo)函數(shù)過(guò)度增大.文獻(xiàn)[2]中提出一種非精確數(shù)據(jù)的思想，即假設(shè)對(duì)于給定的點(diǎn)x和誤差限ε≥0,能夠計(jì)算得到近似的函數(shù)值fε(x)≈f(x)和一個(gè)近似的次梯度gε≈g∈?f(x)滿(mǎn)足:

fε(x)∈[f(x)-ε,f(x)+ε],

gε∈?εf(x)={g:f(y)≥f(x)+g,y-x-ε,?y∈Rn}.

本研究旨在對(duì)文獻(xiàn)[4]的方法進(jìn)行改進(jìn),結(jié)合文獻(xiàn)[2]的思想,提出一個(gè)基于非精確數(shù)據(jù)的非光滑優(yōu)化強(qiáng)次可行方向法.

1　算法

fj(x)=fεj(yj)+gj,x-yj-2εj.

(1.1)

由gj∈?εjf(yj) 和f(yj)≥ fεj(yj)-εj可知

fj(x)≤ f(x),?x∈Rn.

(1.2)

進(jìn)而可定義f的近似割平面模型

記問(wèn)題(0.1)的可行集F={x∈Rn:ci(x)≤0,i∈I}.定義指標(biāo)集I-(x)={i∈I:ci(x)≤0},I+(x)={i∈I:ci(x)>0},約束違反函數(shù)φ(x)=max{0,ci(x),i∈I}.引入改進(jìn)函數(shù)[4]:

H(y;x)=max{f(y)-f(x)-δ(x);ci(y),i∈I-(x);ci(y)-φ(x),i∈I+(x)},

下面給出改進(jìn)函數(shù)的性質(zhì).

基于引理1.1,并結(jié)合鄰近點(diǎn)方法思想[5],選取新的試探點(diǎn)如下:

(1.3)

ci(xk)+ci(xk),d,

ci(xk)+ci(xk),d,

(1.4)

(1.5)

j∈Jk,

(1.6)

更新聚集次梯度如下:

(1.7)

以下引理給出子問(wèn)題(1.4)的解的性質(zhì).

引理1.2設(shè)(dk,zk)是問(wèn)題(1.4)的最優(yōu)解,則

(1.8)

其中,

(1.9)

(ii)gj∈?f(xk),,

sk∈ ?f(xk),,

-ρkdk∈?H(xk;xk),.

(1.10)

(iii)如果zk=0,則dk=0,且xk是問(wèn)題(0.1)的一個(gè)最優(yōu)解.

證明(i)由KKT條件(1.6)中的互補(bǔ)關(guān)系和(1.7)式有

故(1.8)式成立.

(ii)由(1.2)式知,

xkgj,x-xk,

(1.11)

從而(1.10)式的第一個(gè)式子成立.類(lèi)似地,根據(jù)(1.5)式知

f(x)≥f(xk)+sk-1,x-xk.

(1.12)

f(x)≥f(xk)+sk,x-xk,

(1.13)

故(1.10)式的第二個(gè)式子成立.

根據(jù)ci的凸性,有

ci(x)≥ ci(xk)+ci(xk),x-xk.

因此,

此式結(jié)合(1.6)式,(1.13)式,θk≤1及H(xk;xk)=0可得

由此證明(1.10)式的第三個(gè)式子.

算法1.1

步驟3(終止準(zhǔn)則)如果zk≥-εTOL,算法終止;否則,轉(zhuǎn)步驟4.

步驟4(線(xiàn)搜索)計(jì)算試探步長(zhǎng)tk,它是序列{1,β,β2,…}中第一個(gè)滿(mǎn)足下列不等式組的t值:

(1.14)

(1.15)

如果

(1.16)

步驟6(鄰近參數(shù)選擇)如果xk+1≠xk,取ρk+1∈[ρmin,ρk]; 否則,ρk+1=ρk.

步驟7令k∶=k+1,返回步驟1.

引理1.3[4]算法1.1是適定的,即線(xiàn)搜索(1.14)和(1.15)能在有限次計(jì)算后終止.

引理1.4算法1.1必定出現(xiàn)以下兩種情形之一.

(i)存在一個(gè)指標(biāo)k0使得φk0=0,從而φk≡0,δk≡0和f(xk+1)≤f(xk),對(duì)于所有的k≥ k0成立;

證明(i)由步驟4可知,φk≡0及δk≡0對(duì)k≥k0成立.現(xiàn)證明f(xk+1)≤f(xk).根據(jù)步驟4,如果是一個(gè)有效步,由zk<0可得

若是一個(gè)無(wú)效步,則有f(xk+1)=f(xk).

(ii)根據(jù)線(xiàn)搜索(1.14)和(1.15)易證.

2　算法的收斂性

引理2.1鄰近參數(shù)序列{ρk}單調(diào)不增,且有正的下界.

證明根據(jù)步驟6,顯然{ρk} 單調(diào)不增,且ρk≥ρmin>0.

分兩種情形證明.首先考慮有無(wú)限個(gè)有效步的情形.類(lèi)似文獻(xiàn)[7],有如下引理.

s.t.λj≥0,j∈Jk,λs≥0,μi≥0,i∈I,

(2.1)

證明由于問(wèn)題(2.1)是問(wèn)題(1.4)的對(duì)偶問(wèn)題,故問(wèn)題(2.1)的最優(yōu)解即為問(wèn)題(1.4)的KKT乘子.因此,由(1.6)式,(1.9)式及ωk的定義可得結(jié)論成立.

基于引理2.5,得到以下一個(gè)重要的結(jié)論.

εk-1=εk,則

(2.2)

(ii)ωk≤ωk-1-(ρk-1)2(1-

mR)2(ωk-1)2/8(Ck)2,

(2.3)

(2.4)

因此,由(1.1)式和(2.4)式有

-(fεk(xk)-fεk(yk)-gk,xk-yk+3εk)-

δk-1=-(fεk(xk-1)-fεk(yk)-gk,xk-1-yk+

(2.5)

因此根據(jù)(2.4)式可得

(2.6)

(ii)對(duì)任意的υ∈[0,1],定義問(wèn)題(2.1)的可行解

λk(υ)=υ,λj(υ)=0,j∈Jk{k},

由(1.16)式和xk-1=xk可得

(2.7)

因此

υgk+(1-υ)(-ρk-1dk-1).

此外,根據(jù)(2.7)式有

s.t.υ∈[0,1].

定理2.1(i)如果算法1.1有限步終止于第k次迭代,則xk是問(wèn)題(0.1)的一個(gè)最優(yōu)解;(ii)如果算法1.1在第k次迭代時(shí)無(wú)限次在步驟1與步驟2之間循環(huán),則xk是問(wèn)題(0.1)的一個(gè)最優(yōu)解;(iii)如果算法1.1產(chǎn)生一個(gè)無(wú)限迭代序列{xk},則其任一聚點(diǎn)x*都是問(wèn)題(0.1)的一個(gè)最優(yōu)解.

證明(i)如果算法1.1有限次終止于點(diǎn)xk,則zk=0.根據(jù)引理1.2知xk是問(wèn)題(0.1)的一個(gè)最優(yōu)解.

(iii)現(xiàn)在假設(shè)算法1.1產(chǎn)生一個(gè)無(wú)限迭代序列{xk},且x*是其任一聚點(diǎn).則分兩種情況證明x*是問(wèn)題(0.1)的一個(gè)最優(yōu)解.

情形1有無(wú)限多個(gè)有效步.此時(shí),必然存在無(wú)限指標(biāo)集L?{1,2,…}使得xk(l)→ x*,l→∞,l∈L.因此,根據(jù)引理2.3知x*是問(wèn)題(0.1)的一個(gè)最優(yōu)解.

結(jié)合(2.3)式,有

ωk≤ωk-1-ρ2(1-mR)2(ωk-1)2/8C2,

由此可得ωk→0,k→∞,從而zk→0,k→∞.因此,由引理2.2可知x*是問(wèn)題(0.1)的一個(gè)最優(yōu)解.

參考文獻(xiàn)：

[1]KIWIEL K C.An alternating linearization bundle method for convex optimization and nonlinear multicommodity flow problems[J].Mathematical Programming,2011,130(1):59-84.

[2]KIWIEL K C.An algorithm for nonsmooth convex minimization with errors[J].Mathematics of Computation,1985,171(45):173-180.

[3]KIWIEL K C.A method of centers with approximate subgradient linearizations for nonsmooth convex optimization[J].SIAM Journal on Optimization,2007,18(4):1467-1489.

[4]TANG C M,JIAN J B.Strongly sub-feasible direction method for constrained optimization problems with nonsmooth objective functions[J].European Journal of Operational Research,2012,218(1):28-37.

[5]KIWIEL K C.Proximity control in bundle methods for convex nondifferentiable minimization[J].Mathematical Programming,1990,46(1/2/3):105-122.

[6]KIWIEL K C.Methods of Descent for Nondifferentiable Optimization[M].Berlin Heidelberg:Spring-Verlag,1985.

[7]唐春明,簡(jiǎn)金寶.非光滑優(yōu)化的強(qiáng)次可行方向鄰近點(diǎn)束求解方法[J].廣西科學(xué),2014,21(3):283-286. TANG C M,JIAN J B.A proximal bundle method of strongly sub-feasible directions for nonsmooth optimization[J].Guangxi Sciences,2014,21(3):283-286.

(責(zé)任編輯：米慧芝)

Strongly Sub-feasible Direction Method with Inexact Data for Nonsmooth Optimization

TANG Chunming,LV Jinman

Key words：nonsmooth optimization,strongly sub-feasible direction method,inexact data

Abstract：In this paper,a strongly sub-feasible direction method with inexact data is proposed for solving a class of optimization problems with nonsmooth objectives.By constructing a new search direction finding subproblem and a new line search,the strongly sub-feasibility of the iteration points is guaranteed,and the global convergence of the algorithm is proved.

收稿日期：2016-08-05

作者簡(jiǎn)介：唐春明(1979-),男,博士,教授,主要從事最優(yōu)化理論、方法及其應(yīng)用研究,E-mail:cmtang@gxu.edu.cn。

中圖分類(lèi)號(hào):C934

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1005-9164(2016)05-0404-05

修回日期：2016-09-20

*國(guó)家自然科學(xué)基金項(xiàng)目(11301095,11271086)和廣西自然科學(xué)基金項(xiàng)目(2013GXNSFAA019013,2014GXNSFFA118001)資助。

廣西科學(xué)Guangxi Sciences 2016,23(5):404～408

網(wǎng)絡(luò)優(yōu)先數(shù)字出版時(shí)間：2016-11-21【DOI】10.13656/j.cnki.gxkx.20161121.012

網(wǎng)絡(luò)優(yōu)先數(shù)字出版地址：http://www.cnki.net/kcms/detail/45.1206.G3.20161121.1546.024.html