DC復(fù)合優(yōu)化問(wèn)題的近似最優(yōu)性條件*

胡星星，鄭晴慧，田利萍

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

1 問(wèn)題的提出

(1)

他們利用內(nèi)點(diǎn)類條件、閉性條件和上圖類條件等得到了一系列有意義的結(jié)論，如Farkas引理、對(duì)偶理論和最優(yōu)性條件等[1-3].

許多優(yōu)化問(wèn)題，如凸優(yōu)化問(wèn)題、極小極大值問(wèn)題和最佳一致逼近問(wèn)題等，都可以轉(zhuǎn)化為如下復(fù)合優(yōu)化問(wèn)題[4-6]:

(2)

此外，許多實(shí)際問(wèn)題都可以視為如下DC錐約束優(yōu)化問(wèn)題[7-9]的特殊情形:

(3)

他引入新的約束條件，建立了問(wèn)題(3)的最優(yōu)性條件和拉格朗日全對(duì)偶.

注意到，文獻(xiàn)[3，6-7，9-10]主要是討論最優(yōu)化問(wèn)題的最優(yōu)解的特征刻畫(huà).實(shí)際上，對(duì)于某些復(fù)雜問(wèn)題，最優(yōu)解不一定存在或者并不需要計(jì)算其精確解.因此，如何建立優(yōu)化問(wèn)題的近似解的特征刻畫(huà)，成為現(xiàn)代優(yōu)化問(wèn)題研究的一個(gè)熱點(diǎn).例如，Long等[11]利用共軛函數(shù)上圖的特性得到了復(fù)合錐凸優(yōu)化問(wèn)題近似最優(yōu)解的充分必要條件，Bot等[12]得到了無(wú)約束函數(shù)的復(fù)合凸優(yōu)化問(wèn)題近似最優(yōu)解的充分必要條件.受這些工作的啟發(fā)，筆者擬利用函數(shù)ε-次微分的性質(zhì)，引入新的弱性約束規(guī)范條件，建立DC復(fù)合優(yōu)化問(wèn)題(3)的近似最優(yōu)解的特征刻畫(huà).

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

對(duì)X*，Y*和Z*分別賦予弱*拓?fù)鋡*(X*，X)，w*(Y*，Y)和w*(Z*，Z).y*，y表示泛函y*∈Y*在點(diǎn)y∈Y處的值，即y*，y=y*(y).設(shè)Y和Z分別是由閉凸錐S和K所定義的序空間.定義Y，Z上的序?yàn)?若y2-y1∈S，則y1≤Sy2;若z2-z1∈K，則z1≤Kz2.設(shè)S⊕表示S的對(duì)偶錐，即

S⊕∶={y*∈Y*:y*，y≥0,?y∈S}.

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

epif∶={(x，r)∈X×R:f(x)≤r}，

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

設(shè)x0∈domf，定義f在x0處的次微分為

?f(x0)∶={x*∈X*:f(x)-f(x0)≥x*，x-x0，?x∈X}.

(4)

設(shè)ε≥0，定義f在x0∈domf處的ε-次微分為

?εf(x0)∶={x*∈X*:f(x)-f(x0)≥x*，x-x0-ε，?x∈X}.

(5)

由文獻(xiàn)[13]中的定理2.3.1(ⅱ)和定理2.4.2(ⅲ)分別可知

f*(x*)+f(x)≥x*，x?(x，x*)∈X×X*，

(6)

f*(x*)+f(x)=x*，x?x*∈?f(x) ?(x，x*)∈X×X*.

(7)

(6)式稱為Young-Fenchel不等式，(7)式稱為Young等式.

設(shè)D是X中的非空凸集，δD表示D的示性函數(shù)，

令Nε(x0，D)表示D在點(diǎn)x0∈D的ε-法錐，

Nε(x0，D)∶={x*∈X*:x*，x-x0≤ε，?x∈D}.

(8)

特別地，由(5)和(8)式可知

Nε(x0，D)=?εδD(x0) ?x0∈D.

(9)

