雙約束二階錐變分不等式的最優(yōu)性條件分析

王彬，王莉，孫菊賀，孫藝寧，袁艷紅

（1. 沈陽(yáng)航空航天大學(xué) 理學(xué)院，沈陽(yáng) 110136；2. 太原理工大學(xué) 經(jīng)濟(jì)管理學(xué)院， 太原 030024）

本文研究二階錐雙約束變分不等式問題，即求解x*∈Ω，使得

其中C={y∈Ω|-g(x*，y)∈Km}。

式中：F：Rn→Rn為單調(diào)的向量值映射；g：Rn×Rn→Rm為連續(xù)可微映射；＜·，·＞為歐氏內(nèi)積；K=Km1×Km2×…×Kmp，且m1+m2+…mp=m，mi≥1，i=1，2，…，p，每個(gè)Kmi都是mi維的二階錐，集合Ω?Rn為一閉凸集。雙約束條件是形如-g(x*，y)∈Km的約束，該條件與經(jīng)典問題的不同主要在于它將問題的參量與其自身變量聯(lián)系在一起，這給雙約束優(yōu)化問題的研究帶來(lái)了難度和挑戰(zhàn)。

作為數(shù)學(xué)規(guī)劃領(lǐng)域一個(gè)重要的分支，借助變分不等式問題及其特例互補(bǔ)問題可以構(gòu)造出多種數(shù)學(xué)模型和均衡規(guī)劃模型，因此對(duì)于其數(shù)值解的研究具有一定的理論價(jià)值和實(shí)際意義。2000年，Antipin［1］首先提出了具有雙約束條件的變分不等式問題，它在許多數(shù)學(xué)問題中都有應(yīng)用，如：帶有成本預(yù)算的經(jīng)濟(jì)均衡模型［2］、雙人博弈問題［3］、雙層規(guī)劃及層次規(guī)劃［4］等。Antipin［5］研究了雙約束的均衡規(guī)劃問題，討論了對(duì)稱和反對(duì)稱函數(shù)的性質(zhì)，提出了微分反饋控制梯度法，并證明了該方法的全局收斂性。基于變分不等式理論的廣泛應(yīng)用，經(jīng)典變分不等式和廣義變分不等式都已被深入研究，F(xiàn)acchinei等［6］的專著囊括了有限維空間中互補(bǔ)問題與變分不等式幾乎所有的基礎(chǔ)成果，為該領(lǐng)域的進(jìn)一步研究提供了理論支持。

最優(yōu)性條件是最優(yōu)化問題的目標(biāo)函數(shù)和約束函數(shù)在最優(yōu)點(diǎn)所滿足的必要條件和充分條件。最優(yōu)性條件在優(yōu)化算法的終止判定以及優(yōu)化理論的證明中有著重要作用。在最優(yōu)化理論中，Robinson約束規(guī)范條件是最著名的約束規(guī)范條件之一，在進(jìn)行優(yōu)化問題的最優(yōu)性條件以及穩(wěn)定性分析的研究中有著重要作用，相關(guān)介紹可參閱文獻(xiàn)［7-9］。學(xué)者Bonnans等［10-11］對(duì)非線性二階錐優(yōu)化問題所做的一階必要性、二階充分性條件、約束非退化條件等內(nèi)容的描述與分析，對(duì)本文相關(guān)結(jié)論的推導(dǎo)有很大幫助。張立衛(wèi)［12］全面介紹了非線性錐約束優(yōu)化的最優(yōu)性理論，其中第3、4章詳細(xì)論述了一些具體的約束優(yōu)化問題的最優(yōu)性理論，還介紹了不同類型的優(yōu)化問題的Robinson約束規(guī)范、約束非退化條件、最優(yōu)解的一階必要性條件、二階充分性條件等內(nèi)容。

