正獨立映射的判定及其在非凸優化中的應用

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

（1.長春工業大學應用數學所，吉林 長春 130012; 2.吉林農業大學信息技術學院，吉林長春 130018）

0 引 言

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

文中將就正獨立向量以及正獨立映射進行系統的研究，給出其性質及判定方法。

1 正獨立向量組與正獨立映射

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

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

若

必有

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

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

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

（1）當m=n時，rank（η（x0））=n;

（2）當m＜n時，rank（η（x0））=m。

其中

證明:（1）設

對于

同理可證（2）。

命題2 設向量組βi∈Rn，i∈M，若向量組βi，i∈M是線性獨立，則向量組βi，i∈M是正獨立的，即

該命題顯然成立。

性質:設光滑映射ηi:Rn→Rn，i∈M，任意x∈U（x0）?Rn，ηi（x）線性獨立，則映射ηi在x0的鄰域內是正獨立映射。

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

矛盾，命題得證。

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

證明:

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

2 非凸優化中的正獨立映射的判定

對于優化問題

假設f，gi充分光滑。

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

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

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

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

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

必有

則稱η（x）=（η1（x），η2（x），…，ηm（x））T關于▽g（x）正獨立。

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

必有

證明:

充分條件:用反證法。假設 η（x）關于▽g（x）不是正獨立的，即

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

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

或

則該映射ηi（x），i∈M，關于▽ g（x）是正獨立的，其中

由命題3易證該定理。

定理3 若ηi（x），i∈M，關于▽g（x）是正獨立的，則?x∈?Ω，有

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

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

證明:反證法。

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

是Rn上的一個尖凸錐。

顯然成立。

3 構造方法

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

圖1 例1可行域

其中約束函數g（x）由下列函數構成:

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

易知ηi（x）是光滑的且關于▽g（x）是正獨立的。

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

圖2 例2可行域

其中約束函數為:

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

易知ηi（x）是光滑的且關于?Ω是正獨立的。

[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，Feng 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] 林正華，宋岱才，趙立芹.連續求解一般非凸規劃的K-K-T點[J].高校應用數學學報，2002，17:207-218.

[6] Liu Qing-huai，Yu Bo，Feng 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] 王彩玲，劉慶懷，商玉鳳，等.一類多目標 Lipschitz規劃的最優性充分條件[J].長春工業大學學報:自然科學版，2003，24（3）:17-19.

[8] 高 巖.非光滑優化[M].北京:科學出版社，2008.