分式優(yōu)化問題的局部和全局最優(yōu)性條件*

田超松，王仙云

(吉首大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,湖南 吉首 416000)

許多實(shí)際問題,如資源分配問題、投資收益問題、生產(chǎn)計(jì)劃和調(diào)度問題等,大都可以轉(zhuǎn)化為分式優(yōu)化問題,因而分式優(yōu)化問題的研究受到學(xué)者們的廣泛關(guān)注[1-8].特別地,如下帶錐約束的分式優(yōu)化問題引起了學(xué)者的極大興趣：

s.t.x∈C,h(x)∈-S.

(1)

對于分式優(yōu)化問題(1),通常借助Dinkelbach方法[1],將分式優(yōu)化問題轉(zhuǎn)化為如下約束優(yōu)化問題進(jìn)行研究[1-6]：

inff(x)-μg(x)

s.t.x∈C,h(x)∈-S,

(2)

其中μ∈R.顯然,約束優(yōu)化問題(2)與μ的取值有關(guān).當(dāng)μ>0時(shí),問題(2)的目標(biāo)函數(shù)f-μg為DC函數(shù)(即2個(gè)凸函數(shù)的差);當(dāng)μ≤0時(shí),f-μg為凸函數(shù),問題(2)即為經(jīng)典的錐規(guī)劃問題.筆者擬分μ>0和μ≤0 2種情況進(jìn)行討論.在函數(shù)不一定下半連續(xù)、集合不一定是閉集的假設(shè)下,利用函數(shù)的次微分性質(zhì),分別引入新的約束規(guī)范條件,建立分式優(yōu)化問題(1)的局部和全局最優(yōu)性條件.

1 預(yù)備知識

設(shè)X和Y是實(shí)局部凸Hausdorff拓?fù)湎蛄靠臻g,X*和Y*分別表示X和Y的共軛空間,分別賦予弱*拓?fù)洇?(X*,X)和ω*(Y*,Y).x*,x表示泛函x*∈X*在點(diǎn)x∈X的值,即x*,x=x*(x).對于X的子集Z,用clZ和coneZ分別表示Z的閉包和凸錐包.進(jìn)一步,若Z是X的子集,則用Z⊕表示Z的對偶錐,即Z⊕∶={x*∈X*:x*,z≥0,?z∈Z}.用NZ(z0)表示Z在z0點(diǎn)的法錐,定義為

NZ(z0)∶={x*∈X*:x*,z-z0≤0, ?z∈Z}.

令δZ表示Z的示性函數(shù),

domf∶={x∈X:f(x)<+∞},

?f(x)∶={x*∈X*:f(x)+x*,y-x≤f(y),?y∈X} ?x∈domf.

f*(x*)∶=sup{x*,x-f(x):x∈X} ?x*∈X*.

特別地,由定義有NZ(x)=?δZ(x),?x∈Z.

由文獻(xiàn)[9]中的定理2.3.1和定理2.4.2(ⅲ)可知,Young-Fenchel不等式和Young等式成立,即

f(x)+f*(x*)≥x*,x?(x,x*)∈X×X*.

f(x)+f*(x*)=x*,x?x*∈?f(x)?(x*,x*,x-f(x))∈epif*.

?f(a)+?h(a)??(f+h)(a) ?a∈domf∩domh.

設(shè)φ:X→R∪{±∞}是一個(gè)實(shí)值函數(shù),x0∈domφ且滿足|φ(x0)|<+∞.定義函數(shù)φ在x0點(diǎn)的Frechet次微分為

顯然,由定義可知

(3)

(4)

且

x0為φ的整體最優(yōu)解?0∈?φ(x0).

(5)

(6)

顯然,h是S-凸函數(shù)當(dāng)且僅當(dāng)對于?λ∈S⊕,λh是凸函數(shù).

?(f+h)(a)=?f(a)+?h(a) ?a∈domf∩domh.

2 最優(yōu)性條件

引理2[5]x0是問題(1)的最優(yōu)解當(dāng)且僅當(dāng)x0∈A是以下問題的最優(yōu)解：

inff(x)-μ0g(x)

s.t.x∈C,h(x)∈-S.

(7)