本文提出了雙約束二階錐變分不等式問題，并對(duì)該問題進(jìn)行最優(yōu)性條件分析。通過對(duì)原始問題進(jìn)行等價(jià)轉(zhuǎn)換后，借助所得出的廣義鞍點(diǎn)問題，建立極小極大問題模型，將其轉(zhuǎn)換為變分不等式組問題，得到該變分不等式組對(duì)應(yīng)的KKT條件，應(yīng)用Lagrange對(duì)偶理論得到所研究雙約束二階錐變分不等式問題的一階必要性條件?；诩s束集合的切錐、二階切集公式以及對(duì)偶理論，推導(dǎo)出雙約束二階錐變分不等式問題的二階充分性條件，從而實(shí)現(xiàn)雙約束二階錐變分不等式問題的解的最優(yōu)性條件的研究。

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

為了求解雙約束二階錐變分不等式問題的一階最優(yōu)性條件，首先介紹推導(dǎo)過程中所用到的概念與相關(guān)性質(zhì)。

定義1［1］稱向量值函數(shù)g：Rn×Rn→Rm在Rn×Rn上是對(duì)稱的，若有式（2）成立

對(duì)稱向量值函數(shù)的具體應(yīng)用可以體現(xiàn)在帶有成本限制的經(jīng)濟(jì)均衡模型中，如：或者，式中：A為對(duì)稱矩陣；v、w為n維列向量。

性質(zhì)1［1］向量值對(duì)稱函數(shù)g：Rn×Rn→Rm關(guān)于變量x和y的梯度在集合Ω×Ω上的值相等，即有式（3）成立

證明：對(duì)式（2）中等號(hào)左側(cè)關(guān)于第二元y求導(dǎo)，等號(hào)右側(cè)關(guān)于第二元x求導(dǎo)可得

在上式中，令y=x可得等號(hào)左右兩側(cè)的m×n矩陣相等，即得式（3），證畢。

性質(zhì)2［1］算子與對(duì)稱函數(shù)g(x，y)|x=y在集合Ω×Ω上的梯度是一致的，即有下述關(guān)系成立

證明：由可微的定義對(duì)g(x，y)作展開，即

在上式中，令y=x，h=k，結(jié)合性質(zhì)1及其證明可得下述展開形式

該式可以看作是對(duì)g(x，y)作Taylor展開的一種特殊情形，式中g(shù)(x，x)可視為g(x，y)在y=x(x，y∈Ω)時(shí)的函數(shù)，其梯度為?Τg(x，x)，即式（4）成立，證畢。

定義2若Kn∈Rn(n≥1)滿足則稱Kn為n維的二階錐，又稱冰激凌錐。它是自對(duì)偶的閉凸錐，且其內(nèi)點(diǎn)集intKn與邊界點(diǎn)集bdKn表述如下intKn=。

可以發(fā)現(xiàn)，當(dāng)n=1時(shí)，Kn退化為非負(fù)實(shí)數(shù)集R+，因此Antipin［1］提出的具有雙約束條件的變分不等式問題是本文的雙約束二階錐變分不等式問題（1）的特殊情形。

為了研究雙約束二階錐變分不等式的二階必要性條件，下面給出二階錐的切錐與二階切集公式。

引理1［8］二階錐Kn上任意一點(diǎn)x=(x0，)處的切錐為

Kn上任意一點(diǎn)x處沿方向d∈TKn(x)的二階切集為

定義3［9］設(shè)ΚX?X與ΚY?Y是任意非空集合，與函數(shù)L：ΚX×ΚY→相聯(lián)系的原始與對(duì)偶問題定義為

稱L為上述極小極大對(duì)偶性Lagrange函數(shù)，稱∈ΚX×ΚY是函數(shù)L(x，y)的鞍點(diǎn)。若

定義4［13］集合C?X的指示函數(shù)記為IC，定義為

并約定IRn=0，I?=∞。

2 雙約束二階錐變分不等式的等價(jià)轉(zhuǎn)換

本文所研究的雙約束二階錐變分不等式問題（1）對(duì)應(yīng)的最優(yōu)化問題

優(yōu)化問題（7）對(duì)應(yīng)的Lagrange函數(shù)為

式中：x*是原始問題的最優(yōu)解；y、λ分別為原始變量與對(duì)偶變量。由于x*是f(y)在集合Ω上的最小值點(diǎn)，在一定正則條件下（如Slater條件成立），點(diǎn)對(duì)(x*，λ*)是Lagrange函數(shù)L(x*，y，λ)的鞍點(diǎn)，根據(jù)鞍點(diǎn)定義3可知，有以下鞍點(diǎn)不等式成立

