一類非凸規(guī)劃K-K-T點(diǎn)的性質(zhì)及同倫方法收斂定理

孫文娟，申愛(ài)紅，劉 芳

(1.沈陽(yáng)理工大學(xué) 理學(xué)院，沈陽(yáng) 110159；2.中國(guó)刑事警察學(xué)院 基礎(chǔ)部，沈陽(yáng) 110854 )

一類非凸規(guī)劃K-K-T點(diǎn)的性質(zhì)及同倫方法收斂定理

孫文娟1，申愛(ài)紅2，劉 芳1

(1.沈陽(yáng)理工大學(xué) 理學(xué)院，沈陽(yáng) 110159；2.中國(guó)刑事警察學(xué)院 基礎(chǔ)部，沈陽(yáng) 110854 )

對(duì)于目標(biāo)函數(shù)為凸的一類非凸規(guī)劃，證明了其K-K-T點(diǎn)一定是局部極小點(diǎn)。在求解此類非凸規(guī)劃時(shí)，基于可行域滿足較法錐條件更弱的擬法錐、弱擬法錐等條件下，同倫方法得到的K-K-T點(diǎn)一定是局部極小點(diǎn)。對(duì)于一般非凸規(guī)劃問(wèn)題，證明了邊界上的K-K-T點(diǎn)如果不是駐點(diǎn)，則一定是局部極小點(diǎn)。

非凸規(guī)劃；K-K-T點(diǎn)；同倫方法；局部極小

應(yīng)用同倫方法求解優(yōu)化問(wèn)題，最早見(jiàn)于1979年Garcia和Zangwill的工作，他們利用同倫方法求解凸規(guī)劃，并證明了在一定條件下該方法是大范圍收斂的。目前，同倫方法用于求解各種凸規(guī)劃問(wèn)題[1]的理論與算法已基本完善，而用于求解非凸規(guī)劃問(wèn)題的理論與算法還有待進(jìn)一步研究。

自馮國(guó)忱等[2]提出了組合同倫內(nèi)點(diǎn)法求解非凸規(guī)劃問(wèn)題之后，具有大范圍收斂性的同倫方法，受到了諸多學(xué)者的重視，并成為非凸規(guī)劃問(wèn)題求解方法的研究熱點(diǎn)之一。但利用同倫方法求解的非凸規(guī)劃，可行域必須滿足法錐條件，初始點(diǎn)也必須是內(nèi)點(diǎn)，大大削弱了同倫方法的實(shí)用性。近二十年來(lái)，很多學(xué)者致力于研究如何減弱可行域所滿足的條件及對(duì)初始點(diǎn)的限制條件，并取得了一定的成果[3-6]。

由于同倫方法求得的只是優(yōu)化問(wèn)題的K-K-T點(diǎn)，對(duì)于凸規(guī)劃問(wèn)題，K-K-T點(diǎn)即為最優(yōu)解，但對(duì)于非凸規(guī)劃問(wèn)題，結(jié)論不一定成立。而就目前對(duì)非凸規(guī)劃問(wèn)題的研究來(lái)看，所有的實(shí)際數(shù)值算例顯示，同倫算法所收斂到的K-K-T點(diǎn)絕大多數(shù)就是優(yōu)化問(wèn)題的最優(yōu)解或局部極小解。此結(jié)果是否是同倫算法本身所具備的收斂性質(zhì)，還是和初始點(diǎn)的選取有關(guān)，或是和算例中的所選優(yōu)化問(wèn)題的特殊性有關(guān)，目前相應(yīng)理論還不完善。孫文娟等人[7-9 ]只是得到了在非凸區(qū)域滿足法錐條件、同倫映射為正則映射的條件下，構(gòu)造合適的同倫方程，可以收斂到局部極小解。本文在此基礎(chǔ)上，針對(duì)目標(biāo)函數(shù)為凸的一類非凸規(guī)劃問(wèn)題，研究其K-K-T點(diǎn)的性質(zhì)，得到了可行域在滿足較法錐條件更弱的條件下，同倫算法求解此類非凸規(guī)劃的收斂定理，推廣了文獻(xiàn)[9]的結(jié)果。

1 基本概念

考慮非凸規(guī)劃(NCP)問(wèn)題

minf(x)

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

(1)