當(dāng)ε=0時(shí)，N(x0，D)∶=N0(x0，D)即為集合D在點(diǎn)x0∈D的法錐.

定義1設(shè)φ:X→Z?是真函數(shù)，稱函數(shù)φ為K-凸函數(shù)，如果對(duì)于?x，y∈X和t∈[0，1]，有

φ(tx+(1-t)y)≤Ktφ(x)+(1-t)φ(y).

f*(x*)+f(x0)≤x*，x0+ε?x*∈?εf(x0).

(f°φ)*(x*)≤f*(β)+(βφ)*(x*).

3 近似最優(yōu)性條件

令A(yù)表示系統(tǒng){x∈C;h(x)∈-S}的可行解集，即A∶={x∈C:h(x)∈-S}，本研究均假設(shè)dom(f°φ)∩A≠?.定義Λ(X)為X上的真凸函數(shù)族，顯然Λ(X)中的函數(shù)不一定是下半連續(xù)的.設(shè)g∈Λ(X).筆者主要研究如下帶錐約束的DC復(fù)合優(yōu)化問(wèn)題:

為了簡(jiǎn)便起見(jiàn)，設(shè)ε≥0，x∈X，定義

(10)

則下列包含關(guān)系成立:

命題1設(shè)ε≥0，則

Φ(ε，x)??ε(f°φ+δA)(x) ?x∈dom(f°φ)∩A.

(11)

證明令x∈dom(f°φ)∩A，p∈Φ(ε，x).由(10)式可知，存在ε1，ε2，ε3，ε4≥0，λ∈S⊕，β∈domf*∩?ε4(f°φ)(x)，u∈?ε1(βφ)(x)，v∈?ε2(λh)(x)，w∈Nε3(x，C)，使得

ε1+ε2+ε3+ε4=ε+(λh)(x)

(12)

且

u+v+w=p.

(13)

因?yàn)閡∈?ε1(βφ)(x)，v∈?ε2(λh)(x)，w∈Nε3(x，C)，β∈?ε4(f°φ)(x)，所以由(5)式可知，對(duì)于?y∈X，有

u，y-x≤(βφ)(y)-(βφ)(x)+ε1，

v，y-x≤(λh)(y)-(λh)(x)+ε2，

w，y-x≤δC(y)-δC(x)+ε3，

β，φ(y)-φ(x)≤(f°φ)(y)-(f°φ)(x)+ε4.

結(jié)合(12)和(13)式可知，對(duì)于?y∈X，有

p，y-x≤(f°φ+δC+λh)(y)-(f°φ+δC)(x)+ε≤(f°φ+δA)(y)-(f°φ+δA)(x)+ε.

因此，由(5)式可知p∈?ε(f°φ+δA)(x)，從而(11)式成立.證畢.

定義3設(shè)ε≥0，x∈dom(f°φ)∩A.稱系統(tǒng){f，φ，δA;λh:λ∈S⊕}在x點(diǎn)處滿足(ACCQ)條件，如果

?ε(f°φ+δA)(x)=Φ(ε，x).

(14)

稱該系統(tǒng)滿足(ACCQ)條件，如果對(duì)于?x∈dom(f°φ)∩A，都有(14)式成立.

注1(ⅰ)由命題1可知，系統(tǒng){f，φ，δA;λh:λ∈S⊕}滿足(ACCQ)條件，當(dāng)且僅當(dāng)

?ε(f°φ+δA)(x)?Φ(ε，x) ?x∈dom(f°φ)∩A.

(15)

(ⅱ)當(dāng)ε=0時(shí)，(ACCQ)條件轉(zhuǎn)化為文獻(xiàn)[10]中的(CBCQ)條件，即

為了刻畫(huà)DC復(fù)合優(yōu)化問(wèn)題(3)的近似最優(yōu)性條件，先給出問(wèn)題(3)的近似最優(yōu)解的定義.

定義4設(shè)ε≥0，x0∈A.稱x0為問(wèn)題(3)的近似最優(yōu)解，如果對(duì)于?x∈A，有

