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

(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}为内部非空有界带洞非凸域.