復(fù)合優(yōu)化問題的ε-對偶間隙性質(zhì)和ε-強對偶*

田利萍，方東輝

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

1 問題的提出

inff(φ(x))

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

(1)

特別地,當X=Z,φ為單位算子時,問題(1)即為如下經(jīng)典的錐約束優(yōu)化問題[10-14]：

inff(x)

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

(2)

許多學(xué)者對復(fù)合優(yōu)化問題進行了深入研究,得到了一系列有意義的結(jié)論.Bot等[1-2]在函數(shù)具有連續(xù)性、集合是閉集的情形下,刻畫了無約束條件下復(fù)合優(yōu)化問題與其對偶問題之間的強對偶和穩(wěn)定強對偶.方東輝等[3-4]在函數(shù)不一定是下半連續(xù)函數(shù)、集合不一定是閉集的情形下,利用共軛函數(shù)的上圖性質(zhì),等價刻畫了問題(1)與其對偶問題之間的零對偶間隙性質(zhì)、強對偶和Farkas引理.Boncea等[10]利用上圖類條件和ε次微分類條件，等價刻畫了問題(2)的ε-對偶間隙性質(zhì)和穩(wěn)定ε-對偶間隙性質(zhì).特別地,Boncea等[9]利用上圖類條件和次微分類條件,建立了復(fù)合優(yōu)化問題與其對偶問題之間的ε-對偶間隙性質(zhì)、穩(wěn)定ε-對偶間隙性質(zhì)和ε-Farkas引理.受上述文獻啟發(fā),筆者擬在函數(shù)不一定下半連續(xù)、集合不一定是閉集的情況下,通過引入新的約束規(guī)范條件,來等價刻畫問題(1)與其對偶問題之間的ε-對偶間隙性質(zhì)、ε-強對偶和ε-Farkas引理.

2 記號與定義

設(shè)X*,Y*和Z*分別是X,Y和Z的共軛空間,分別賦予弱*拓撲w*(X*,X),w*(Y*,Y)和w*(Z*,Z).〈x*,x〉表示泛函x*∈X*在x∈X處的值,即〈x*,x〉=x*(x).X的子集C的對偶錐和示性函數(shù)分別定義為

C⊕∶={x*∈X*:〈x*,c〉≥0,?c∈C},

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

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

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

由文獻[15]中的定理2.3.1可知,

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

(3)

epif*+epig*?epi(f+g)*,

f≤g?f*≥g*?epif*?epig*.

(4)

定義f與g的下端卷積函數(shù)f□g:X→R∪{±∞} 為

(h+p+r)*(x*)=h*(x*-p)-r?x*∈X*,

(5)

epi(h+p+r)*=epih*+(p,-r).

(6)

3 ε-對偶間隙性質(zhì)和ε-強對偶

設(shè)p∈X*.考慮帶線性擾動的復(fù)合優(yōu)化問題

inff(φ(x))-〈p,x〉

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

(7)

及其Lagrange對偶問題

(8)

特別地,當p=0時,問題(7)即為問題(1),而問題(8)轉(zhuǎn)化為

(9)

令v(i)(i為問題對應(yīng)的序號)表示問題的最優(yōu)值,則有

v(7)≥v(8),

(10)

即問題(1)與(9)之間的穩(wěn)定弱對偶成立.設(shè)A表示系統(tǒng){x∈C;h(x)∈-S}的解集,即A∶={x∈C:h(x)∈-S}.如不加特殊說明,文中均假設(shè)A∩dom(f°φ)≠?.

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

(11)

于是,對于?r∈R和p∈X*,有

(p,r)∈epi(f°φ+δA)*?v(7)≥-r.

(12)

如不加特殊說明,下文均假設(shè)ε≥0.

定義1(ⅰ)若v(1)-v(9)≤ε,則稱問題(1)和(9)之間的ε-對偶間隙性質(zhì)成立.

(ⅱ)若存在(λ,β)∈S⊕×domf*，使得對于?x∈C，有

v(1)≤(βφ)(x)-f*(β)+(λh)(x)+ε,

則稱問題(1)和(9)之間的ε-強對偶成立.

(ⅲ)若對于?p∈X*,有v(7)-v(8)≤ε,則稱問題(1)和(9)之間的穩(wěn)定ε-對偶間隙性質(zhì)成立.

(ⅳ)若對于?p∈X*,存在(λ,β)∈S⊕×domf*，使得對于?x∈C，有

v(7)≤(βφ)(x)-f*(β)+(λh)(x)-〈p,x〉+ε,

則稱問題(1)和(9)之間的穩(wěn)定ε-強對偶成立.

為了簡便起見,記

為了研究問題(1)和(9)之間的ε-對偶間隙性質(zhì)和ε-強對偶,引入如下約束規(guī)范條件:

epi(f°φ+δA)*?Ω1-(0,ε),

(13)

epi(f°φ+δA)*?Ω2-(0,ε).

(14)

(13)式稱為(CQIε)條件, (14)式稱為(CQε)條件.

命題1如下包含關(guān)系成立:

