孫文娟，申愛紅，劉 芳

(1.沈陽理工大學 理學院，沈陽 110159；2.中國刑事警察學院 基礎部，沈陽 110854 )

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

孫文娟1，申愛紅2，劉 芳1

(1.沈陽理工大學 理學院，沈陽 110159；2.中國刑事警察學院 基礎部，沈陽 110854 )

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

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

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

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

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

1 基本概念

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

minf(x)

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

(1)

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

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

Yg(x)=0,

y≥0,g(x)≤0

(2)

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

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

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

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

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

H(t,ω)=

(3)

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

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

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

假設條件：

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

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

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

構(gòu)造同倫方程

(4)

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

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

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]設x*是K-K-T點，則對在x*點的每一個可行方向d,有

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

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

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

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

故在點x*處無可行下降方向，x*一定是局部極小點。

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

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

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

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

4 結(jié)論

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

[1]王宇.計算機優(yōu)化同倫內(nèi)點法[M].大連：大連理工大學出版社，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)點法中的應用[D].長春：吉林大學，2001.

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

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

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

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

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

(責任編輯：馬金發(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

遼寧省教育廳科學技術研究項目(LG201615)

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

1003-1251(2017)04-0102-03

O221

A