顯然,問題(7)的目標(biāo)函數(shù)f-μ0g的性質(zhì)與μ0的取值有關(guān).當(dāng)μ0>0時(shí),問題(7)的目標(biāo)函數(shù)是DC函數(shù);當(dāng)μ0≤0時(shí),問題(7)的目標(biāo)函數(shù)是凸函數(shù).因此,筆者對問題(7)分2種情形進(jìn)行討論.為了簡便起見,記

(1)μ0>0的情形.

為了刻畫問題(1)的局部和全局最優(yōu)性條件,引入如下約束規(guī)范條件:

定義1(a)設(shè)x0∈dom(f-μ0g)∩A，若包含關(guān)系

(8)

成立,則稱系統(tǒng){f,g,δC;λh:λ∈S⊕}在x0處滿足(FBCQ)條件.若對于?x0∈dom(f-μ0g)∩A,(8)式成立,則稱該系統(tǒng)滿足(FBCQ)條件.

(b)設(shè)x0∈dom(f-μ0g)∩A，若等式

?(f-μ0g+δA)(x0)=Ω(x0)

(9)

成立,則稱系統(tǒng){f,g,δC;λh:λ∈S⊕}在x0處滿足(GBCQ)條件.若對于?x0∈dom(f-μ0g)∩A,(9)式成立,則稱該系統(tǒng)滿足(GBCQ)條件.

注1當(dāng)μ0=0時(shí),(FBCQ)條件與(GBCQ)條件一致并轉(zhuǎn)化為文獻(xiàn)[9]中的(BCQ)f條件,即

(10)

命題1假設(shè)(BCQ)f條件成立,則系統(tǒng){f,g,δC;λh:λ∈S⊕}滿足(FBCQ)條件,從而

?(f-μ0g+δA)(x0)?Ω(x0) ?x0∈dom(f-μ0g)∩A.

(11)

定理1假設(shè)系統(tǒng){f,g,δC;λh:λ∈S⊕}在x0處滿足(FBCQ)條件.若x0是問題(1)的局部最優(yōu)解,則對于?β∈?(μ0g)(x0),存在λ∈S⊕滿足(λh)(x0)=0,使得

β∈?f(x0)+NC(x0)+?(λh)(x0).

(12)

證明假設(shè)系統(tǒng){f,g,δC;λh:λ∈S⊕}在x0處滿足(FBCQ)條件,即(8)式成立.設(shè)x0是問題(1)的局部最優(yōu)解,由引理2可知x0也是問題(7)的局部最優(yōu)解,故由(4)式可知

(13)

又由(FBCQ)條件成立，結(jié)合(13)式可得

(14)

(14)式意味著對于?β∈?(μ0g)(x0),存在λ∈S⊕滿足(λh)(x0)=0,使得(12)式成立.證畢.

定理2假設(shè)系統(tǒng){f,g,δC;λh:λ∈S⊕}在x0處滿足(GBCQ)條件,則x0是問題(1)的全局最優(yōu)解當(dāng)且僅當(dāng)對于?β∈?(μ0g)(x0),存在λ∈S⊕滿足(λh)(x0)=0,使得(12)式成立.

證明假設(shè)系統(tǒng){f,g,δC;λh:λ∈S⊕}在x0處滿足(GBCQ)條件,即(9)式成立.由引理2和(5)式可知,x0是問題(1)的全局最優(yōu)解當(dāng)且僅當(dāng)

0∈?(f-μ0g+δA)(x0).

(15)

因?yàn)?GBCQ)條件成立,所以(15)式等價(jià)于0∈Ω(x0),即對于?β∈?(μ0g)(x0),存在λ∈S⊕滿足(λh)(x0)=0,使得(12)式成立.證畢.

定理3設(shè)x0是問題(1)的全局最優(yōu)解,則下列命題等價(jià):

(ⅰ)對于?β∈?(μ0g)(x0),存在λ∈S⊕滿足(λh)(x0)=0,使得(12)式成立.

(ⅱ)(11)式成立.

證明由定義可知,命題(ⅰ)成立等價(jià)于0∈Ω(x0).同時(shí)由(5)式可知,x0是問題(1)的全局最優(yōu)解等價(jià)于0∈?(f-μ0g+δA)(x0).證畢.

由命題1和定理1直接可得以下結(jié)論:

