基于非精确数据的非光滑优化强次可行方向法*

唐春明,律金曼

(广西大学数学与信息科学学院,广西南宁　530004)



基于非精确数据的非光滑优化强次可行方向法*

唐春明,律金曼

(广西大学数学与信息科学学院,广西南宁530004)

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

摘要:本研究针对一类目标函数非光滑优化问题,提出一个基于非精确数据的强次可行方向法.通过构造新的寻找搜索方向子问题和新型线搜索,该算法能够保证迭代点的强次可行性,且具备全局收敛性.

关键词：非光滑优化强次可行方向法非精确数据

0　引言

考虑如下非线性不等式约束优化问题

(0.1)

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

其中f:Rn→R是凸函数但不一定光滑,ci(i∈I):Rn→R是连续可微的凸函数.

在一些实际问题中,有时很难精确计算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)的近似值.因此,研究基于非精确数据的优化方法具有重要的意义[1-3].

文献[4]基于精确数据,提出一个求解问题(0.1)的强次可行方向法,其优点在于能接受不可行的初始点,且一旦产生一个可行迭代点,即自动变为可行下降算法.此外,算法可保证迭代点的强次可行性,同时能防止目标函数过度增大.文献[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]的思想,提出一个基于非精确数据的非光滑优化强次可行方向法.

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)的最优解,则

(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)的一个最优解.

证明(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)的最优解即为问题(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)的一个最优解;(ii)如果算法1.1在第k次迭代时无限次在步骤1与步骤2之间循环,则xk是问题(0.1)的一个最优解;(iii)如果算法1.1产生一个无限迭代序列{xk},则其任一聚点x*都是问题(0.1)的一个最优解.

证明(i)如果算法1.1有限次终止于点xk,则zk=0.根据引理1.2知xk是问题(0.1)的一个最优解.

(iii)现在假设算法1.1产生一个无限迭代序列{xk},且x*是其任一聚点.则分两种情况证明x*是问题(0.1)的一个最优解.

情形1有无限多个有效步.此时,必然存在无限指标集L⊆{1,2,…}使得xk(l)→ x*,l→∞,l∈L.因此,根据引理2.3知x*是问题(0.1)的一个最优解.

结合(2.3)式,有

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

由此可得ωk→0,k→∞,从而zk→0,k→∞.因此,由引理2.2可知x*是问题(0.1)的一个最优解.

参考文献：

[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]唐春明,简金宝.非光滑优化的强次可行方向邻近点束求解方法[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-),男,博士,教授,主要从事最优化理论、方法及其应用研究,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

网络优先数字出版时间：2016-11-21【DOI】10.13656/j.cnki.gxkx.20161121.012

网络优先数字出版地址：http://www.cnki.net/kcms/detail/45.1206.G3.20161121.1546.024.html