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

唐春明,律金曼

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

?

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

唐春明,律金曼

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

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

摘要:本研究針對一類目標函數非光滑優(yōu)化問題,提出一個基于非精確數據的強次可行方向法.通過構造新的尋找搜索方向子問題和新型線搜索,該算法能夠保證迭代點的強次可行性,且具備全局收斂性.

關鍵詞：非光滑優(yōu)化強次可行方向法非精確數據

0　引言

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

(0.1)

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

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

在一些實際問題中,有時很難精確計算f的函數值.例如,f是如下max-型函數

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

(0.2)

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

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

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

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

本研究旨在對文獻[4]的方法進行改進,結合文獻[2]的思想,提出一個基于非精確數據的非光滑優(yōu)化強次可行方向法.

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)

進而可定義f的近似割平面模型

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

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

下面給出改進函數的性質.

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

(1.3)

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

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

(1.4)

(1.5)

j∈Jk,

(1.6)

更新聚集次梯度如下:

(1.7)

以下引理給出子問題(1.4)的解的性質.

引理1.2設(dk,zk)是問題(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是問題(0.1)的一個最優(yōu)解.

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

故(1.8)式成立.

(ii)由(1.2)式知,

xkgj,x-xk,

(1.11)

從而(1.10)式的第一個式子成立.類似地,根據(1.5)式知

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

(1.12)

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

(1.13)

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

根據ci的凸性,有

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

因此,

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

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

算法1.1

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

步驟4(線搜索)計算試探步長tk,它是序列{1,β,β2,…}中第一個滿足下列不等式組的t值:

(1.14)

(1.15)

如果

(1.16)

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

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

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

引理1.4算法1.1必定出現以下兩種情形之一.

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

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

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

(ii)根據線搜索(1.14)和(1.15)易證.

2　算法的收斂性

引理2.1鄰近參數序列{ρk}單調不增,且有正的下界.

證明根據步驟6,顯然{ρk} 單調不增,且ρk≥ρmin>0.

分兩種情形證明.首先考慮有無限個有效步的情形.類似文獻[7],有如下引理.

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

(2.1)

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

基于引理2.5,得到以下一個重要的結論.

ε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)

因此根據(2.4)式可得

(2.6)

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

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

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

(2.7)

因此

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

此外,根據(2.7)式有

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

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

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

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

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

結合(2.3)式,有

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

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

參考文獻：

[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]唐春明,簡金寶.非光滑優(yōu)化的強次可行方向鄰近點束求解方法[J].廣西科學,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.

(責任編輯：米慧芝)

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

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

中圖分類號:C934

文獻標識碼：A

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

修回日期：2016-09-20

*國家自然科學基金項目(11301095,11271086)和廣西自然科學基金項目(2013GXNSFAA019013,2014GXNSFFA118001)資助。

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

網絡優(yōu)先數字出版時間：2016-11-21【DOI】10.13656/j.cnki.gxkx.20161121.012

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