正獨(dú)立映射的判定及其在非凸優(yōu)化中的應(yīng)用

張春陽， 張國霜， 李卓識，2， 劉慶懷*

（1.長春工業(yè)大學(xué)應(yīng)用數(shù)學(xué)所，吉林 長春 130012; 2.吉林農(nóng)業(yè)大學(xué)信息技術(shù)學(xué)院，吉林長春 130018）

0 引 言

對于非凸規(guī)劃，非凸可行域的邊界條件在“外法錐條件”或“擬法錐條件”下，文獻(xiàn)[1-5]構(gòu)造了組合同倫內(nèi)點(diǎn)算法具有大范圍收斂性。文獻(xiàn)[6]中定義了“正獨(dú)立映射”，發(fā)現(xiàn)了比法錐條件更弱的擬法錐條件，并給出了修正的組合同倫方程。文獻(xiàn)[7]給出了弱擬法錐條件定義，并證明在改條件下算法的收斂性。這些條件的發(fā)現(xiàn)拓寬了同倫方法求解非凸規(guī)劃問題的范圍。而在判定非凸區(qū)域的邊界滿足什么樣的條件時(shí)都與正獨(dú)立映射密切相關(guān)，如何判定正獨(dú)立映射，是實(shí)現(xiàn)該算法的重要環(huán)節(jié)，為此，給出正獨(dú)立映射的判定方法具有重要意義。

文中將就正獨(dú)立向量以及正獨(dú)立映射進(jìn)行系統(tǒng)的研究，給出其性質(zhì)及判定方法。

1 正獨(dú)立向量組與正獨(dú)立映射

記M={i=1，…，m}在整篇文章中都成立。

定義2 若映射ηi:Rn→Rn，i∈M，在x0∈Rn處滿足下邊條件:

若

必有

則稱η（x）=（η1（x），…，ηm（x））為 x0處的正獨(dú)立映射。

定義3 若η（x）在D?Rn上處處是正獨(dú)立的，則稱η（x）在D上是正獨(dú)立映射。

命題1 映射η（x）在 x0∈Rn處是正獨(dú)立映射的充分條件:

（1）當(dāng)m=n時(shí)，rank（η（x0））=n;

（2）當(dāng)m＜n時(shí)，rank（η（x0））=m。

其中

證明:（1）設(shè)

對于

同理可證（2）。

命題2 設(shè)向量組βi∈Rn，i∈M，若向量組βi，i∈M是線性獨(dú)立，則向量組βi，i∈M是正獨(dú)立的，即

該命題顯然成立。

性質(zhì):設(shè)光滑映射ηi:Rn→Rn，i∈M，任意x∈U（x0）?Rn，ηi（x）線性獨(dú)立，則映射ηi在x0的鄰域內(nèi)是正獨(dú)立映射。

命題3 設(shè)光滑映射ηi:Rn→Rn，i∈M，在x0∈Rn處有ηi（x0）＞0，或ηi（x0）＜0，則ηi在x0處是正獨(dú)立映射。

矛盾，命題得證。

命題4 設(shè)向量組βi∈Rn，i∈M，則向量組βi，i∈M是正獨(dú)立的充分必要條件:存在x∈Rn，使得（β1，β2，…，βm）Tx＜0有解。

證明:

推論 設(shè)向量βi∈Rn，i∈M，若βi是正獨(dú)立向量，則向量組βj也是正獨(dú)立向量，j=1，…，p，p＜m。

2 非凸優(yōu)化中的正獨(dú)立映射的判定

對于優(yōu)化問題

假設(shè)f，gi充分光滑。

Ω={x∈R|gi（x）≤0，i=1…，m}表示可行解集;

Ω0={x∈R|gi（x）＜0，i=1…，m}表示嚴(yán)格可行解;

?Ω=ΩΩ0表示可行解集的邊界;

I（x）={i|gi（x）=0，i=1，…，m}表示有效指標(biāo)集。

