單洞非凸域上優(yōu)化問(wèn)題的區(qū)域分割方法

劉傲多， 劉慶懷， 商玉鳳

(1.長(zhǎng)春工業(yè)大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 吉林 長(zhǎng)春 130012；2.長(zhǎng)春財(cái)經(jīng)學(xué)院經(jīng)濟(jì)學(xué)院， 吉林 長(zhǎng)春 130122)

0 引 言

1984年，Karmarkar[1]提出的內(nèi)點(diǎn)法求解線(xiàn)性規(guī)劃問(wèn)題被發(fā)現(xiàn)實(shí)質(zhì)上是一種內(nèi)點(diǎn)同倫算法。自此，許多學(xué)者對(duì)非線(xiàn)性?xún)?yōu)化問(wèn)題進(jìn)行了大量研究。凸優(yōu)化問(wèn)題在解存在的條件下，利用組合同倫法可以得到問(wèn)題的最優(yōu)解。相比之下，非凸優(yōu)化問(wèn)題更難解決，求解非凸優(yōu)化問(wèn)題成為人們研究的一個(gè)熱點(diǎn)問(wèn)題。1993年，F(xiàn)eng G C等[2]為研究非凸優(yōu)化的整體求解問(wèn)題提出了基于牛頓同倫和不動(dòng)點(diǎn)同倫的組合同倫內(nèi)點(diǎn)法(Combined Homotopy Interior Point Method， CHIP)，并證明了當(dāng)求解區(qū)域滿(mǎn)足“外法錐條件”時(shí)，CHIP方法具有大范圍收斂性。法錐條件是對(duì)非凸可行域邊界的刻畫(huà)條件，凸可行域一定滿(mǎn)足法錐條件。文獻(xiàn)[3]給出了既有不等式約束,又有等式約束的非線(xiàn)性?xún)?yōu)化問(wèn)題的組合同倫方法。其后，對(duì)法錐條件進(jìn)行減弱。文獻(xiàn)[4-5]提出了凝聚約束同倫方法，可以求解可行域，如星星區(qū)域的非凸優(yōu)化問(wèn)題。文獻(xiàn)[6-7]定義了正獨(dú)立映射，發(fā)現(xiàn)了擬法錐條件，并給出了修正的組合同倫方程。文獻(xiàn)[8]進(jìn)一步削弱了約束區(qū)域的限制條件，定義了弱法錐條件，并證明了同倫路徑的存在性和收斂性。文獻(xiàn)[9-10]給出動(dòng)邊界同倫方程，初始點(diǎn)的選取不要求在可行域內(nèi)部。文獻(xiàn)[11]利用F-B函數(shù)建立了邊界滿(mǎn)足法錐條件時(shí)非凸非線(xiàn)性?xún)?yōu)化問(wèn)題的同倫方程。

1 單洞非凸域的分割

考慮單洞非凸域上非凸優(yōu)化問(wèn)題

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ù)可微函數(shù)，Ω={x|p(x)≤0,q(x)≤0}為可行域，Ω0={x|p(x)<0,q(x)<0}為嚴(yán)格可行域，?Ω=ΩΩ0為可行域邊界，Ωp={x|p(x)≥0}，Ωq={x|q(x)≤0}，Ωp?Ωq且Ωq∩Ωp=φ,如圖1所示。

原問(wèn)題的KKT系統(tǒng)

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

假設(shè)Ω為有界連通集且Ω0非空。

為求解單洞非凸域上的非凸優(yōu)化問(wèn)題，文中提出了單洞非凸域上優(yōu)化問(wèn)題的區(qū)域分割方法，將單洞可行域分割成兩個(gè)滿(mǎn)足法錐條件的可行域，則原問(wèn)題分為Ⅰ、Ⅱ兩個(gè)分別滿(mǎn)足法錐條件的問(wèn)題。通過(guò)法錐條件下組合同倫方法分別求解Ⅰ、Ⅱ兩個(gè)問(wèn)題的KKT點(diǎn)，從而得到原問(wèn)題的KKT點(diǎn)。區(qū)域分割方法只需利用已有的組合同倫方法對(duì)問(wèn)題進(jìn)行求解，不需要重新構(gòu)造組合同倫方程。

顯然單洞非凸域Ω不滿(mǎn)足法錐條件，將可行域Ω用g(x)=0分成Ω1和Ω2兩個(gè)分別滿(mǎn)足法錐條件的區(qū)域。其中，g(x)=0為經(jīng)過(guò)Ωp球心的超平面，則原問(wèn)題被分成Ⅰ、Ⅱ兩個(gè)獨(dú)立且可行域分別為Ω1和Ω2的問(wèn)題。

問(wèn)題Ⅰ

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,

問(wèn)題Ⅰ的KKT系統(tǒng)

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

問(wèn)題Ⅱ

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,

問(wèn)題Ⅱ 的KKT系統(tǒng)

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

2 子問(wèn)題與原問(wèn)題的關(guān)系

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

證明 由x∈S1，有x滿(mǎn)足KKT系統(tǒng)

即x∈S。

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

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

證明 若x∈S1∩S2，則x滿(mǎn)足KKT系統(tǒng)

且x滿(mǎn)足KKT系統(tǒng)

則有

g(x)=

g(x)=0

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

對(duì)?x∈?Ω1(或?x∈?Ω2)，p(x)，q(x)和g(x)正獨(dú)立，有

即x∈S。

定理3設(shè)x∈S1(或x∈S2)，若x?S1∩S2且g(x)=0，則x?S。

證明 若x∈S，則x滿(mǎn)足KKT系統(tǒng)

因?yàn)閤∈S1，所以x滿(mǎn)足KKT系統(tǒng)

則有

g2(x)=

g(x),

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

對(duì)?x∈?Ω1，p(x)，q(x)和g(x)正獨(dú)立，有

x∈S1，?y(1)使得(x,y(1))滿(mǎn)足KKT系統(tǒng)

即x∈S2。

與x?S1∩S2矛盾,所以x?S。

同理，對(duì)?x∈S2，若x?S1∩S2且g(x)=0，則x?S。

3 結(jié) 語(yǔ)

單洞非凸域不滿(mǎn)足法錐條件及廣義法錐條件，利用法錐條件下的組合同倫方法對(duì)單洞非凸域上優(yōu)化問(wèn)題進(jìn)行研究，提出了單洞非凸域上的區(qū)域分割方法。將單洞非凸域分割成兩個(gè)相對(duì)獨(dú)立且分別滿(mǎn)足法錐條件的可行域，利用法錐條件下的組合同倫方法分別求解分割后的非凸優(yōu)化問(wèn)題，從而得到原問(wèn)題的解。區(qū)域分割方法能夠解決一類(lèi)更復(fù)雜的約束優(yōu)化問(wèn)題，進(jìn)一步擴(kuò)大了組合同倫方法的應(yīng)用范圍，求解多洞非凸域上優(yōu)化問(wèn)題是下一步要研究的工作。