推論1假設(shè)(BCQ)f條件成立,若x0是問題(1)的局部最優(yōu)解,則對于?β∈?(μ0g)(x0),存在λ∈S⊕滿足(λh)(x0)=0,使得(12)式成立.

注2在假設(shè)f,g,h是真凸下半連續(xù)函數(shù),C是X的非空閉凸子集的情形下,Sun等[5]利用閉性條件

(16)

建立了當(dāng)μ0>0時(shí)問題(1)的局部最優(yōu)性條件.事實(shí)上,在此假設(shè)下,由文獻(xiàn)[9]中的命題3.1和文獻(xiàn)[10]中的推論3.4可知,(16)式嚴(yán)格強(qiáng)于(BCQ)f條件.于是,當(dāng)(16)式成立時(shí),由命題1可知 (BCQ)f條件成立.因此筆者改進(jìn)了文獻(xiàn)[5]中的定理3.2.

(2)μ0≤0的情形.

當(dāng)μ0≤0時(shí),問題(7)的目標(biāo)函數(shù)f-μ0g是凸函數(shù).由于凸函數(shù)的局部最優(yōu)解即為整體最優(yōu)解,因此現(xiàn)只考慮問題(1)的全局最優(yōu)性條件.

定義2設(shè)x0∈dom(f-μ0g)∩A，若

(17)

則稱系統(tǒng){f,g,δC;λh:λ∈S⊕}在x0點(diǎn)處滿足(CBCQ)條件.若對于?x0∈dom(f-μg)∩A,(17)式成立,則稱系統(tǒng){f,g,δC;λh:λ∈S⊕}滿足(CBCQ)條件.

注3當(dāng)μ0=0時(shí), (CBCQ)即為文獻(xiàn)[9]中的(BCQ)f條件.

命題2假設(shè)(BCQ)f條件成立，設(shè)g在domf∩domg∩A上有連續(xù)點(diǎn),則系統(tǒng){f,g,δC;λh:λ∈S⊕}滿足(CBCQ)條件.

證明假設(shè)(BCQ)f條件成立，即(10)式成立.設(shè)g在domf∩domg∩A上有連續(xù)點(diǎn),因?yàn)閒+δA和g都是真凸函數(shù),所以由引理1可知

?(f-μ0g+δA)(x0)=?(f+δA)(x0)+?(-μ0g).

于是,由(BCQ)f條件可知(17)式成立.

定理4假設(shè)系統(tǒng){f,g,δC;λh:λ∈S⊕}在x0處滿足(CBCQ)條件,則x0是問題(1)的最優(yōu)解當(dāng)且僅當(dāng)存在λ∈S⊕滿足(λh)(x0)=0,使得

0∈?f(x0)+?(-μ0g)(x0)+NC(x0)+?(λh)(x0).

(18)

證明假設(shè)系統(tǒng){f,g,δC;λh:λ∈S⊕}在x0處滿足(CBCQ)條件，即(17)式成立.由引理2和(5)式可知,x0是問題(1)的最優(yōu)解當(dāng)且僅當(dāng)(15)式成立.因?yàn)?CBCQ)條件成立,所以(15)式等價(jià)于

即存在λ∈S⊕滿足(λh)(x0)=0,使得(18)式成立.證畢.

由命題2和定理3可直接得到以下推論:

推論2假設(shè)g在domf∩domg∩A上有連續(xù)點(diǎn).若(BCQ)f條件成立,則x0是問題(1)的最優(yōu)解當(dāng)且僅當(dāng)存在λ∈S⊕滿足(λh)(x0)=0,使得(18)式成立.

注4在假設(shè)f,g,h是真凸下半連續(xù)函數(shù),C是X的非空閉凸子集的情形下,Sun等[5]利用閉性條件(CC1)建立了當(dāng)μ0≤0時(shí)問題(1)的局部最優(yōu)性條件.事實(shí)上,類似于文獻(xiàn)[9]中的命題3.1和文獻(xiàn)[10]中的推論3.4可知,閉性條件(CC1)嚴(yán)格強(qiáng)于(CBCQ)條件.于是,當(dāng)閉性條件(CC1)成立時(shí), (CBCQ)條件成立.因此筆者改進(jìn)了文獻(xiàn)[5]中定理3.1.