定義4 如果光滑映射η（x）滿足對?x∈?Ω，若

必有

則稱η（x）=（η1（x），η2（x），…，ηm（x））T關(guān)于▽g（x）正獨(dú)立。

定理1 映射η（x），關(guān)于▽g（x）正獨(dú)立的充分必要條件是對?x∈?Ω，?t∈（0，1），若

必有

證明:

充分條件:用反證法。假設(shè) η（x）關(guān)于▽g（x）不是正獨(dú)立的，即

且至少存在 αi1≠0，yi2≠0（若只存在 αi1≠0與η（x）是正獨(dú)立映射相矛盾，同理不能只有yi2≠0）。不妨設(shè)存在 αi1≠0，yi2≠0，再設(shè) αi1=（1-t）β，yi2=tk，其中 β≠0，k≠0則有（1-t）βηi1（x）+tk▽gi2（x）=0。與題設(shè)相矛盾。

定理2 設(shè)映射ηi:Rn→Rn，i∈M，是連續(xù)可微的，若?x∈?Ω，對?i∈I（x），存在1≤j≤n，使得

或

則該映射ηi（x），i∈M，關(guān)于▽ g（x）是正獨(dú)立的，其中

由命題3易證該定理。

定理3 若ηi（x），i∈M，關(guān)于▽g（x）是正獨(dú)立的，則?x∈?Ω，有

證明:由推論可知定理成立。

定理4 若{ηi（x）|i∈I（x）}是線性獨(dú)立的，則?x∈?Ω，有

證明:反證法。

定理5 映射ηi（x），i∈M，關(guān)于▽g（x）正獨(dú)立的充分必要條件是?x∈?Ω，有:

是Rn上的一個(gè)尖凸錐。

顯然成立。

3 構(gòu)造方法

例1:Ω={x∈Rn|gi（x）≤0，i=1，2，…，6}，如圖1所示。

圖1 例1可行域

其中約束函數(shù)g（x）由下列函數(shù)構(gòu)成:

取映射ηi（x）（i=1，2，…，6）如下:

易知ηi（x）是光滑的且關(guān)于▽g（x）是正獨(dú)立的。

例2:Ω={x∈Rn|（g1（x），g2（x））T≤0}，如圖2所示。

圖2 例2可行域

其中約束函數(shù)為:

取映射ηi（x）（i=1，2）如下 :

易知ηi（x）是光滑的且關(guān)于?Ω是正獨(dú)立的。

[1] Feng Guo-chen，Yu Bo.Combined homotopy interior point method for nonlinear programming[J].Problems，Lecture Notes inNum.Anal，1995，14:9-16.

[2] Feng Guo-chen，Lin Zheng-hua，Yu Bo.Existenceof an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem[J]. Nonlinear Analysis，1998，32:761-768.

[3] Lin Zheng-hua，Yu Bo，F(xiàn)eng Guo-chen.Combined homotopy interior point method forconvex nonlinear programming[J].Appl.Math.Computer，1997，84:193-211.

[4] Yu Bo，Lin Zheng-hua.Homotopy method for a class of nonconvex brouwer fixed pointproblems [J].Appl.Math.Computer，1996，74:65-77.

[5] 林正華，宋岱才，趙立芹.連續(xù)求解一般非凸規(guī)劃的K-K-T點(diǎn)[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào)，2002，17:207-218.

[6] Liu Qing-huai，Yu Bo，F(xiàn)eng Guo-chen.An interior point path-following mehod for nonconvex programming with quasi normal cone congdition[J].Advances in M athematics of Comunication，2000，29: 281-282.

[7] 王彩玲，劉慶懷，商玉鳳，等.一類多目標(biāo) Lipschitz規(guī)劃的最優(yōu)性充分條件[J].長春工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2003，24（3）:17-19.

[8] 高 巖.非光滑優(yōu)化[M].北京:科學(xué)出版社，2008.