同倫方法求解一類(lèi)非凸規(guī)劃問(wèn)題的新的收斂性定理

孫文娟，趙巍巍

(1.沈陽(yáng)理工大學(xué) 理學(xué)院，遼寧 沈陽(yáng) 110159；2.吉林機(jī)械交通高級(jí)技工學(xué)校 教務(wù)科，吉林 吉林 132011)

同倫方法是20世紀(jì)70年代發(fā)展起來(lái)的一種求解非凸規(guī)劃問(wèn)題的大范圍收斂方法。在數(shù)學(xué)規(guī)劃、不動(dòng)點(diǎn)計(jì)算、代數(shù)方程組求解等方面都有廣泛應(yīng)用。近年來(lái)，同倫方法的基本理論和應(yīng)用也獲得了極大的發(fā)展[1-5]。

同倫方法只能求得問(wèn)題的K-K-T點(diǎn)，而人們更關(guān)心的是全局最優(yōu)解或局部最優(yōu)解?；谶@一點(diǎn)，孫文娟等人[6-8]研究了在同倫映射為正則映射的條件下，同倫方法收斂到的K-K-T點(diǎn)的性質(zhì)。文獻(xiàn)[6]在同倫映射為正則映射的條件下，證明了同倫方法求解目標(biāo)函數(shù)為凸的一類(lèi)非凸規(guī)劃時(shí)，得到的K-K-T點(diǎn)一定是局部極小解。而正則映射是一個(gè)較強(qiáng)的條件，很多算例顯示，即使在不滿足正則映射的條件下，同倫方法也能收斂到局部最優(yōu)解，但目前理論上卻沒(méi)有相應(yīng)的結(jié)論。本文研究對(duì)于目標(biāo)函數(shù)為凸的一類(lèi)非凸規(guī)劃問(wèn)題，如何在更弱的條件下判別出收斂點(diǎn)的類(lèi)型，得到了同倫方法的一個(gè)新的收斂性定理，推廣了文獻(xiàn)[6]的結(jié)果。

1 預(yù)備知識(shí)

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

minf(x)

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

(1)

式中：x∈Rn；f(x)為充分光滑凸函數(shù);gi(x)(i=1,2,…,m)為充分光滑函數(shù)(不必凸)。

定義1 (K-K-T條件)若點(diǎn)(x,y)滿足方程

(2)

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

為了方便，引入以下記號(hào)：

Ω={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)集。

對(duì)K-K-T系統(tǒng)(2)構(gòu)造組合內(nèi)點(diǎn)同倫方程:

H(t,ω)=

(3)

本文的基本假設(shè)如下：

假設(shè)1

(1)f(x)為充分光滑凸函數(shù)，gi(x)(i=1,2,…,m)為充分光滑函數(shù)；

(2)Ω0非空(Slater條件)有界；

(3){▽gi(x),i∈I(x)}為列滿秩矩陣(約束正則性條件)；

2 同倫方法的收斂性質(zhì)

引理1 若H(t,ω)由式(3)定義，則

證明： 將式(3)中H(t,ω)分別對(duì)ω和t求導(dǎo)，易得引理1。

引理2 設(shè)x*是由同倫方法得到的K-K-T點(diǎn)，則對(duì)在x*點(diǎn)的每一個(gè)可行方向d,有

dT▽gi(x*)≤0,i∈I(x*)

證明對(duì)在x*點(diǎn)的每一個(gè)可行方向d,有

gi(x*+δd)-gi(x*)=δdT▽gi(x*)+o(δ2),i∈I(x*)

式中δ>0。若dT▽gi(x*)>0,i∈I(x*)成立，當(dāng)δ充分小時(shí)，則有

gi(x*+δd)-gi(x*)>0

因?yàn)間i(x*)=0,i∈I(x*)，故gi(x*+δd)>0，與d是x*點(diǎn)處的可行方向矛盾。

因此引理2成立。

定理2 若構(gòu)造同倫方程為(3)，且假設(shè)1成立，則由組合同倫內(nèi)點(diǎn)方法得到的K-K-T點(diǎn)x*是問(wèn)題(1)的局部極小點(diǎn)。

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

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

當(dāng)▽f(x*)=0時(shí)，顯然x*為局部極小點(diǎn)；當(dāng)▽f(x*)≠0時(shí)，對(duì)每一個(gè)可行方向d，由引理2及K-K-T方程，有

▽f(x*)Td=-y*T▽g(x*)Td≥0

故x*也一定是局部極小點(diǎn)。

綜上所述，由組合同倫內(nèi)點(diǎn)方法得到的K-K-T點(diǎn)x*是問(wèn)題(1)的局部極小點(diǎn)。

3 結(jié)論

研究了對(duì)于目標(biāo)函數(shù)為凸的一類(lèi)非凸規(guī)劃問(wèn)題，同倫方法的收斂性質(zhì)，得到了一個(gè)新的收斂性定理。證明了無(wú)論同倫映射是否為正則映射，同倫方法求解得到的K-K-T點(diǎn)都是問(wèn)題的局部極小點(diǎn)，推廣了文獻(xiàn)[6]的結(jié)果。而對(duì)于一般的非凸規(guī)劃問(wèn)題，能否在比正則映射更弱的條件下，研究收斂點(diǎn)的性質(zhì),判別出收斂點(diǎn)的類(lèi)型，將是今后的研究方向。

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

[2] YU Bo,WANG Yi.A new interior path following method for nonconvex nonlinear programming[J].Northeast.Math.J.,1997,13(3)：257-260.

[3] LIN Zhenghua,LI Yong.Homotopy method for solving variational ineaualities[J].Journal of Optimization Theory and Applications,1999,100(1)：207-218.

[4] XU Qing,YU Bo.Homotopy method for non-convex programming in unbounded set[J].Northeast.Math.J.,2005,21(1):25-31.

[5] 于波，商玉鳳.解非凸規(guī)劃問(wèn)題動(dòng)邊界組合同倫方法[J].數(shù)學(xué)研究與評(píng)論,2006,26(4)：831-834.

[6] 孫文娟，劉慶懷，王彩玲.同倫方法求解一類(lèi)非凸規(guī)劃問(wèn)題的局部極小[J].吉林大學(xué)學(xué)報(bào)(理學(xué)版),2008,46(3):469-471.

[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.