解一类带洞非凸域上函数极值的动约束同伦算法

商玉凤，党 杨，吴 睿，刘庆怀

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

0 引言

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

minf(x)，
s.t.p(x)≤0，
q(x)≥0.

(1)

其中：f：Rn→R，p：Rn→R，q：Rn→R.易知问题(1)的KKT系统为

(2)

在已有的利用组合同伦方法求解非凸规划问题中，从几何上看一般需要满足法锥、拟法锥、伪锥等条件[1-3]，而带洞非凸区域不满足这些条件.文献[4]给出了动约束组合同伦算法，通过构造动约束使其满足法锥条件，扩大了应用范围，但没有给出构造约束函数的方法.文献[5-6]应用动约束同伦方法讨论了不动点问题以及非光滑非凸规划问题.本文针对带洞非凸区域上的优化问题给出了一个新的同伦方程，利用该方程求解非凸规划问题可以发现随着同伦参数的变化，约束区域由一个有界凸区域变为有界非凸区域，由于初始区域为凸区域因而不需要验证法锥条件，并证明了路径的存在性与收敛性，通过算例表明该方法是有效的.

1 基本假设

图1 带洞非凸区域示例图

非空凸区域与边界的正独立性具有下面性质：

这里Ip(x)={i|pi(x)=0}.

对给定x(0)∈Rn，t∈[0，1]，定义参数函数P(x，x(0)，t)以及Q(x，t)如下：

P(x，x(0)，t)=p(x)-tΘ(p(x(0))+em)，Q(x，t)=tel+(1-t)q(x).

(3)

其中：

记：

Ω(x(0)，t)={x|P(x，x(0)，t)≤0，Q(x，t)≥0}；

ΩP(x(0)，t)={x|P(x，x(0)，t)≤0}；

ΩQ(t)={x|Q(x，t)≥0}；

∂Ω(x(0)，t)=Ω(x(0)，t)Ω0(x(0)，t)；

I(x，x(0)，t)={i|pi(x)-tθi(pi(x(0))+1)=0}；

J(x，t)={j|t+(1-t)qj(x)=0}.

由(3)式P(x，x(0)，t)及Q(x，t)的定义可以得到如下引理：

引理2设p：Rn→Rn，q：Rn→Rl均为凸向量值函数，Ω为带洞非凸域.则当t∈[0，1]时有：

Ω=Ω(x(0)，0)⊂Ω(x(0)，t)⊂Ω(x(0)，1)；

ΩP(x(0)，0)⊂ΩP(x(0)，t)⊂ΩP(x(0)，1)；

ΩQ(0)⊂ΩQ(t)⊂ΩQ(1)；

∂ΩP(x(0)，t)∩∂ΩQ(t)=∅.

考虑含参数t的优化问题

minf(x)，
s.t.P(x，x(0)，t)≤0，
Q(x，t)≥0.

(4)

问题(4)的KKT系统为

(5)

为求解系统(5)，构造组合同伦映射H(x，y，z，t)为

(6)

当t=1时，同伦方程H(x，y，z，1)=0，从而

x-x(0)=0，YP(x，x(0)，1)-Y(0)P(x(0)，x(0)，1)=0，Zel-Z(0)el=0，

此时方程H(x，y，z，1)=0有唯一的解x=x(0)，Y=Y(0)，Z=Z(0).

当t=0时，同伦方程H(x，y，z，0)=0，即

此时方程H(x，y，z，0)=0的解即为KKT系统(2)的解.

2 同伦路径存在性与收敛性

假设1p∈Cr：Rn→Rm，q∈Cr：Rn→Rl(r>2)均为凸向量值函数.

假设2Ω={x|p(x)≤0，q(x)≥0}为内部非空有界带洞非凸域.

其中En为n维单位矩阵.由Θ的定义，得到

(7)

Y(k)P(x(k)，x(0)，tk)-tkY(0)P(x(0)，x(0)，1)=0；

(8)

Z(k)Q(x(k)，tk)-tkZ(0)el=0.

(9)

下面证明有且仅有情况(ⅵ)发生，情况(ⅰ)—(ⅴ)都是不可能发生的.

(a) 当t*=1，k→+∞时，由方程(9)知，必有‖z(k)‖+∞.若存在则由方程(8)必有i∈I(x*，x(0)，t*).改写(7)式为

(10)

(11)

(12)

而对(11)式右端乘(x(0)-x*)T得到(x(0)-x*)T(x(0)-x*)≥0，这是不可能的，因此‖y*‖+∞，情况(ⅰ)不能发生.

(13)

则必有

‖λ‖=1，λ1≥0，i∈I(x*，x(0)，t*)，

由引理1可知所有λi=0(i∈I(x*，x(0),t*)),这是不可能的.

(14)

容易看到

‖μ‖=1，μj≥0，j∈J(x*，t*).

由假设条件3可知μj=0(j∈J(x*，t*))，这与‖μ‖=1矛盾，因此z*必为有限值，情况(ⅱ)不可能发生.

(c) 由方程(8)和(9)可以看到情况(ⅲ)与(ⅳ)不可能发生，由0是H(w，t)的正则值，情况(ⅴ)是不可能的.

3 数值算例

本文采用标准的预估-校正同伦方法跟踪同伦路径，编写了Matlab程序.算例中初始点x(0)利用随机数产生，取y(0)=(1，…，1)T，迭代运算终止原则为tk<10-12以及‖H(w(0)，w(k)，tk)‖<10-10，具体结果如下.

例1解R2上非凸优化问题：

本问题的最优解为x*=(1.275 3，-1.478 8)T，目标值为f(x*)=-17.855 7.利用随机函数产生的4个初始点分别是x1(0)=(-0.174 1，-1.926 0)T，x2(0)=(1.741 9，1.667 6)T，x3(0)=(-0.219 6，1.713 1)T，x4(0)=(-0.636 0，-0.625 4)T.注意到这里x1(0)∉Ω，x2(0)∉Ω，x3(0)∈Ω，以及x4(0)∉Ω，沿着每一个初始点都可以到达最优解点x*.图2给出了当t从1变到0时，初始点x(0)沿同伦曲线Γ变到解点x*的变化路径.

图2 例1同伦路径x1-x2曲线图

例2解R3上非凸优化问题：

本问题有2个KKT点分别为(x1*，y1*)=(-2.778 2，5.988 4，4.534 4，0.439 8)T，(x2*，y2*)=(-3.166 3，2.603 4，-8.741 8，0.263 3)T；相应的函数值为f(x1*)=-40.522 1，f(x2*)=-11.926 6.利用随机函数产生了4个初始点，分别为x1(0)=(-0.870 6，-9.629 9，6.428 1)T，x2(0)=(-1.105 9，2.308 6，5.838 7)T，x3(0)=(-8.347 7，6.414 3，-6.139 6)T，x4(0)=(2.280 4，7.826 0，5.241 9)T.注意到x1(0)∉Ω，x2(0)∈Ω，x3(0)∉Ω，以及x4(0)∉Ω.图3给出了当t从1变到0时，初始点x(0)沿同伦曲线Γ变到解点x*的变化路径，分别表示t-x1，t-x2，t-x3曲线图.

图3 例2解的路径t-x1，t-x2，t-x3曲线图