(f°φ-g)(x0)≤(f°φ-g)(x)+ε.

由ε-次微分的定義可知，

x0為問(wèn)題(3)的近似最優(yōu)解?0∈?ε(f°φ-g+δA)(x0).

(16)

命題2設(shè)ε≥0，x0∈A，則對(duì)于?p∈?g(x0)，有

0∈?ε(f°φ-g+δA)(x0)?p∈?ε(f°φ+δA)(x0).

(17)

證明設(shè)p∈?g(x0).由(4)式可知

g(x)-g(x0)≥p，x-x0?x∈X.

(18)

由(5)式可知0∈?ε(f°φ-g+δA)(x0)，當(dāng)且僅當(dāng)

(f°φ-g+δA)(x)-(f°φ-g+δA)(x0)+ε≥0 ?x∈X.

(19)

由(18)式可知(19)式成立，當(dāng)且僅當(dāng)

(f°φ+δA)(x)-(f°φ+δA)(x0)+ε≥p，x-x0?x∈X，

即p∈?ε(f°φ+δA)(x0).證畢.

設(shè)p∈X*，考慮如下帶線性擾動(dòng)的復(fù)合優(yōu)化問(wèn)題:

(20)

定理1設(shè)x0∈dom(f°φ)∩A且ε≥0，則下列命題等價(jià):

(ⅰ)系統(tǒng){f，φ，δA;λh:λ∈S⊕}在x0處滿足(ACCQ)條件.

(ⅱ)對(duì)于?g∈Λ(X)，x0是問(wèn)題(3)的近似最優(yōu)解，當(dāng)且僅當(dāng)對(duì)于?p∈?g(x0)，存在ε1，ε2，ε3，ε4≥0，λ∈S⊕，β∈domf*，u，v，w∈X*，使得:

(a)0≤(βφ)*(u)+(βφ)(x0)-u，x0≤ε1;

(b)0≤(λh)*(v)+(λh)(x0)-v，x0≤ε2;

(d)0≤f*(β)+(f°φ)(x0)-β，φ(x0)≤ε4;

(e)ε+(λh)(x0)=ε1+ε2+ε3+ε4;

(f)u+v+w=p.

(ⅲ)對(duì)于?p∈X*，x0是問(wèn)題(20)的近似最優(yōu)解，當(dāng)且僅當(dāng)存在ε1，ε2，ε3，ε4≥0，λ∈S⊕，β∈domf*，u，v，w∈X*，使得(ⅱ)中的(a)～(f)成立.

證明(ⅰ)?(ⅱ).假設(shè)(ⅰ)成立.令g∈Λ(X)，x0是問(wèn)題(3)的近似最優(yōu)解，則由(16)和(17)式可知，對(duì)于?p∈?g(x0)，有p∈?ε(f°φ+δA)(x0).由(ⅰ)可知p∈Φ(ε，x0).因此，存在ε1，ε2，ε3，ε4≥0，λ∈S⊕，β∈domf*∩?ε4(f°φ)(x0)，u∈?ε1(βφ)(x0)，v∈?ε2(λh)(x0)，w∈Nε3(x0，C)，使得

ε1+ε2+ε3+ε4=ε+(λh)(x0)

且

u+v+w=p，

即(e)和(f)成立.由β∈?ε4(f°φ)(x0)和引理1，有

f*(β)+(f°φ)(x0)≤β，φ(x0)+ε4.

由(6)式可知

β，φ(x0)-(f°φ)(x0)≤f*(β)，

即(d)成立.同理，由u∈?ε1(βφ)(x0)，v∈?ε2(λh)(x0)，w∈Nε3(x0，C)可知(a)～(c)成立.

反之，令g∈Λ(X).對(duì)于?p∈?g(x0)，存在ε1，ε2，ε3，ε4≥0，λ∈S⊕，β∈domf*，u，v，w∈X*，使得關(guān)系(a)～(f)成立.欲證x0是問(wèn)題(3)的近似最優(yōu)解，只需證p∈?ε(f°φ+δA)(x0).由(c)和(9)式可知，w∈Nε3(x0，C)，即w∈?ε3δC(x0)，因此