式中：x∈Rn；f(x)、gi(x)(i=1,2,…,m)為二階連續(xù)可微函數(shù)(不必凸)。

設(shè)Ω={x∈Rn:gi(x)≤0,i∈{1,2,…,m}}為(NCP)的可行域，Ω0={x∈Rn:gi(x)<0,i∈{1,2,…,m}}為(NCP)的嚴(yán)格可行域，?Ω=ΩΩ0為Ω的邊界集，I(x)={i∈{1,2,…,m}:gi(x)=0}為在x點(diǎn)的緊指標(biāo)集。

Yg(x)=0,

y≥0,g(x)≤0

(2)

式中Y=diag(y)。系統(tǒng)(2)稱為問(wèn)題(1)的K-K-T系統(tǒng)或一階必要條件。如果點(diǎn)(x*,y*)滿足式(2)，那么稱x*為問(wèn)題(1)的K-K-T點(diǎn)，y*為L(zhǎng)agrange乘子。如果f,gi是凸函數(shù)，那么K-K-T點(diǎn)就是問(wèn)題(1)的最優(yōu)解。

定義2設(shè)Ω為非空子集，x*∈Ω。非零向量d∈Rn稱為在x*處的可行方向，若存在δ>0使得

x*+αd∈Ω,其中α∈(0,δ)。

2 求解不同非凸區(qū)域的同倫方法

馮國(guó)忱等[2]提出了可行域Ω滿足法錐條件，即x∈?Ω有

H(t,ω)=

(3)

劉慶懷等[5-6]研究了在較法錐條件更弱的擬法錐條件及弱擬法錐條件下，通過(guò)定義正獨(dú)立映射，構(gòu)造修正的組合同倫方程，進(jìn)一步拓寬了同倫方法求解非凸規(guī)劃的范圍。

所謂Ω滿足擬法錐條件是指：若存在關(guān)于g(x)正獨(dú)立光滑映射ηi(x)(i=1,2,…,m)，且滿足?x∈?Ω,有?。Ω滿足弱擬法錐條件是指：存在?Ω0,?x∈?Ω,滿足?。

顯然若Ω滿足法錐條件或擬法錐條件，則一定滿足弱擬法錐條件，但反之不然。

假設(shè)條件：

(1)Ω為連通、有界閉集，Ω0非空；

(2) 任意x∈?Ω,ηi(x)(i=1,2,…,m)關(guān)于g(x)關(guān)于是正獨(dú)立的。

(3)Ω關(guān)于ηi(x)(i=1,2,…,m)滿足弱擬法錐條件。

構(gòu)造同倫方程

(4)

3 一類非凸規(guī)劃的K-K-T點(diǎn)性質(zhì)及同倫方法收斂定理

考慮非凸規(guī)劃問(wèn)題

minf(x)

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

(5)

式中：x∈Rn；f(x)為二階連續(xù)可微凸函數(shù)；gi(x)(i=1,2,…,m)為二階連續(xù)可微函數(shù)(不必凸)。

引理1[9]設(shè)x*是K-K-T點(diǎn)，則對(duì)在x*點(diǎn)的每一個(gè)可行方向d,有

dTgi(x*)≤0,i∈I(x*)

定理2若x*是K-K-T點(diǎn)，則x*一定是問(wèn)題(5)的局部極小點(diǎn)。

證明1) 若x*∈Ω0，由于f(x)為凸函數(shù)，顯然x*為局部極小點(diǎn)。

2) 若x*∈?Ω，則I(x*)≠?。

故在點(diǎn)x*處無(wú)可行下降方向，x*一定是局部極小點(diǎn)。

綜上所述，若x*是K-K-T點(diǎn)，x*是問(wèn)題(5)的局部極小點(diǎn)。

由定理2及其證明，易得如下定理。

定理3對(duì)于一般非凸規(guī)劃問(wèn)題(1)，K-K-T點(diǎn)x*若在區(qū)域邊界上，且不為駐點(diǎn)(即f(x*)≠0)，則x*一定是局部極小點(diǎn)。

定理4對(duì)于問(wèn)題(5)，在可行域滿足更弱(擬法錐、弱擬法錐等)條件下，構(gòu)造修正同倫方程，同倫方法得到的K-K-T點(diǎn)都是局部極小點(diǎn)。

4 結(jié)論

