一类典型非凸域动约束函数构造

吴 铮，刘庆怀，商玉凤

(1.长春工业大学 数学与统计学院，吉林 长春 130012;2.长春财经学院 经济学院，吉林 长春 130122)

0 引 言

考虑如下形式的非凸规划问题

minf(x),

s.t.gi(t)≤0,i=1,2,…,m,

(1)

其中f:Rn→R,g:Rn→Rm,g=(g1,g2,…,gm)T,f(x),gi(x)∈Cr(r≥2)。

易知(1)的KKT系统为

f(x)+g(x)y=0,

Yg(x)=0,y≥0,

(2)

其中

Y=diag{y1,y2,…,ym},

假设条件1：

(A1)Ω连通有界,Ω0非空;

(A2)当x∈∂Ω时,{gi(x)|i∈I(x)}是正独立的,即对任意给定的vi≥0,如果方程

成立,则必有

vi=0，i∈I(x)，

其中

Ω={x|gi(x)≤0,i=1,2,…,m},

Ω0={x|gi(x)<0,i=1,2,…,m},

∂Ω=ΩΩ0,

I(x)={i|gi(x)=0,i=1,2,…,m}。

文献[1]给出了一个求解非凸规划问题的动约束同伦方法(简称CSCH方法),通过构造动约束组合同伦方程,在弱条件下证明了CSCH方法的全局收敛性,并运用算例表明了CSCH方法的有效性和可行性。文献[2-6]将CSCH方法应用到解无界非凸域上多目标规划问题、变分不等式问题、不动点问题上;文献[7]利用凝聚光滑化方法,给出了求解非凸优化问题的凝聚CSCH方法。在利用CSCH方法求解非凸规划问题时,如何构造动约束函数成为关键点。

文中首先给出了多尖非凸域的定义,在该区域上构造了动约束函数,并在较弱条件下证明了该动约束函数满足边界正则性条件及法锥条件,最后,通过数值例子表明构造方法是可行的、有效的。

1 预备知识

定义1(正则性定义) 设φ:D⊂Rm→Rn是光滑映射,任意的y∈Rn,记φ-1(y)={x∈D|φ(x)=y}为y在映射φ下的逆像。如果φ在x(0)∈D处的Jacobi矩阵∂φ(x(0))∂x行满秩,则称x(0)是映射φ的正则点;否则称x(0)是映射φ的临界点。如果对所有的x(0)∈φ-1(y(0))都是映射φ的正则点;则称y(0)是映射φ的正则值;否则称y(0)是映射φ的临界值。

引理1(参数化的Sard定理) 设V⊂Rn,U⊂Rm均为开集,φ:V×U→RP是Cr映射,这里r>max{0,m-p}。如果0∈RP是φ的一个正则值,则对几乎所有a∈V,0是φ(a,·)的一个正则值。

引理2(逆映像定理) 如果0是映射φ(a,·)的正则值,则逆映射φ-1(a,·)由有限条一维光滑流形组成。

引理3(一维流形分类定理) 一维带边光滑流形的每个连通分支,或者微分同胚于单位圆周S1,或者微分同胚于实数区间(0,1]或[0,1)或[0,1]。

为求解非凸优化问题(1),构造含参变量t的非凸优化问题

(3)

假设条件2:

(B3)对任意给定的t∈(0,1],Ω(t)是连通有界非空闭集;

(B5)Ω(1)满足法锥条件,即对任意的x∈∂Ω(1),

其中符号说明如下:

∂Ω(t)=Ω(t)〗Ω0(t);

(4)

式中：D=t(x-x0)。

H-1(0)={t∈(0,1],x∈Ω(t),

2 典型非凸域的动约束函数构造

首先给出2维情形下多尖非凸域上的动约束函数构造方法,然后将该构造方法从2维情形推广到n维情形。

定义2设

(5)

i=1,2,…,n,

若

Ω={x|gi(x)≤0，i=1,2,…,2n}

为含原点的连通有界闭区域,则称该区域为多尖非凸域,其中aij,bi(i=1，2，…,n,j=1，2，…,n)均为正值常数。

当n=2时，

(6)

图1 多尖非凸域(阴影部分)

为了证明非凸集Ω的有界性,在2维情形下给出如下定理。为方便讨论在式(6)中取

aij=a，j≠i,i=1,2,j=1,2,3,4,

bi=b，i=1,2,3,4，

令

Ω1={x|x1≥0，x2≥0，g1(x)≤0,g2(x)≤0},

Ω2={x|x1≤0，x2≥0，g1(x)≤0,g4(x)≤0},

Ω3={x|x1≥0，x2≤0，g2(x)≤0,g3(x)≤0},

Ω4={x|x1≤0，x2≤0，g3(x)≤0,g4(x)≤0},

其中

i=1,2,3,4,

且

图示意图(阴影部分)

为此仅需证方程组

(7)

即

(8)

一般情形,当aij

bi=b，i=1,2,3,4,

可同证Ω为有界闭集。

证毕。

类似地,在n维情形下可得到如下定理。为方便讨论在式(5)中取

aij=a，j≠i,i=1,2,…,n,j=1,2,…,n,

bi=b，i=1,2,…,n。

根据约束函数的构成方式,只需证方程组

(9)

即

(10)

有解。

因为00,且

即

易知式(10)有解

证毕。

构造动约束函数如下

(11)

t=1时围成区域(圆形区域)如图3所示。

图3 t=1时围成区域(圆形区域)

在2维情形有如下边界正独立性结论:

1)当t=0时,由假设条件1知原可行域满足正独立性。

(12)

由x1>0可知，

xg1(x,t)≠0,

(13)

所以,当#I(x,t)=1时,正独立性成立。

若#I(x,t)=2,不妨设I(x,t)={1，2};若存在vi>0,i=1,2给出证明。由式(11)得到

v1

(14)

往证,当且仅当v1=0,v2=0时,有

v1

成立,利用反证法,即证明v1,v2不全为零。由类似定理2取a12=a,a21=a,x1=x2且x1,x2均非零,则

v1((1-t)+2tx1)+v2((1-t)(-2ax1)+2tx1)=0,

v1((1-t)(-2ax1)+2tx1)+v2((1-t)+2tx1)=0,

(15)

因此v1=v2,若

(1-t)+2tx1+(1-t)(-2ax1)+2tx1=0,

(16)

由式(16)解得

(17)

3)当t=1时,若vi≠0,则必有

故满足正独立性。

综上所述,当t∈[0,1]时,可行域满足正独立性。

在n维情形给出如下定理。

成立,则必有

vi=0，i∈I(x,t)。

证明

3)由定理2可知,Ω=Ω(0)是连通有界闭集,Ω(1)是连通有界闭凸集,对任意给定的t∈[0,1],由动约束函数构造方法可知Ω(0)⊂Ω(t)⊂Ω(1),因此Ω(t)为有界连通闭集。满足假设条件(B3);

4)由定理4可知，对任意给定的t∈[0,1],满足动边界正独立性,即满足假设条件(B4);

成立,从而满足假设条件(B5)。

证毕。

例:解如下非凸规划问题

构造动约束函数如下:

求解非凸规划问题路径跟踪时区域的变化过程曲线形状如图4所示。

(a) 当t=1时约束区域Ω(1)

3 结 语

对一类典型多尖非凸区域上的非凸规划问题给出了动约束函数的构造方法,并在假设条件下证明了动可行域的有界性以及边界正独立性,数值算例表明构造方法的有效性和可行性,从而进一步扩大了CSCH方法求解非凸规划的范围，将动约束函数的构造方法推广到一般的非凸区域是后续的研究工作。