第28卷 第2期 上海第二工业大学学报 Vol.28 No.2 文章编号: 一类多目标非线性优化问题 一类多目标非线性优化问题
朱伟芬,陈雄达
(同济大学数学系,上海200092)
摘 要:多目标最优化问题广泛应用于工程技术、经济管理等诸多领域。许多数学工作者致力于多目标最优化理论
的研究,给出了多目标优化问题最优解的必要条件和充分条件。近年来,广义凸函数也越来越受到人们的重视,人们从不同的角度提出了广义凸函数的概念。在文献提出的非线性多目标优化问题的研究基础上,给出了在常秩约束规范(CRCQ)下,这一类优化问题最优解的必要条件和充分条件。 关键词:Pareto最优解;G-invex;KKT条件;CRCQ 中图分类号:O224 文献标志码:A
0 引言
考虑一般优化问题,形式如下:
s.t.gj(x)≤0,j∈J={1,2,⋯,m} (0.1)
其中,x∈ℝn称为决策变量,函数f(x), gj(x),j=1,⋯,m, ht(x)=0,t=1,⋯,p,都是定义在ℝn的实值函数。函数f(x):ℝn→ℝ称为目标函数。s.t.是英文subject to(满足于)的缩写。gj(x)≤0,j=1,⋯,m,ht(x)=0,t=1,⋯,p称为约束条件,而gj(x), ht(x)则分别称为不等式约束函数和等式约束函数。我们称集合
j
t
minf(x)
ht(x)=0,t∈T={1,2,⋯,p}
{x|g(x)≤0,j∈J,h(x)=0,t∈T}为可行域,记为D。若x∈D,则称x为可行点。设x是可行点,我们定义x处的有效集J(x)={j∈J,g(x)=0},等式约束条件和有效集对应的不等式约束条件统称为有效约束。
j
当目标函数和约束函数是可微的,则在一定约束规范下,问题(0.1)的局部最优解满足KKT条件,即存在λj,µt∈ℝ,使得下列等式和不等式系统成立:
∇f(x)+∑λj∇gj(x)+∑µt∇ht(x*)=0
*
m
*
p
λjgj(x*)=0,j∈Jλj≥0,µt∈ℝ
现在较为常用的约束规范主要有以下几个: 量组{∇gj(x),j∈J(x)}∪{∇ht(x),t∈T}线性无关。
j=1t=1
(0.2)
(1) LICQ (Linear Independence Constraint Qualification ):我们称优化问题在可行点x处满足LICQ,若向
若等式约束函数的梯度{∇ht(x),t∈T}线性无关,且存在一个向量d∈ℝn,使得
∇gj(x)d
T
T
(2) MFCQ (Mangasarian-Fromovitz Constraint Qualification):我们称优化问题在可行点x处满足MFCQ,
下面的约束规范由Mangasarian和Fromovitz于1967年在文献[1]中给出。
(3) CRCQ (Constant Rank Constraint Qualification[2]):我们称优化问题在可行点x处满足CRCQ,若存在x
收稿日期: 2011-1-28; 修回日期: 2011-2-23 作者简介: 朱伟芬(1987-),女,硕士,主要研究方向为运筹学与控制论,电子邮件地址[email protected]。
第2期 朱伟芬,陈雄达:一类多目标非线性优化问题 107
的邻域B(x,δ),使得对所有y∈B(x,δ),及J0⊆J(x),T0⊆T,向量组{∇gj(y),j∈J0}∪{∇ht(y),t∈T0}都具有 相同的秩,其中B(x,δ)={y|y−x2≤δ,δ>0}。
等价替换为两个不等式约束ht(x)≤0和−ht(x)≤0时,CRCQ仍成立,但LICQ和MFCQ并不具有这个性质,说明CRCQ比LICQ和MFCQ弱。
CPLD条件,对于任何J0⊆J(x)与T0⊆T,当向量组{∇gj(x),j∈J0}∪{∇ht(x),t∈T0}在可行点x处是正线性相关。其中,对于向量vi∈ℝn,i=1,2,⋯,k,我们称向量组{v1,v2,⋯,vk}正线性相关,若存在不全为0的实
ki=1
显然,当所有的约束为仿射函数时,CRCQ恒成立。如果在x处CRCQ成立,则当把等式约束ht(x)=0
(4) CPLD条件 (Constant Positive Linear Dependence Condition [9]):我们称优化问题在可行点x处满足
相关时,存在x的邻域B(x,δ),使得对所有y∈B(x,δ),向量组{∇gj(y),j∈J0}∪{∇ht(y),t∈T0}也是正线性
数ai≥0,i=1,2,⋯,k,使∑aivi=0。 LICQ⇒CRCQ⇒CPLD。
由参考文献[1]至[3],以上四个约束规范的关系有如下关系:LICQ⇒MFCQ⇒CPLD,
文献[4]给出了在MFCQ约束规范条件下的一类非线性约束优化问题最优解的必要条件以及充分条件。在此基础上,本文提出了在一定约束规范下,这类多目标优化问题最优解的必要条件仍然是KKT条件,并给出了新的最优充分条件。文章主要内容如下:首先,我们给出一些基本定义和预备知识;然后,给出了主要结论;最后是总结。
1 预备知识
首先,在说明文献[4]提及的优化问题之前,我们先介绍以下符号以及定义(见文献[5]至[9])。
ℝn(n≥1)表示实n维列向量空间,对于任何x=(x1,⋯,xn)∈ℝn,y=(y1,⋯,yn)∈ℝn,上标“T”表示 转置。定义:
(2) x
TT
(3) x≤y, 若xi≤yi,i=1,2,⋯,n;
定义1.1 C⊆ℝn称为凸集,若对任意x,y∈C和实数λ∈(0,1),有
(1−λ)x+λy∈C
定义1.2 我们称函数f:C→ℝ为凸函数,其中C是ℝn上的凸集,若对任意x,y∈C和实数λ∈(0,1)有
f((1−λ)x+λy)≤(1−λ)f(x)+λf(y) (1.1)
若不等式(1.1)严格成立,则称函数f是严格凸函数。
定义1.3 我们称可微函数f:X→ℝ,其中非空开集X⊆ℝn,我们称函数f为关于η的不变凸 (invex)函数,若存在函数η:X×X→ℝn,使得对所有x,u∈X,都有
T
本文研究的优化问题包含了一类广义凸函数。我们先来看看不变凸函数(见文献[10])的定义。
f(x)−f(u)≥η(x,u)∇f(u) (1.2)
显然,当η(x,u)=x−u时,函数f就是按照1.2定义的凸函数。当不等式(1.2)的反向成立时,我们称函数f为关于η的incave函数。
关于invex函数的更多理论知识,见文献[11]至[15]。
108 上海第二工业大学学报 2011年 第28卷
定义1.4我们称函数f:ℝ→ℝ为严格增函数,若对于x,y∈ℝ,且x
X⊆ℝn,Ifi(X)表示fi的值域,即Ifi(X)={y|y=fi(x),x∈X}。
下面,我们给出G-invex函数的定义。记向量函数f(x)=(f1(x),⋯,fk(x)):X→ℝk,其中非空开集
量函数Gf=Gf1,⋯,Gfk:ℝ→ℝk,分量函数Gfi:Ifi→ℝ是在定义域Ifi(X)上都是严格增函数,且存在函
定义1.5 f=(f1,⋯,fk):X→ℝk是定义在非空开集X⊆ℝn的可微向量函数。设u∈X,若存在可微向
()
数η:X×X→ℝn, 对于任意x∈X\{u},对于任意i=1,⋯,k, 都有
则称f在u点满足关于η的Gf-invex性质。若(1.3)对每个u∈X都满足,则称f是关于η的Gf-invex函数。当不等式(1.3)严格成立时,则称f在u点满足关于η的严格Gf-invex性质。若不等式(1.3)对每个u∈X都严格成立,则称f在X是一个关于η的严格Gf-invex函数。
注 当把不等式(1.3)反向或者严格反向时,可以得到f是关于η的Gf-incave函数或者严格Gf-incave函我们来介绍下多目标优化问题。多目标优化问题具有如下一般形式:
Gfi(fi(x))−Gfi(fi(u))≥G′fi(fi(u))∇fi(u)η(x,u) (1.3)
T
数的定义。
s.t.gj(x)≤0,j∈J={1,2,⋯,m} (1.4)
ht(x)=0,t∈T={1,2,⋯,p}
优化问题(1.4)是将优化问题(0.1)的目标函数变成向量函数。求解多目标优化问题通常是求它的弱Pareto最优解。.弱Pareto最优解定义如下:
定义1.6 我们称可行点x*为优化问题(1.4)的Pareto最优解或者有效解,若不存在x∈D,使得
f(x)≤f(x*) (1.5)
*
minf(x)=(f1(x),⋯,fk(x))
当不等式(1.5)严格成立时,我们称可行点x是问题(1.4) 的弱Pareto最优解或弱有效解。
T. Antczak在文献[16]至[18]中讨论了目标函数和约束函数是Gf-invex函数时,多目标优化问题(1.4)最优解的充分必要条件。文献[4]考虑的函数除了包含Gf-invex函数以外,还包含一类不可微函数——支撑函数,具体定义:
定义1.7 C⊂ℝn是紧凸集,定义C上的支撑函数s(x|C):=max{xTy:y∈C}。我们称一个集合是紧集,
若它的任意开覆盖都有有限子覆盖。特别地,ℝn有界闭集是紧集。 次梯度,若对于所有x∈X,都有
所有在x0的次梯度的集合称为次微分,记为∂f(x0)。
f(x)−f(x0)≥vT(x−x0)
定义1.8 设函数f:X→ℝ是一个凸函数,其中X⊆ℝn是凸集,向量v∈ℝn称为函数f在点x0∈X的
由凸分析的基础理论[2]可知,支撑函数s(x|C)是凸的,处处有限并且是有次梯度的,可以得出支撑函数s(x|C)的次梯度∂s(x|C)={z∈C:zTx=s(x|C)}。
2 主要结果
本文考虑了如下形式的非线性多目标规划问题:
第2期 朱伟芬,陈雄达:一类多目标非线性优化问题 109
s.t.
minGF1(f1(x)+s(x|C1)),⋯,GFk(fk(x)+s(x|Ck))
((G
g1h1
(g1(x)),⋯,Gg(gm(x)))≤0
m
)
(2.1)
其中fi:X→ℝ, i∈I={1,⋯,k}, gj:X→ℝ, j∈J={1,⋯,m}, ht:X→ℝ, t∈T={1,⋯,p},是定义在另假设GFi, i∈I, Ggj, j∈J, Ght, t∈T分别是定义在IFi(D), Igj(D), Iht(D)上的h(x)=(h1(x),⋯,hp(x))。
T
(G
(h1(x)),⋯,Gh
p
(h(x)))=0
p
X⊆ℝn的可微函数,Fi(x)=fi(x)+yiTx,yi∈Ci,记F(x)=(F1(x),⋯,Fk(x)),g(x)=(g1(x),⋯,gm(x)),
T
T
严格增函数,F(x)是GF-invex函数,g(x)是Gg-invex函数,h(x)是Gh-invex函数。我们称
D=x∈X:Ggj(gj(x))≤0,j∈J,Ght(ht(x))=0,t∈T
{}
为优化问题(2.1)的可行域。x∈D称为可行点。设x是可行点,我们定义在x处的有效集J(x)=
{j∈J,G(g(x))=0},等式约束条件和有效集对应的约束条件统称为有效约束。
gj
j
优化问题(2.1)的弱Pareto最优解有如下定义:
定义2.1 我们称可行点x*是优化问题(3.1)的弱Pareto最优解,若不存在x∈D, 使得 下面介绍CRCQ一些基本性质。
则存在x的两个邻域V1和V2,性质2.1[19] {fi(x)}i∈K的Jacobian矩阵{∇fi(x)}i∈K在点x*的某个邻域常秩,且存在某个局部微分同胚映射φ:V1→V2,使得
(ii) φ在x的Jacobian矩阵是单位矩阵;
*
*
GFi(fi(x)+s(x|Ci))
(i) φ(x*)=x*;
(iii) 函数fi(x) φ−1(i∈K)对所有的d∈E是常值,其中E:=d∈ℝn:∇fi(x)d=0,i∈K。
{
T
}
性质2.2[19] 假设在x满足常秩约束规范,则对集合
*
{d∈ℝ
(i)
t→0+
n
|∇gj()d≤0,j∈J(),∇ht()d=0,t∈T (2.3)
T
T
}
中的每个向量d,都有:存在弧t→ξ(t),t∈(0,),>0, 使得ξ(t)⊂D, 且有
limξ(t)=x,lim+
*
t→0
ξ(t)−x*
=d;
(ii) 对满足∇gj(x*)d=0的j∈J(x*),则有gj(ξ(t))=0。
T
定义2.1 函数f:X→ℝ在x处的方向导数定义为f′(x;d):=lim
t→0
f(x+td)−f(x)
。
下面我们来说明在CRCQ下优化问题(2.1)的Pareto最优解必要条件。
成立,则存在λ∈ℝk,ξ∈ℝm,µ∈ℝp,ωi∈Ci,使得
IFi(D), Igj(D), Iht(D)上的可微严格增实函数。x*∈D是优化问题(2.1)一个弱Pareto最优解,且在x*CRCQ
定理2.1 (G-Karush-Kuhn-Tucker必要最优性条件) 设GFi, i∈I, Ggj, j∈J, Ght, t∈T分别是定义在
∑λG′(f(x)+x
ki=1m
i
Fi
i
*
*T
′gj(xωi∇fi(x)+ωi+∑ξjGg
)(
*
)
m
∑ξG(g(x))=0;
j∈J,λ≥0,ξ≥0
j=1
j
gj
j
*
j=1
j
(
*
))(∇g(x))+∑µG′(h(x))(∇h(x))=0
j
*
mj=1
t
ht
t
*
t
*
ωiTx*=s(x*|Ci)
(2.4)
110 上海第二工业大学学报 2011年 第28卷
证明 在x处CRCQ成立,由性质2.2可知,对于集合
d∈ℝn|∇gj(x*)d≤0,j∈J(x*),∇ht(x*)d=0,t∈T
*
中的每个向量d, 都有:存在弧ξ(t)=φ−1(x*+td),满足t∈(0,),>0,使得ξ(t)⊂D,有
t→0+
{
TT
}
limξ(t)=x,lim+
*
t→0
ξ(t)−x*
=d
显然,有φ(ξ(t))=x*+td,由性质2.1可知,对于足够小的t,有φ(ξ(t))=ξ(t)=x*+td。 假设bi(x*)=s(x*|Ci),i=1,2,⋯,k,由于Ci是凸紧集,则方向导数
bi′(x;d)=lim+
*
t→0
bi(x*+td)−bi(x*)
=ωiTd
其中ωi∈∂s(x*|Ci),且对所有的d∈ℝn,都有
(G
lim+
t→0
Fi
(fi+bi)′(x;d)=
GFi(fi(x*+td)+bi(x*+td))−GFi(fi(x*)+bi(x*))
)
由于fi的可微性可知,∇fi(x*;d)=∇fiTd。 所以式(2.5)变为
GFi′(fi(x*)+bi(x*))∇fi(x*;d)+bi′(x*;d)
(
= (2.5)
)
(G
Fi
(fi+bi)′(x;d)=GFi′(fi(x*)+bi(x*))(∇fiTd+ωiTd)
)
因为x*∈D是优化问题(2.1)一个弱Pareto最优解,则找不到d∈ℝn使得以下等式和不等式系统成立:
GFi′(fi(x*)+bi(x*))(∇fi(x*)Td+ωiTd)
由择一性定理(见文献[11]),存在λi≥0,i∈I,ξj≥0,j∈J(),µt∈ℝ,t∈T,λi≥0不全为0,使得
TT
(2.6)
∑λG′(f(x)+b(x))(∇f(x)
ki=1
i
Fi
i
*
i
*
i
*T
+ωi
T
)+∑ξG′(g(x))∇g(x)+∑µG′(h(x))∇h(x)=0
j∈J()
jgjj
*
j
*
p
t=1
thtt
*
t
*
令ξj=0,j∉J(x*)。
综上,原命题得证。
下面我们来说明一个优化问题(2.1)最优解的充分条件。
定义2.2 设x*∈D,d∈ℝn,如果存在序列dk∈ℝn,k=1,2,⋯和实数δk>0,k=1,2,⋯,使得
x*+δkdk∈D,∀k
SFD(x*,D)。
(2.7)
且有dk→d, δk→0,称d是D在x*处的序列可行方向。D在x*处的所有序列可行方向构成的集合记为
定理2.2 (充分最优性条件) 设x*∈D。对于优化问题(2.1),若有
dT(∇f(x*)+ωi)>0,ωi∈∂s(x*|Ci) ,∀0≠d∈SFD(x*,D) (2.8)
则x*是问题(2.1)的弱Pareto最优解。
第2期 朱伟芬,陈雄达:一类多目标非线性优化问题 111
证明 假设x*不是问题(2.1)的弱Pareto最优解,则存在xk∈D,使得
GFi(fi(xk)+s(xk|Ci))
且有xk→x*, xk≠x*。不失一般性,我们可以假定
k−令dk=
xk−x*
2
→d (2.10)
k−T
xk−x*
2
δk=xk−x*
2
,中i
2
表示向量的二范数,定义
为x2=
,
由于式(2.8)以及ωi∈∂s(x*|Ci)可知
x=(x1,⋯,xn)∈ℝn。根据定义2.2可知,0≠d∈SFD(x*,D)。
GFi(fi(xk)+ωiTxk)≤GFi(fi(xk)+s(xk|Ci))
GFi(fi(x*)+ωiTx*)
GFi(fi(x*)+s(x*|Ci))=
(2.11)
因为
GFi(fi(xk)+ωiTxk)−GFi(fi(x*)+ωiTx*)=′(fi(x)+ωixδkGF
(
*T*
i
)(∇f(x)+ω))
i
*
i
T
dk+ο(δkdk
2
)
(2.12)
由式(2.10),GFi的严格增性,以及δk>0,对式(2.11)左右两边取极限,可得:
dT(∇f(x*)+ωi)≤0
与式(2.8)矛盾。
所以,x*是问题(2.1)的弱Pareto最优解,原命题得证。
(2.13)
3 总结
凸性是一个基本数学概念,在许多数学问题中起到重要的作用。但是,在实际中,很多问题并不满足凸性条件。适当地放宽凸性条件限制,推广凸函数的概念,成为具有实际应用和理论意义的问题。文献[4]提出了一类包含G-invex函数的非线性多目标优化问题,给出了在MFCQ下这类优化问题最优解的必要条件以及充分条件。本文则在此基础之上,给出了在更弱的CRCQ约束规范下这类多目标优化问题最优解的必要条件和充分条件,说明了在更弱的CRCQ下,弱Pareto解的必要条件仍然是KKT条件。 参考文献:
[1] MANGASARIAN O L, FROMOVITZ S. The necessary optimality conditions in the presence of equality and inequality constraints [J]. Journal of
Mathematical Analysis and Applications, 1967, 17: 37-47.
[2] ROCKAFELLAR R T. Convex Analysis[M]. N. J. Princeton: Princeton University Press, 1997.
[3] QI L, WEI Z. On the constant positive linear dependence condition and its application to SQP methods[J]. SIAM Journal on Optimization, 2000, 10:
963-981.
[4] KIM H J, SEO Y Y. KIM D S. Optimality conditions in nondifferentiable G-invex muliti-objective programming[J]. Journal of Inequalities and
Applications, Volume 2010, Article ID 172059: 1-13. [6] AIBIN J P. Optima and Equilibria: An Introduction to Nonlinear Analysis[M].Berlin Heidelberg: Springer Verlag, 1993. [7] 袁亚湘. 非线性规划数值方法[M]. 上海: 上海科学技术出版社, 1993. [8] 袁亚湘,孙文瑜. 最优化理论与方法[M]. 北京: 科学出版社, 1997.
[5] 胡毓达. 实用多目标最优化[M]. 上海: 上海科学技术出版社, 1990
[9] NOCEDAL J,WRIGHT S J. Numerical Optimization[M]. 北京: 科学出版社, 2006.
[10] HANSON M A. On sufficiency of the Kuhn-Tucker condition[J]. Journal of Mathematical Analysis and Applications, 1981, 80: 545-550. [11] CRAVEN B D. Invex functions and constrained local minima[J]. Bull. Austral. Math. Soc., 1981, 24: 357-366.
112 上海第二工业大学学报 2011年 第28卷 [12] CRAVEN B D, CLOVER B M. Invex function and duality[J]. Journal of the Australian Mathematical Society, Series A, 1985, 39(1): 1-20. [13] MARTIN D H. The essence of invexity[J]. Journal of Optimization Theory and Applications, 1985, 47(1): 65-76. [14] ISREAL A B, MOND B. What is invexity?[J]. J. Austral. Math. Soc. Sen. B, 1986, 28: 1-9.
[15] HANSON M A, MOND B. Necessary and sufficient conditions in constrained optimization[J]. Math. Programming, 1987, 37: 51-58.
[16] ANTCZAK T. New optimality conditions and duality results of G type in differentiable mathematical programming[J]. Nonlinear Analysis, 2007,
66: 1617-1632.
[17] ANTCZAK T. On G-invex multi-objective programming. I. optimality[J]. Journal of Global Optimization, 2009, 43 (1): 97-109. [18] ANTCZAK T. On G-invex multi-objective programming. Ⅱ. Duality[J]. Journal of Global Optimization, 2009, 43 (1): 111-140. [19] JANIN R. Direction derivative of the marginal function in nonlinear programming[J]. Math. Program. Stud., 1984, 21: 127-138.
Optimality Conditions in Nondifferentiable
Multi-objective Programming
ZHU Wei-fen, CHEN Xiong-da
(Department of Mathematics, Tong Ji University, Shanghai 200092, P. R. China)
Abstract: The multi-objective optimization problems are widely used in engineering, economic management and so on. Many mathematicians committed to the research of multi-objective optimization theory, and necessary and sufficient conditions of the optimal solution of multi-objective optimization are given. In recent years, generalized convex functions play a more important role and many generalized convex functions are generalized from different perspectives. In this paper, necessary and sufficient conditions of the optimal solution of some multi-objective optimization which was proposed in literature under Constant Rank Constraint Qualification (CRCQ) are given.
Keywords: pateto optimal solution; G-invex; KKT condition; CRCR
第28卷 第2期 上海第二工业大学学报 Vol.28 No.2 文章编号: 一类多目标非线性优化问题 一类多目标非线性优化问题
朱伟芬,陈雄达
(同济大学数学系,上海200092)
摘 要:多目标最优化问题广泛应用于工程技术、经济管理等诸多领域。许多数学工作者致力于多目标最优化理论
的研究,给出了多目标优化问题最优解的必要条件和充分条件。近年来,广义凸函数也越来越受到人们的重视,人们从不同的角度提出了广义凸函数的概念。在文献提出的非线性多目标优化问题的研究基础上,给出了在常秩约束规范(CRCQ)下,这一类优化问题最优解的必要条件和充分条件。 关键词:Pareto最优解;G-invex;KKT条件;CRCQ 中图分类号:O224 文献标志码:A
0 引言
考虑一般优化问题,形式如下:
s.t.gj(x)≤0,j∈J={1,2,⋯,m} (0.1)
其中,x∈ℝn称为决策变量,函数f(x), gj(x),j=1,⋯,m, ht(x)=0,t=1,⋯,p,都是定义在ℝn的实值函数。函数f(x):ℝn→ℝ称为目标函数。s.t.是英文subject to(满足于)的缩写。gj(x)≤0,j=1,⋯,m,ht(x)=0,t=1,⋯,p称为约束条件,而gj(x), ht(x)则分别称为不等式约束函数和等式约束函数。我们称集合
j
t
minf(x)
ht(x)=0,t∈T={1,2,⋯,p}
{x|g(x)≤0,j∈J,h(x)=0,t∈T}为可行域,记为D。若x∈D,则称x为可行点。设x是可行点,我们定义x处的有效集J(x)={j∈J,g(x)=0},等式约束条件和有效集对应的不等式约束条件统称为有效约束。
j
当目标函数和约束函数是可微的,则在一定约束规范下,问题(0.1)的局部最优解满足KKT条件,即存在λj,µt∈ℝ,使得下列等式和不等式系统成立:
∇f(x)+∑λj∇gj(x)+∑µt∇ht(x*)=0
*
m
*
p
λjgj(x*)=0,j∈Jλj≥0,µt∈ℝ
现在较为常用的约束规范主要有以下几个: 量组{∇gj(x),j∈J(x)}∪{∇ht(x),t∈T}线性无关。
j=1t=1
(0.2)
(1) LICQ (Linear Independence Constraint Qualification ):我们称优化问题在可行点x处满足LICQ,若向
若等式约束函数的梯度{∇ht(x),t∈T}线性无关,且存在一个向量d∈ℝn,使得
∇gj(x)d
T
T
(2) MFCQ (Mangasarian-Fromovitz Constraint Qualification):我们称优化问题在可行点x处满足MFCQ,
下面的约束规范由Mangasarian和Fromovitz于1967年在文献[1]中给出。
(3) CRCQ (Constant Rank Constraint Qualification[2]):我们称优化问题在可行点x处满足CRCQ,若存在x
收稿日期: 2011-1-28; 修回日期: 2011-2-23 作者简介: 朱伟芬(1987-),女,硕士,主要研究方向为运筹学与控制论,电子邮件地址[email protected]。
第2期 朱伟芬,陈雄达:一类多目标非线性优化问题 107
的邻域B(x,δ),使得对所有y∈B(x,δ),及J0⊆J(x),T0⊆T,向量组{∇gj(y),j∈J0}∪{∇ht(y),t∈T0}都具有 相同的秩,其中B(x,δ)={y|y−x2≤δ,δ>0}。
等价替换为两个不等式约束ht(x)≤0和−ht(x)≤0时,CRCQ仍成立,但LICQ和MFCQ并不具有这个性质,说明CRCQ比LICQ和MFCQ弱。
CPLD条件,对于任何J0⊆J(x)与T0⊆T,当向量组{∇gj(x),j∈J0}∪{∇ht(x),t∈T0}在可行点x处是正线性相关。其中,对于向量vi∈ℝn,i=1,2,⋯,k,我们称向量组{v1,v2,⋯,vk}正线性相关,若存在不全为0的实
ki=1
显然,当所有的约束为仿射函数时,CRCQ恒成立。如果在x处CRCQ成立,则当把等式约束ht(x)=0
(4) CPLD条件 (Constant Positive Linear Dependence Condition [9]):我们称优化问题在可行点x处满足
相关时,存在x的邻域B(x,δ),使得对所有y∈B(x,δ),向量组{∇gj(y),j∈J0}∪{∇ht(y),t∈T0}也是正线性
数ai≥0,i=1,2,⋯,k,使∑aivi=0。 LICQ⇒CRCQ⇒CPLD。
由参考文献[1]至[3],以上四个约束规范的关系有如下关系:LICQ⇒MFCQ⇒CPLD,
文献[4]给出了在MFCQ约束规范条件下的一类非线性约束优化问题最优解的必要条件以及充分条件。在此基础上,本文提出了在一定约束规范下,这类多目标优化问题最优解的必要条件仍然是KKT条件,并给出了新的最优充分条件。文章主要内容如下:首先,我们给出一些基本定义和预备知识;然后,给出了主要结论;最后是总结。
1 预备知识
首先,在说明文献[4]提及的优化问题之前,我们先介绍以下符号以及定义(见文献[5]至[9])。
ℝn(n≥1)表示实n维列向量空间,对于任何x=(x1,⋯,xn)∈ℝn,y=(y1,⋯,yn)∈ℝn,上标“T”表示 转置。定义:
(2) x
TT
(3) x≤y, 若xi≤yi,i=1,2,⋯,n;
定义1.1 C⊆ℝn称为凸集,若对任意x,y∈C和实数λ∈(0,1),有
(1−λ)x+λy∈C
定义1.2 我们称函数f:C→ℝ为凸函数,其中C是ℝn上的凸集,若对任意x,y∈C和实数λ∈(0,1)有
f((1−λ)x+λy)≤(1−λ)f(x)+λf(y) (1.1)
若不等式(1.1)严格成立,则称函数f是严格凸函数。
定义1.3 我们称可微函数f:X→ℝ,其中非空开集X⊆ℝn,我们称函数f为关于η的不变凸 (invex)函数,若存在函数η:X×X→ℝn,使得对所有x,u∈X,都有
T
本文研究的优化问题包含了一类广义凸函数。我们先来看看不变凸函数(见文献[10])的定义。
f(x)−f(u)≥η(x,u)∇f(u) (1.2)
显然,当η(x,u)=x−u时,函数f就是按照1.2定义的凸函数。当不等式(1.2)的反向成立时,我们称函数f为关于η的incave函数。
关于invex函数的更多理论知识,见文献[11]至[15]。
108 上海第二工业大学学报 2011年 第28卷
定义1.4我们称函数f:ℝ→ℝ为严格增函数,若对于x,y∈ℝ,且x
X⊆ℝn,Ifi(X)表示fi的值域,即Ifi(X)={y|y=fi(x),x∈X}。
下面,我们给出G-invex函数的定义。记向量函数f(x)=(f1(x),⋯,fk(x)):X→ℝk,其中非空开集
量函数Gf=Gf1,⋯,Gfk:ℝ→ℝk,分量函数Gfi:Ifi→ℝ是在定义域Ifi(X)上都是严格增函数,且存在函
定义1.5 f=(f1,⋯,fk):X→ℝk是定义在非空开集X⊆ℝn的可微向量函数。设u∈X,若存在可微向
()
数η:X×X→ℝn, 对于任意x∈X\{u},对于任意i=1,⋯,k, 都有
则称f在u点满足关于η的Gf-invex性质。若(1.3)对每个u∈X都满足,则称f是关于η的Gf-invex函数。当不等式(1.3)严格成立时,则称f在u点满足关于η的严格Gf-invex性质。若不等式(1.3)对每个u∈X都严格成立,则称f在X是一个关于η的严格Gf-invex函数。
注 当把不等式(1.3)反向或者严格反向时,可以得到f是关于η的Gf-incave函数或者严格Gf-incave函我们来介绍下多目标优化问题。多目标优化问题具有如下一般形式:
Gfi(fi(x))−Gfi(fi(u))≥G′fi(fi(u))∇fi(u)η(x,u) (1.3)
T
数的定义。
s.t.gj(x)≤0,j∈J={1,2,⋯,m} (1.4)
ht(x)=0,t∈T={1,2,⋯,p}
优化问题(1.4)是将优化问题(0.1)的目标函数变成向量函数。求解多目标优化问题通常是求它的弱Pareto最优解。.弱Pareto最优解定义如下:
定义1.6 我们称可行点x*为优化问题(1.4)的Pareto最优解或者有效解,若不存在x∈D,使得
f(x)≤f(x*) (1.5)
*
minf(x)=(f1(x),⋯,fk(x))
当不等式(1.5)严格成立时,我们称可行点x是问题(1.4) 的弱Pareto最优解或弱有效解。
T. Antczak在文献[16]至[18]中讨论了目标函数和约束函数是Gf-invex函数时,多目标优化问题(1.4)最优解的充分必要条件。文献[4]考虑的函数除了包含Gf-invex函数以外,还包含一类不可微函数——支撑函数,具体定义:
定义1.7 C⊂ℝn是紧凸集,定义C上的支撑函数s(x|C):=max{xTy:y∈C}。我们称一个集合是紧集,
若它的任意开覆盖都有有限子覆盖。特别地,ℝn有界闭集是紧集。 次梯度,若对于所有x∈X,都有
所有在x0的次梯度的集合称为次微分,记为∂f(x0)。
f(x)−f(x0)≥vT(x−x0)
定义1.8 设函数f:X→ℝ是一个凸函数,其中X⊆ℝn是凸集,向量v∈ℝn称为函数f在点x0∈X的
由凸分析的基础理论[2]可知,支撑函数s(x|C)是凸的,处处有限并且是有次梯度的,可以得出支撑函数s(x|C)的次梯度∂s(x|C)={z∈C:zTx=s(x|C)}。
2 主要结果
本文考虑了如下形式的非线性多目标规划问题:
第2期 朱伟芬,陈雄达:一类多目标非线性优化问题 109
s.t.
minGF1(f1(x)+s(x|C1)),⋯,GFk(fk(x)+s(x|Ck))
((G
g1h1
(g1(x)),⋯,Gg(gm(x)))≤0
m
)
(2.1)
其中fi:X→ℝ, i∈I={1,⋯,k}, gj:X→ℝ, j∈J={1,⋯,m}, ht:X→ℝ, t∈T={1,⋯,p},是定义在另假设GFi, i∈I, Ggj, j∈J, Ght, t∈T分别是定义在IFi(D), Igj(D), Iht(D)上的h(x)=(h1(x),⋯,hp(x))。
T
(G
(h1(x)),⋯,Gh
p
(h(x)))=0
p
X⊆ℝn的可微函数,Fi(x)=fi(x)+yiTx,yi∈Ci,记F(x)=(F1(x),⋯,Fk(x)),g(x)=(g1(x),⋯,gm(x)),
T
T
严格增函数,F(x)是GF-invex函数,g(x)是Gg-invex函数,h(x)是Gh-invex函数。我们称
D=x∈X:Ggj(gj(x))≤0,j∈J,Ght(ht(x))=0,t∈T
{}
为优化问题(2.1)的可行域。x∈D称为可行点。设x是可行点,我们定义在x处的有效集J(x)=
{j∈J,G(g(x))=0},等式约束条件和有效集对应的约束条件统称为有效约束。
gj
j
优化问题(2.1)的弱Pareto最优解有如下定义:
定义2.1 我们称可行点x*是优化问题(3.1)的弱Pareto最优解,若不存在x∈D, 使得 下面介绍CRCQ一些基本性质。
则存在x的两个邻域V1和V2,性质2.1[19] {fi(x)}i∈K的Jacobian矩阵{∇fi(x)}i∈K在点x*的某个邻域常秩,且存在某个局部微分同胚映射φ:V1→V2,使得
(ii) φ在x的Jacobian矩阵是单位矩阵;
*
*
GFi(fi(x)+s(x|Ci))
(i) φ(x*)=x*;
(iii) 函数fi(x) φ−1(i∈K)对所有的d∈E是常值,其中E:=d∈ℝn:∇fi(x)d=0,i∈K。
{
T
}
性质2.2[19] 假设在x满足常秩约束规范,则对集合
*
{d∈ℝ
(i)
t→0+
n
|∇gj()d≤0,j∈J(),∇ht()d=0,t∈T (2.3)
T
T
}
中的每个向量d,都有:存在弧t→ξ(t),t∈(0,),>0, 使得ξ(t)⊂D, 且有
limξ(t)=x,lim+
*
t→0
ξ(t)−x*
=d;
(ii) 对满足∇gj(x*)d=0的j∈J(x*),则有gj(ξ(t))=0。
T
定义2.1 函数f:X→ℝ在x处的方向导数定义为f′(x;d):=lim
t→0
f(x+td)−f(x)
。
下面我们来说明在CRCQ下优化问题(2.1)的Pareto最优解必要条件。
成立,则存在λ∈ℝk,ξ∈ℝm,µ∈ℝp,ωi∈Ci,使得
IFi(D), Igj(D), Iht(D)上的可微严格增实函数。x*∈D是优化问题(2.1)一个弱Pareto最优解,且在x*CRCQ
定理2.1 (G-Karush-Kuhn-Tucker必要最优性条件) 设GFi, i∈I, Ggj, j∈J, Ght, t∈T分别是定义在
∑λG′(f(x)+x
ki=1m
i
Fi
i
*
*T
′gj(xωi∇fi(x)+ωi+∑ξjGg
)(
*
)
m
∑ξG(g(x))=0;
j∈J,λ≥0,ξ≥0
j=1
j
gj
j
*
j=1
j
(
*
))(∇g(x))+∑µG′(h(x))(∇h(x))=0
j
*
mj=1
t
ht
t
*
t
*
ωiTx*=s(x*|Ci)
(2.4)
110 上海第二工业大学学报 2011年 第28卷
证明 在x处CRCQ成立,由性质2.2可知,对于集合
d∈ℝn|∇gj(x*)d≤0,j∈J(x*),∇ht(x*)d=0,t∈T
*
中的每个向量d, 都有:存在弧ξ(t)=φ−1(x*+td),满足t∈(0,),>0,使得ξ(t)⊂D,有
t→0+
{
TT
}
limξ(t)=x,lim+
*
t→0
ξ(t)−x*
=d
显然,有φ(ξ(t))=x*+td,由性质2.1可知,对于足够小的t,有φ(ξ(t))=ξ(t)=x*+td。 假设bi(x*)=s(x*|Ci),i=1,2,⋯,k,由于Ci是凸紧集,则方向导数
bi′(x;d)=lim+
*
t→0
bi(x*+td)−bi(x*)
=ωiTd
其中ωi∈∂s(x*|Ci),且对所有的d∈ℝn,都有
(G
lim+
t→0
Fi
(fi+bi)′(x;d)=
GFi(fi(x*+td)+bi(x*+td))−GFi(fi(x*)+bi(x*))
)
由于fi的可微性可知,∇fi(x*;d)=∇fiTd。 所以式(2.5)变为
GFi′(fi(x*)+bi(x*))∇fi(x*;d)+bi′(x*;d)
(
= (2.5)
)
(G
Fi
(fi+bi)′(x;d)=GFi′(fi(x*)+bi(x*))(∇fiTd+ωiTd)
)
因为x*∈D是优化问题(2.1)一个弱Pareto最优解,则找不到d∈ℝn使得以下等式和不等式系统成立:
GFi′(fi(x*)+bi(x*))(∇fi(x*)Td+ωiTd)
由择一性定理(见文献[11]),存在λi≥0,i∈I,ξj≥0,j∈J(),µt∈ℝ,t∈T,λi≥0不全为0,使得
TT
(2.6)
∑λG′(f(x)+b(x))(∇f(x)
ki=1
i
Fi
i
*
i
*
i
*T
+ωi
T
)+∑ξG′(g(x))∇g(x)+∑µG′(h(x))∇h(x)=0
j∈J()
jgjj
*
j
*
p
t=1
thtt
*
t
*
令ξj=0,j∉J(x*)。
综上,原命题得证。
下面我们来说明一个优化问题(2.1)最优解的充分条件。
定义2.2 设x*∈D,d∈ℝn,如果存在序列dk∈ℝn,k=1,2,⋯和实数δk>0,k=1,2,⋯,使得
x*+δkdk∈D,∀k
SFD(x*,D)。
(2.7)
且有dk→d, δk→0,称d是D在x*处的序列可行方向。D在x*处的所有序列可行方向构成的集合记为
定理2.2 (充分最优性条件) 设x*∈D。对于优化问题(2.1),若有
dT(∇f(x*)+ωi)>0,ωi∈∂s(x*|Ci) ,∀0≠d∈SFD(x*,D) (2.8)
则x*是问题(2.1)的弱Pareto最优解。
第2期 朱伟芬,陈雄达:一类多目标非线性优化问题 111
证明 假设x*不是问题(2.1)的弱Pareto最优解,则存在xk∈D,使得
GFi(fi(xk)+s(xk|Ci))
且有xk→x*, xk≠x*。不失一般性,我们可以假定
k−令dk=
xk−x*
2
→d (2.10)
k−T
xk−x*
2
δk=xk−x*
2
,中i
2
表示向量的二范数,定义
为x2=
,
由于式(2.8)以及ωi∈∂s(x*|Ci)可知
x=(x1,⋯,xn)∈ℝn。根据定义2.2可知,0≠d∈SFD(x*,D)。
GFi(fi(xk)+ωiTxk)≤GFi(fi(xk)+s(xk|Ci))
GFi(fi(x*)+ωiTx*)
GFi(fi(x*)+s(x*|Ci))=
(2.11)
因为
GFi(fi(xk)+ωiTxk)−GFi(fi(x*)+ωiTx*)=′(fi(x)+ωixδkGF
(
*T*
i
)(∇f(x)+ω))
i
*
i
T
dk+ο(δkdk
2
)
(2.12)
由式(2.10),GFi的严格增性,以及δk>0,对式(2.11)左右两边取极限,可得:
dT(∇f(x*)+ωi)≤0
与式(2.8)矛盾。
所以,x*是问题(2.1)的弱Pareto最优解,原命题得证。
(2.13)
3 总结
凸性是一个基本数学概念,在许多数学问题中起到重要的作用。但是,在实际中,很多问题并不满足凸性条件。适当地放宽凸性条件限制,推广凸函数的概念,成为具有实际应用和理论意义的问题。文献[4]提出了一类包含G-invex函数的非线性多目标优化问题,给出了在MFCQ下这类优化问题最优解的必要条件以及充分条件。本文则在此基础之上,给出了在更弱的CRCQ约束规范下这类多目标优化问题最优解的必要条件和充分条件,说明了在更弱的CRCQ下,弱Pareto解的必要条件仍然是KKT条件。 参考文献:
[1] MANGASARIAN O L, FROMOVITZ S. The necessary optimality conditions in the presence of equality and inequality constraints [J]. Journal of
Mathematical Analysis and Applications, 1967, 17: 37-47.
[2] ROCKAFELLAR R T. Convex Analysis[M]. N. J. Princeton: Princeton University Press, 1997.
[3] QI L, WEI Z. On the constant positive linear dependence condition and its application to SQP methods[J]. SIAM Journal on Optimization, 2000, 10:
963-981.
[4] KIM H J, SEO Y Y. KIM D S. Optimality conditions in nondifferentiable G-invex muliti-objective programming[J]. Journal of Inequalities and
Applications, Volume 2010, Article ID 172059: 1-13. [6] AIBIN J P. Optima and Equilibria: An Introduction to Nonlinear Analysis[M].Berlin Heidelberg: Springer Verlag, 1993. [7] 袁亚湘. 非线性规划数值方法[M]. 上海: 上海科学技术出版社, 1993. [8] 袁亚湘,孙文瑜. 最优化理论与方法[M]. 北京: 科学出版社, 1997.
[5] 胡毓达. 实用多目标最优化[M]. 上海: 上海科学技术出版社, 1990
[9] NOCEDAL J,WRIGHT S J. Numerical Optimization[M]. 北京: 科学出版社, 2006.
[10] HANSON M A. On sufficiency of the Kuhn-Tucker condition[J]. Journal of Mathematical Analysis and Applications, 1981, 80: 545-550. [11] CRAVEN B D. Invex functions and constrained local minima[J]. Bull. Austral. Math. Soc., 1981, 24: 357-366.
112 上海第二工业大学学报 2011年 第28卷 [12] CRAVEN B D, CLOVER B M. Invex function and duality[J]. Journal of the Australian Mathematical Society, Series A, 1985, 39(1): 1-20. [13] MARTIN D H. The essence of invexity[J]. Journal of Optimization Theory and Applications, 1985, 47(1): 65-76. [14] ISREAL A B, MOND B. What is invexity?[J]. J. Austral. Math. Soc. Sen. B, 1986, 28: 1-9.
[15] HANSON M A, MOND B. Necessary and sufficient conditions in constrained optimization[J]. Math. Programming, 1987, 37: 51-58.
[16] ANTCZAK T. New optimality conditions and duality results of G type in differentiable mathematical programming[J]. Nonlinear Analysis, 2007,
66: 1617-1632.
[17] ANTCZAK T. On G-invex multi-objective programming. I. optimality[J]. Journal of Global Optimization, 2009, 43 (1): 97-109. [18] ANTCZAK T. On G-invex multi-objective programming. Ⅱ. Duality[J]. Journal of Global Optimization, 2009, 43 (1): 111-140. [19] JANIN R. Direction derivative of the marginal function in nonlinear programming[J]. Math. Program. Stud., 1984, 21: 127-138.
Optimality Conditions in Nondifferentiable
Multi-objective Programming
ZHU Wei-fen, CHEN Xiong-da
(Department of Mathematics, Tong Ji University, Shanghai 200092, P. R. China)
Abstract: The multi-objective optimization problems are widely used in engineering, economic management and so on. Many mathematicians committed to the research of multi-objective optimization theory, and necessary and sufficient conditions of the optimal solution of multi-objective optimization are given. In recent years, generalized convex functions play a more important role and many generalized convex functions are generalized from different perspectives. In this paper, necessary and sufficient conditions of the optimal solution of some multi-objective optimization which was proposed in literature under Constant Rank Constraint Qualification (CRCQ) are given.
Keywords: pateto optimal solution; G-invex; KKT condition; CRCR