定理1雙約束二階錐變分不等式問題（1）等價(jià)轉(zhuǎn)化為變分不等式問題（10）

證明：原問題（1）可以視作線性函數(shù)

上述不等式說明(x*，λ*)滿足下面關(guān)系

對(duì)于鞍點(diǎn)不等式（11），運(yùn)用極小極大問題模型［14］，可做如下推導(dǎo)

考慮極小極大問題

(x*λ*)∈C×Km是Lagrange函數(shù)

L(x*，y，λ)的鞍點(diǎn)的必要條件為

即

根據(jù)對(duì)稱函數(shù)的性質(zhì)2及向量值函數(shù)g(x，x)的各分量的凸性，式（15）中第一個(gè)表達(dá)式中關(guān)于函數(shù)g(x，x)的運(yùn)算可以有下面的形式

則雙約束二階錐變分不等式（1）可等價(jià)轉(zhuǎn)化為鞍點(diǎn)問題（16）

因此，問題（16）可以表述為下面的形式

若令Y=C×Κm，

Y={z∈Rn+m|G(z)∈Κ2m}，其中參量z=，約束條件為，證畢。

3 一階必要性條件

本節(jié)研究問題（10）對(duì)應(yīng)的優(yōu)化問題（18）的Lagrange對(duì)偶理論，由此分析出其最優(yōu)解同時(shí)也包括原變分不等式的解需要滿足的一階必要條件，并對(duì)相關(guān)性質(zhì)加以研究。

雙約束二階錐變分不等式問題（10）可以看作下述優(yōu)化問題的等價(jià)形式

其中函數(shù)

且f：Rn+m→Rn+m是一連續(xù)可微函數(shù)，約束條件中的G：R2m→R2m是一連續(xù)可微的向量值函數(shù)，K2m? R2m為一閉凸錐。

優(yōu)化問題（18）對(duì)應(yīng)的Lagrange函數(shù)為

因此，問題（18）的Lagrange對(duì)偶問題為

由于最優(yōu)值val(P)≥val(D)，若對(duì)于點(diǎn)對(duì)(z*，p*)∈Y×Κ2m，使得原始與對(duì)偶目標(biāo)函數(shù)值相等，即

式中：I為指示函數(shù)，則有val(P)=val(D)。進(jìn)一步若其公共值是有限的，則z*∈Y與p*∈K2m分別為最優(yōu)化問題（18）與對(duì)偶問題（20）的最優(yōu)解。由鞍點(diǎn)定理可知，原始對(duì)偶問題的解(z，p)可由下述系統(tǒng)刻畫

總結(jié)上述關(guān)系，借助Lagrange對(duì)偶理論［9］，可以得到下述結(jié)論。

定理 2令val(P)與val(D)分別表示原始問題（18）與對(duì)偶問題（20）的最優(yōu)值，則有val(P)≥val(D)。進(jìn)一步可推出，val(P)=val(D)，且該公共值是有限的，則z*∈Y與p*∈K2m分別為原始問題P與對(duì)偶問題D的最優(yōu)解的充分必要條件是式（21）成立。

稱點(diǎn)對(duì)(z*，p*)為問題（18）的KKT點(diǎn)，若(z*，p*)滿足KKT條件（22）

上述系統(tǒng)即為一般情形的一階必要性條件，是從代數(shù)角度推導(dǎo)出的，K-T乘子p*也稱為L(zhǎng)agrange乘子，z*為問題（18）的局部最優(yōu)解，可將其進(jìn)一步總結(jié)為下述定理。

定理3設(shè)z*是雙約束二階錐優(yōu)化問題（18）的局部最優(yōu)解，且滿足Robinson約束規(guī)范

則在z*處的Lagrange乘子集合Λ(z*)是非空緊致凸集合。

證明：設(shè)(z*，p*)為問題（18）相應(yīng)的La‐grange對(duì)偶問題的最優(yōu)解對(duì)，其中p*為L(zhǎng)a‐grange乘子，則(z*，p*)滿足KKT條件（22）。由于能夠保證（22）的Lagrange乘子集合是緊致集的充分必要條件正是Robinson約束規(guī)范條件，即

