半互補集合的相依切錐和極限法錐的刻畫

賈玲玲，劉玉蘭

（廣東工業(yè)大學 數(shù)學與統(tǒng)計學院, 廣東 廣州 510520）

隨著大數(shù)據(jù)時代的到來，越來越多的學者關(guān)注稀疏優(yōu)化問題，如帶有零模約束的優(yōu)化問題。

式中：f:Rn→R為連續(xù)可微的函數(shù)，κ 為一個給定的正整數(shù)且κ ＜n，Ω ?Rn為一個給定的集合，‖x‖0為向量x∈Rn的零模，即向量x中非零分量的個數(shù)。式(1)在統(tǒng)計、信號與圖像處理、機器學習、壓縮感知、基因選擇與分析等領(lǐng)域有廣泛的應用[1-6]。由于零模函數(shù)具有組合性質(zhì)，所以帶有零模約束的優(yōu)化模型(1)是NP(Nondeterminism Polynomial)難問題。文獻[7-9]把式(1)轉(zhuǎn)化為混合整數(shù)規(guī)劃問題進行求解。文獻[10-11]把式(1)轉(zhuǎn)化為帶有如下互補約束集的互補規(guī)劃，或稱為帶有均衡約束的數(shù)學規(guī)劃(Mathematical Programs, MP)。

另外，文獻[12]引理3.1，給出了零模函數(shù)的一個等價刻畫，即零模函數(shù)可看成是一個特定帶有互補約束集(2)的參數(shù)優(yōu)化的最優(yōu)值函數(shù)。利用零模函數(shù)的這個變分刻畫，文獻[13-14]研究了零模正則問題和零模極小化問題的一些等價Lipschitz代理，并討論了它們的穩(wěn)定點之間的關(guān)系。

眾所周知，刻畫約束集合的相依切錐和極限法錐對描述約束優(yōu)化問題的最優(yōu)性條件是至關(guān)重要的。文獻[15]刻畫了集合{x∈Rn:‖x‖0≤κ}的相依切錐、Clarke切錐和法錐，借助這些切錐和法錐的刻畫，給出了式(1)在Ω=Rn時的一階和二階最優(yōu)性條件。本文主要刻畫了由零模約束誘導出來的半互補約束集(2)的相依切錐、正則法錐和極限法錐。

1 定義

2 主要結(jié)論

根據(jù)文獻[16]中的命題6.41可知，半互補集合(2)的相依切錐、正則法錐和極限法錐的刻畫主要依賴n=1時對應的半互補集，即

的相依切錐、正則法錐和極限法錐的刻畫。下文刻畫了半互補集合D的相依切錐、正則法錐和極限法錐。

類似地，任意取定v∈R+,令序列vk≡v。容易驗證，對于任意的k一定有

聯(lián)合式(7)和式(8)，可得

下文主要來論證式(10)的包含關(guān)系成立。

3 結(jié)論

稀疏約束使得優(yōu)化問題(1)產(chǎn)生了組合特征，是一個NP難問題。一般來講，連續(xù)優(yōu)化的理論通常不能用于處理該類問題，但是稀疏約束集合的特殊結(jié)構(gòu)也為研究提供了一個新機遇。切錐、法錐是刻畫優(yōu)化問題的最優(yōu)性條件的重要工具之一。本文利用了切錐、法錐的工具,刻畫了半互補集合D的相依切錐、正則法錐和極限法錐。后續(xù)將提出相應的約束規(guī)范并建立最優(yōu)性條件。這些結(jié)果在某種程度上豐富了非連續(xù)、非凸規(guī)劃問題的最優(yōu)性理論。