δ*C(w)+δC(x0)-w，x0≤ε3.

結(jié)合(a)，(b)，(d)，(e)可知

δC(x0)-w，x0+f*(β)+(f°φ)(x0)-β，φ(x0)≤

ε1+ε2+ε3+ε4=ε+(λh)(x0).

由(f)，有

(21)

對(duì)于?β∈domf*，λ∈S⊕，u，v∈X*，x∈X，由引理2可知

f*(β)+(βφ)*(u)≥(f°φ)*(u)≥u，x-(f°φ)(x)，

(λh)*(v)≥v，x-(λh)(x)≥v，x，

從而對(duì)于?x∈X，有

v，x+p-u-v，x-δC(x)=p，x-(f°φ+δC)(x)≥

p，x-(f°φ+δA)(x).

再由共軛函數(shù)的定義，有

(22)

結(jié)合(21)和(22)式可知

(f°φ+δA)*(p)+(f°φ+δA)(x0)≤ε+p，x0，

從而由引理1可得p∈?ε(f°φ+δA)(x0).

(ⅱ)?(ⅲ).顯然成立.

(ⅲ)?(ⅰ).假設(shè)(ⅲ)成立.由(15)式可知，只需證?ε(f°φ+δA)(x0)?Φ(ε，x0).為此，設(shè)p∈?ε(f°φ+δA)(x0)，則x0是問(wèn)題(20)的近似最優(yōu)解.故由(ⅲ)可知，存在ε1，ε2，ε3，ε4≥0，λ∈S⊕，β∈domf*，u，v，w∈X*，使得關(guān)系(a)～(f)成立.于是由(a)，(b)，(c)，(d)分別可得u∈?ε1(βφ)(x0)，v∈?ε2(λh)(x0)，w∈Nε3(x0，C)，β∈?ε4(f°φ)(x0)，由(f)可得

p=u+v+w∈?ε1(βφ)(x0)+?ε2(λh)(x0)+Nε3(x0，C).

因此p∈Φ(ε，x0)，從而?ε(f°φ+δA)(x0)?Φ(ε，x0).證畢.

定理1建立了問(wèn)題(3)和問(wèn)題(20)的近似最優(yōu)解的特征刻畫(huà).當(dāng)ε=0時(shí)，由定理1可知以下結(jié)論成立:

推論1設(shè)x0∈dom(f°φ)∩A，則以下命題等價(jià):

(ⅰ)系統(tǒng){f，φ，δA;λh:λ∈S⊕}在x0處滿足(CBCQ)條件.

(ⅱ)對(duì)于?g∈Λ(X)，x0是問(wèn)題(3)的最優(yōu)解，當(dāng)且僅當(dāng)對(duì)于?p∈?g(x0)，存在λ∈S⊕，β∈domf*，u，v，w∈X*，使得:

(a)(βφ)*(u)+(βφ)(x0)-u，x0=0;

(b)(λh)*(v)+(λh)(x0)-v，x0=0;

(d)f*(β)+(f°φ)(x0)-β，φ(x0)=0;

(e)u+v+w=p;

(f)(λh)(x0)=0.

(ⅲ)對(duì)于?p∈X*，x0是問(wèn)題(20)的近似最優(yōu)解，當(dāng)且僅當(dāng)存在λ∈S⊕，β∈domf*，u，v，w∈X*，使得(ⅱ)中的(a)～(f)成立.

注2Bot等[4]利用如下廣義內(nèi)點(diǎn)正則條件(CQ)得到了推論1的相關(guān)結(jié)論:

存在x∈ri(C):h(x)∈-ri(S)且φ(x)∈ri(D)-ri(K)，

其中D?Z是非空凸集，假設(shè)φ(C)?D.事實(shí)上，由文獻(xiàn)[11]中的例3.12可知，(CBCQ)條件弱于(CQ)條件.因此，推論1改進(jìn)了文獻(xiàn)[4]中的相關(guān)結(jié)論.