Ω2?Ω1?epi(f°φ+δA)*.

(15)

證明設(shè)p∈X*.對于?(λ,β)∈S⊕×domf*，有

于是,由(4)式可知Ω2?Ω1.接下來只需證明

Ω1?epi(f°φ+δA)*.

(16)

(βηφ-f*(βη)+δC+ληh)*(p)≤r+η.

(17)

由(3)式可知，〈βη,φ(x)〉-f*(βη)≤f(φ(x)),?x∈X,同時δC(x)+(ληh)(x)≤δA(x),?x∈X,因此

(βηφ)(x)-f*(βη)+δC(x)+(ληh)(x)≤f(φ(x))+δA(x) ?x∈X.

(18)

由(4)，(17)和(18)式可知，

(f°φ+δA)*(p)≤(βηφ-f*(βη)+δC+ληh)*(p)≤r+η.

令η→0，則(f°φ+δA)*(p)≤r,即(p,r)∈epi(f°φ+δA)*，故(16)式成立.證畢.

注1(ⅰ)由命題1可知(CQε)條件?(CQIε)條件.

(ⅱ)當ε=0時,由(15)式可知(CQIε)條件轉(zhuǎn)化為

epi(f°φ+δA)*=Ω1,

(19)

(CQε)條件轉(zhuǎn)化為文獻[4]中的(CQ3)條件,即epi(f°φ+δA)*=Ω2.

定理1(ⅰ)問題(1)和(9)之間的ε-對偶間隙性質(zhì)成立，當且僅當

epi(f°φ+δA)*∩({0}×R)?Ω1∩({0}×R)-(0,ε).

(ⅱ)問題(1)和(9)之間的穩(wěn)定ε-對偶間隙性質(zhì)成立，當且僅當(CQIε)條件成立.

證明因命題(ⅰ)和(ⅱ)的證明基本類似,故此處只證明命題(ⅱ).由共軛函數(shù)的定義可知，

(20)

于是,由(11)和(20)式可知,問題(1)和(9)之間的穩(wěn)定ε-對偶間隙性質(zhì)成立等價于

(21)

由(4)和(6)式可知,(21)式等價于epi(f°φ+δA)*?Ω1-(0,ε),因此結(jié)論成立.證畢.

定理1等價刻畫了問題(1)和(9)之間的ε-對偶間隙性質(zhì)和穩(wěn)定ε-對偶間隙性質(zhì).

當ε=0時,由定理1、注1(ⅱ)和(10)式可得如下結(jié)論：

推論1(ⅰ)問題(1)和(9)之間的零對偶間隙成立(即v(1)=v(9))，當且僅當

epi(f°φ+δA)*∩({0}×R)=Ω1∩({0}×R).

(22)

(ⅱ)問題(1)和(9)之間的穩(wěn)定零對偶間隙成立(即v(7)=v(8))，當且僅當(19)式成立.

由(4)式可知，

注2文獻[3]中的定理 4.2和定理 4.4分別利用約束規(guī)范條件

(23)

(24)

建立了問題(1)與其對偶問題

(25)

之間的零對偶間隙性質(zhì)和穩(wěn)定零對偶間隙性質(zhì).

命題2如下結(jié)論成立:(23)?(22),(24)?(19).

證明因“ (23)?(22) ”和“ (24)?(19) ”的證明基本類似,故此處只證明“ (24)?(19) ”.假設(shè)(24)式成立.由命題1可知,欲證(19)式成立,只需證明

(26)

又由(3)式可知,對于?(λ,β)∈S⊕×domf*和y*,z*∈X*，有

〈z*,x〉-(λh)(x)+〈p-y*-z*,x〉-δC(x)+f*(β)=

〈p,x〉-(βφ-f*(β)+δC+λh)(x) ?x∈X.

于是

從而(p,r)∈Ω1，故(26)式成立.證畢.

注3由共軛函數(shù)的定義可知,問題(25)與(9)等價.而由命題2可知,(23)和(24)式分別強于(22)和(19)式.因此,推論1改進了文獻[3]中的定理4.2和定理4.4.

定理2下列命題等價:

(ⅰ)(CQε)條件成立.

(ⅱ)對于?p∈X*,存在(λ,β)∈S⊕×domf*，使得

(f°φ+δA)*(p)≥〈p,x〉-(βφ-f*(β)+λh)(x)-ε?x∈C.

(27)

(ⅲ)設(shè)p∈X*，r∈R.若對于?x∈A，有f(φ(x))-〈p,x〉≥-r,則存在λ∈S⊕，β∈domf*，使得

(βφ)(x)-f*(β)+(λh)(x)-〈p,x〉≥-r-ε?x∈C.

(28)

(ⅳ)問題(1)和(9)之間的穩(wěn)定ε-強對偶成立.

證明(ⅰ)?(ⅱ).假設(shè)(CQε)條件成立.令p∈X*，若(f°φ+δA)*(p)=+∞,則(27)式成立.下設(shè)r∶=(f°φ+δA)*(p)<+∞,則(p,r)∈epi(f°φ+δA)*.由(CQε)條件可知 (p,r)∈Ω2-(0,ε),于是存在(λ,β)∈S⊕×domf*，使得