研究了對(duì)于目標(biāo)函數(shù)為凸的一類非凸規(guī)劃問(wèn)題K-K-T點(diǎn)的性質(zhì)，并得到了同倫方法的收斂性定理。證明了這類非凸規(guī)劃問(wèn)題，K-K-T點(diǎn)一定是問(wèn)題的局部極小點(diǎn)，因此在用同倫方法求解此類非凸規(guī)劃時(shí)，當(dāng)可行域在更弱(擬法錐、弱擬法錐等)條件下，只要同倫路徑存在并且收斂到K-K-T點(diǎn)，那么該收斂點(diǎn)一定是局部極小點(diǎn)，從而推廣了文獻(xiàn)[9]的結(jié)果。而對(duì)于目標(biāo)函數(shù)非凸的非凸規(guī)劃問(wèn)題，一些數(shù)值算例顯示，在比正則映射更弱的條件下，可行域滿足較法錐條件更弱條件時(shí)，也能收斂到局部極小點(diǎn)，但沒(méi)有相應(yīng)的理論依據(jù)，這將是今后的研究方向。

[1]王宇.計(jì)算機(jī)優(yōu)化同倫內(nèi)點(diǎn)法[M].大連：大連理工大學(xué)出版社，1991.

[2]FENG Guochen,LIN Zhenghua,YU Bo.Existence of interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem [J].Nonlinear Analysis,Theory,Methods and Applications,1998,32(6)：761-768.

[3]YU Bo,FENG Guochen,ZHANG Shaoliang.The aggregate constraint homotopy method for nonconvex nonlinear programming[J].Nonlinear Analysis,Theory,Methods &Applications,2001(45):839-847.

[4]商玉鳳.馬蹄形非凸區(qū)域上的偽錐構(gòu)造及其在同倫內(nèi)點(diǎn)法中的應(yīng)用[D].長(zhǎng)春：吉林大學(xué)，2001.

[5]劉慶懷，于波，馮國(guó)忱.基于擬法錐條件的非凸非線性規(guī)劃問(wèn)題的同倫內(nèi)點(diǎn)法[J].應(yīng)用數(shù)學(xué)學(xué)報(bào)，2003，26(2)：371-377.

[6]劉慶懷，張春陽(yáng)，張樹(shù)功.弱擬法錐條件下非凸優(yōu)化問(wèn)題的同倫算法[J].應(yīng)用數(shù)學(xué)學(xué)報(bào)，2011，34(6)：996-1006.

[7]孫文娟，李忠范，王彩玲,等.同倫方法求解無(wú)約束非凸優(yōu)化問(wèn)題的局部極小[J].東北師大學(xué)報(bào)：自然科學(xué)版,2009,41(3):17-20.

[8]孫文娟，王彩玲.同倫方法求解無(wú)界域上非凸規(guī)劃問(wèn)題的收斂性定理[J].應(yīng)用數(shù)學(xué)，2012,25(4):732-737.

[9]孫文娟，趙巍巍.同倫方法求解一類非凸規(guī)劃問(wèn)題的新的收斂性定理[J].沈陽(yáng)理工大學(xué)學(xué)報(bào)，2014，33(3)：32-34.

(責(zé)任編輯：馬金發(fā))

PropertyoftheK-K-TPointandConvergenceTheoremofHomotopyMethodforaClassofNonconvexProgramming

SUN Wenjuan1，SHEN Aihong2，LIU Fang1

(1.Shenyang Ligong University,Shenyang 110159,China；2.Foundation department,National Police University of China,Shenyang 110854,China)

It is proved that,the K-K-T point of a class of nonconvex programming problem,objective function of which is convex,is a local minimum.For this nonconvex programming problem under the quasi-normal cone condition or the weak quasi-normal cone condition,which are weaker than normal,cone condition the K-K-T point got by homotopy method must be a local minimum.It is also proved that,for general nonconvex programming problem,if the K-K-T point on the boundary is not a stationary point,it must be a local minimum.Keywordsnonconvex programming;K-K-T point;homotopy method;local minimum

2016-09-20

遼寧省教育廳科學(xué)技術(shù)研究項(xiàng)目(LG201615)

孫文娟(1982—)，女，講師，研究方向：最優(yōu)化理論與算法;通訊作者：劉芳(1979—)，女，講師，研究方向：應(yīng)用數(shù)學(xué)。

1003-1251(2017)04-0102-03

O221

A