由文獻(xiàn)［15］知，式（24）的等價(jià)表達(dá)為

證畢。

假設(shè)z*是雙約束二階錐優(yōu)化問題（18）的穩(wěn)定點(diǎn)，即點(diǎn)對(duì)(z*，p*)滿足KKT條件（22）。若在z*處有下述約束非退化條件成立

式中：linΤK2m(G(z*))是二階錐K2m在G(z*)的切錐的線性化空間。則可得出約束非退化條件與Lagrange乘子的唯一性關(guān)系。

定理4假設(shè)z*是雙約束二階錐優(yōu)化問題（18）的一個(gè)穩(wěn)定點(diǎn)，若z*是約束非退化的，則存在唯一的Lagrange乘子p*；反之，若(z*，p*)滿足嚴(yán)格互補(bǔ)條件G(z*)+p*∈intK2m，且p*是唯一對(duì)應(yīng)z*的Lagrange乘子，則z*是非退化的最優(yōu)解。

4 二階充分性條件

本節(jié)討論雙約束二階錐變分不等式問題（18）的二階充分性條件。設(shè)映射f(z)與G(z)是二階連續(xù)可微的。下述定理給出了問題（18）在穩(wěn)定點(diǎn)z*處的臨界錐的定義。

定理5設(shè)z*是問題（18）的一個(gè)穩(wěn)定點(diǎn)，Lagrange乘子p∈Λ(z*)。給定方向h∈Rn+m，借助引理1中的公式，可推出如式（25）的臨界錐的結(jié)論

定理6設(shè)z*是問題（18）的一個(gè)穩(wěn)定點(diǎn)，且滿足Robinson約束規(guī)范條件（23），則在z*處二階增長(zhǎng)條件成立當(dāng)且僅當(dāng)式（26）的二階條件成立

式中：H(z*，p)=

證明：假設(shè)定理?xiàng)l件成立，則由文獻(xiàn)［9］可知二階錐是二階正則的，在z*處二階增長(zhǎng)條件成立當(dāng)且僅當(dāng)下述條件成立

其中?2：=表示在G(z*)處沿方向?ΤG(z*)h的二階切集，σ(·，?2)為集合?2的支撐函數(shù)。

該定理只需證明式（26）是式（27）的具體表述形式即可?？紤]在G(z*)處沿著?ΤG(z*)h方向的二階切集形式如下：

由于二階錐是卡式積運(yùn)算，故可以計(jì)算支撐函數(shù)σ(-p，?2)如下。

（1）由h∈C(z*)知，

?ΤG(z*)h∈TK2m(G(z*))，又由

-p*∈NK2m(G(z*))且G(z*)∈K2m，由二階切集的定義知，σ(-p，?2)≤0。

若0∈?2，則σ(-p；?2)=0。由式（28）可知，若?ΤG(z*)h∈intTK2m(G(z*))或者

G(z*)=0或者?ΤG(z*)h=0時(shí)，都有0∈?2。

（2）若?ΤG(z*)h，G(z*)∈bdK2m{0}，記滿足該情形的指標(biāo)集合為I，由式（28）可得

故在此情形下，有

綜合上述情況，可推出

證畢。

5 結(jié)論

Antipin［1］所研究的雙約束變分不等式是雙約束二階錐變分不等式的特殊情形，本文討論了雙約束二階錐變分不等式問題的一階必要性條件和二階充分性條件。首先對(duì)原始雙約束二階錐變分不等式問題進(jìn)行極小化問題轉(zhuǎn)化后得出了廣義鞍點(diǎn)不等式，借助極小極大問題模型，可以將其等價(jià)于一個(gè)變分不等式組。進(jìn)一步對(duì)所得出的等價(jià)變分不等式組分析，應(yīng)用Lagrange對(duì)偶理論得出其有解的一階必要性條件。然后借助約束集合的二階切集與對(duì)偶理論，得到雙約束二階錐變分不等式問題的二階充分性條件。雙約束二階錐變分不等式問題的最優(yōu)性條件的分析對(duì)該問題的解的存在性及收斂性的研究給出了理論支持。