单洞非凸域上优化问题的区域分割方法

刘傲多， 刘庆怀， 商玉凤

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

0 引 言

1984年，Karmarkar[1]提出的内点法求解线性规划问题被发现实质上是一种内点同伦算法。自此，许多学者对非线性优化问题进行了大量研究。凸优化问题在解存在的条件下，利用组合同伦法可以得到问题的最优解。相比之下，非凸优化问题更难解决，求解非凸优化问题成为人们研究的一个热点问题。1993年，Feng G C等[2]为研究非凸优化的整体求解问题提出了基于牛顿同伦和不动点同伦的组合同伦内点法(Combined Homotopy Interior Point Method， CHIP)，并证明了当求解区域满足“外法锥条件”时，CHIP方法具有大范围收敛性。法锥条件是对非凸可行域边界的刻画条件，凸可行域一定满足法锥条件。文献[3]给出了既有不等式约束,又有等式约束的非线性优化问题的组合同伦方法。其后，对法锥条件进行减弱。文献[4-5]提出了凝聚约束同伦方法，可以求解可行域，如星星区域的非凸优化问题。文献[6-7]定义了正独立映射，发现了拟法锥条件，并给出了修正的组合同伦方程。文献[8]进一步削弱了约束区域的限制条件，定义了弱法锥条件，并证明了同伦路径的存在性和收敛性。文献[9-10]给出动边界同伦方程，初始点的选取不要求在可行域内部。文献[11]利用F-B函数建立了边界满足法锥条件时非凸非线性优化问题的同伦方程。

1 单洞非凸域的分割

考虑单洞非凸域上非凸优化问题

minf(x),

s.t.p(x)=α2-(x-a)T(x-a)≤0,

q(x)=(x-b)T(x-b)-β2≤0,

其中，x∈Rn，a∈Rn，b∈Rn，f是连续可微函数，Ω={x|p(x)≤0,q(x)≤0}为可行域，Ω0={x|p(x)<0,q(x)<0}为严格可行域，∂Ω=ΩΩ0为可行域边界，Ωp={x|p(x)≥0}，Ωq={x|q(x)≤0}，Ωp⊂Ωq且Ωq∩Ωp=φ,如图1所示。

原问题的KKT系统

其中，y=(y1,y2)T，y≥0。

假设Ω为有界连通集且Ω0非空。

为求解单洞非凸域上的非凸优化问题，文中提出了单洞非凸域上优化问题的区域分割方法，将单洞可行域分割成两个满足法锥条件的可行域，则原问题分为Ⅰ、Ⅱ两个分别满足法锥条件的问题。通过法锥条件下组合同伦方法分别求解Ⅰ、Ⅱ两个问题的KKT点，从而得到原问题的KKT点。区域分割方法只需利用已有的组合同伦方法对问题进行求解，不需要重新构造组合同伦方程。

显然单洞非凸域Ω不满足法锥条件，将可行域Ω用g(x)=0分成Ω1和Ω2两个分别满足法锥条件的区域。其中，g(x)=0为经过Ωp球心的超平面，则原问题被分成Ⅰ、Ⅱ两个独立且可行域分别为Ω1和Ω2的问题。

问题Ⅰ

minf(x),

s.t.p(x)=α2-(x-a)T(x-a)≤0,

q(x)=(x-b)T(x-b)-β2≤0,

-g(x)≤0,

问题Ⅰ的KKT系统

其中，y=(y1,y2,y3)T，y≥0。

问题Ⅱ

minf(x),

s.t.p(x)=α2-(x-a)T(x-a)≤0,

q(x)=(x-b)T(x-b)-β2≤0,

g(x)≤0,

问题Ⅱ 的KKT系统

其中，y=(y1,y2,y3)T，y≥0。

2 子问题与原问题的关系

定理1若x∈S1(或x∈S2)且g(x)>0(或g(x)<0)，则x∈S。

证明 由x∈S1，有x满足KKT系统

即x∈S。

同理，若x∈S2且g(x)<0，则x∈S。

定理2若x∈S1∩S2，则x∈S。

证明 若x∈S1∩S2，则x满足KKT系统

且x满足KKT系统

则有

g(x)=

g(x)=0

Ap(x)+Bq(x)+Cg(x)=0

对∀x∈∂Ω1(或∀x∈∂Ω2)，p(x)，q(x)和g(x)正独立，有

即x∈S。

定理3设x∈S1(或x∈S2)，若x∉S1∩S2且g(x)=0，则x∉S。

证明 若x∈S，则x满足KKT系统

因为x∈S1，所以x满足KKT系统

则有

g2(x)=

g(x),

Dp(x)+Eg(x)=0，

对∀x∈∂Ω1，p(x)，q(x)和g(x)正独立，有

x∈S1，∃y(1)使得(x,y(1))满足KKT系统

即x∈S2。

与x∉S1∩S2矛盾,所以x∉S。

同理，对∀x∈S2，若x∉S1∩S2且g(x)=0，则x∉S。

3 结 语

单洞非凸域不满足法锥条件及广义法锥条件，利用法锥条件下的组合同伦方法对单洞非凸域上优化问题进行研究，提出了单洞非凸域上的区域分割方法。将单洞非凸域分割成两个相对独立且分别满足法锥条件的可行域，利用法锥条件下的组合同伦方法分别求解分割后的非凸优化问题，从而得到原问题的解。区域分割方法能够解决一类更复杂的约束优化问题，进一步扩大了组合同伦方法的应用范围，求解多洞非凸域上优化问题是下一步要研究的工作。