(p,r)∈epi(βφ-f*(β)+δC+λh)*-(0,ε),

即

(p,r+ε)∈epi(βφ-f*(β)+δC+λh)*，

從而

(βφ-f*(β)+δC+λh)*(p)≤r+ε.

(29)

由(3)和(29)式可得，

〈p,x〉-(βφ-f*(β)+λh)(x)≤r+ε?x∈C,

因此(27)式成立.

(ⅱ)?(ⅲ).假設(shè)(ⅱ)成立.令p∈X*，r∈R.若對于?x∈A，有f(φ(x))-〈p,x〉≥-r,則由(11)式可知,-(f°φ+δA)*(p)≥-r. 又(ⅱ)成立,則存在(λ,β)∈S⊕×domf*，使得

-r≤-(f°φ+δA)*(p)≤(βφ-f*(β)+λh)(x)-〈p,x〉+ε?x∈C，

即(28)式成立.

(ⅲ)?(ⅳ).假設(shè)(ⅲ)成立.令p∈X*，-r∶=v(7)∈R,則對于?x∈A，有f(φ(x))-〈p,x〉≥-r.由(ⅲ)可知,存在(λ,β)∈S⊕×domf*,使得對于?x∈C,有

(βφ)(x)-f*(β)+(λh)(x)-〈p,x〉≥-r-ε,

于是

v(7)=-r≤(βφ)(x)-f*(β)+(λh)(x)-〈p,x〉+ε?x∈C,

因此問題(1)和(9)之間的穩(wěn)定ε-強對偶成立.

(ⅳ)?(ⅰ).假設(shè)(ⅳ)成立.任取(p,r)∈epi(f°φ+δA)*.由(12)式可知,v(7)≥-r.又因(ⅳ)成立,故存在(λ,β)∈S⊕×domf*，使得

-r≤v(7)≤(βφ)(x)-f*(β)+δC(x)+(λh)(x)-〈p,x〉+ε?x∈C,

于是

從而(p,r+ε)∈epi(βφ-f*(β)+δC+λh)*,即(p,r)∈Ω2-(0,ε),因此(CQε)條件成立.證畢.

定理2等價刻畫了問題(1)和(9)之間的穩(wěn)定ε-強對偶和穩(wěn)定ε-Farkas引理.

當p=0時,由定理2可得如下結(jié)論：

定理3下列命題等價:

(ⅰ)

epi(f°φ+δA)*∩({0}×R)?Ω2∩({0}×R)-(0,ε).

(30)

(ⅱ)設(shè)r∈R.若對于?x∈A，有f(φ(x))≥-r,則存在(λ,β)∈S⊕×domf*，使得

(βφ)(x)-f*(β)+(λh)(x)≥-r-ε?x∈C.

(ⅲ)問題(1)和(9)之間的ε-強對偶成立.

注4由注1(ⅱ)可知,當ε=0時,(CQε)條件和(30)式分別是文獻[4]中的(CQ3)條件和定理3.6(ⅰ). 因此,結(jié)合(10)式可知,定理2和定理3分別推廣了文獻[4]中的定理4.1和定理4.4.

4 應(yīng)用

設(shè)p∈X*,X=Z,φ為單位算子,則問題(7)轉(zhuǎn)化為

inff(x)-〈p,x〉

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

(31)

問題(8)轉(zhuǎn)化為

(32)

當p=0時,問題(31)轉(zhuǎn)化為問題(2)，問題(32)轉(zhuǎn)化為

(33)

同時,(CQIε)和(CQε)條件分別轉(zhuǎn)化為

(34)

(35)

于是，由定理1～3可得如下結(jié)論：

定理4(ⅰ)問題(2)和(33)之間的ε-對偶間隙性質(zhì)成立，當且僅當

(ⅱ)問題(2)和(33)之間的穩(wěn)定ε-對偶間隙性質(zhì)成立，當且僅當(34)式成立.

定理5下列命題等價:

(ⅰ)(35)式成立.

(ⅱ)設(shè)p∈X*，r∈R.若對于?x∈A，有f(x)-〈p,x〉≥-r,則存在λ∈S⊕，x*∈domf*，使得-f*(x*)-(δC+λh)*(p-x*)≥-r-ε.

(ⅲ)問題(2)和(33)之間的穩(wěn)定ε-強對偶成立.

定理6下列命題等價:

(ⅱ)設(shè)r∈R.若對于?x∈A，有f(x)≥-r,則存在(λ,x*)∈S⊕×domf*，使得

-f*(x*)-(δC+λh)*(-x*)≥-r-ε.

(ⅲ)問題(2)和(33)之間的ε-強對偶成立.

注5Boncea等[10]利用

(36)

得到了定理4(ⅱ)的相關(guān)結(jié)論.由下端卷積函數(shù)的定義可知,(34)與(36)式等價，因此定理4(ⅱ)推廣了文獻[10]中的推論2.12.