一類雙層多目標(biāo)規(guī)劃問題的若干等價形式

魏彥吉， 陸 晶， 劉慶懷

（1.長春工業(yè)大學(xué)基礎(chǔ)科學(xué)學(xué)院，吉林長春 130012；2.吉林農(nóng)業(yè)大學(xué)發(fā)展學(xué)院基礎(chǔ)部，吉林長春 130600）

0 引 言

雙層規(guī)劃問題（Bilevel Programming Problem，BLPP）是一類特殊的平衡約束優(yōu)化問題，在工程學(xué)和經(jīng)濟(jì)學(xué)方面應(yīng)用廣泛，如經(jīng)濟(jì)規(guī)劃、農(nóng)業(yè)信貸分配、網(wǎng)絡(luò)設(shè)計(jì)、機(jī)器學(xué)習(xí)、交通運(yùn)輸規(guī)劃、模式識別等［1－5］。所以，近幾年越來越受到人們的重視。許多學(xué)者對其進(jìn)行了深入研究，提出了許多解決雙層規(guī)劃的算法。J F Bard和J T Moore［6］等研究提出了求解該問題的分支定界算法，Aiyoshi和Shimizu［7］等提出了罰函數(shù)法解決雙層規(guī)劃問題，但算法收斂速度比較慢，2004年，徐慶［8］等提出用同倫算法來求解雙層規(guī)劃問題，徐俊彥［9］等提出解線性互補(bǔ)問題的組合同倫方法，為雙層規(guī)劃算法的研究注入了新的活力。文中在平凡的條件下，給出了上層是多目標(biāo)，下層是單目標(biāo)的雙層多目標(biāo)規(guī)劃問題（簡稱BMOP）的若干等價形式。

1 基本概念與記號

考慮BMOP問題：

其中，（x，y）∈Rn＋m，f：Rn＋m→Rp，F(xiàn)：Rn＋m→R分別是上層和下層目標(biāo)函數(shù)，g＝（g1，g2，…，gs）T：Rn→Rs，G＝（G1，G2，…，Gl）T：Rn＋m→Rl分別是上層和下層約束條件。

文中使用記號如下：

S（x）——問題（1）下層的解集。

文中假設(shè)如下：

1）存在開集A?Rn，對任意x∈A，有D（x）≠φ；

2）存在有界開集Rm?B，使得對任意x∈A，有D（x）?B；

4）對任意x∈Ωx且y∈S（x），｛▽yGi（x，y），i∈（y）｝是線性獨(dú)立的；

5）對 任 意 的 （x，y）∈Ω，其 梯 度｛▽gi（x，y），i∈Ig（x，y）｝是線性獨(dú)立的。

對于BMOP問題（1），設(shè)f，F(xiàn)，g，G都是充分光滑的，F(xiàn)，G是凸的。

首先，考慮BMOP問題（1）的下層問題：

如果對于給定的點(diǎn)x∈Rn，則｛y∈Rm：G（x，y）＜0｝是非空的，下層優(yōu)化問題的KKT系統(tǒng)可寫為：

那么問題（1）可等價轉(zhuǎn)化為如下關(guān)于變量（x，y，u）的優(yōu)化問題：

下面將問題（2）等價轉(zhuǎn)換為如下問題：

其中，z∈Rl，它的引入只是為了后面證明的方便，并不是必須的。最小算子min是按z和u的分量取最小，即

若引入函數(shù)h0：Rn＋m＋l＋l→Rm＋l＋l如下：

則上面的問題可緊湊地寫為：

從而由假設(shè)條件易知，問題（4）等價于問題（2），即等價于問題（1），亦即（x＊，y＊）是問題（1）的一個全局（局部）解的充要條件，是存在一個向量（z＊，u＊）使得（x＊，y＊，z＊，u＊）為問題（4）的一個全局（局部）解。

為了處理互補(bǔ)型約束，文中引進(jìn)由Kanzow和Jiang［1］提出的NCP函數(shù)φμ：R2→R：

式中：μ——擾動參數(shù)，μ＞0。

其中

那么，當(dāng)μ≠0時，可定義最優(yōu)化問題：

問題（6）是問題（4）關(guān)于參數(shù)μ的一個光滑擾動問題，盡管問題（4）一般情形下非光滑，但當(dāng)μ≠0時，問題（6）則是一個光滑最優(yōu)化問題，且當(dāng)μ＝0時，問題（6）與問題（4）等價。

記

表示問題（6）的可行集，記

表示問題（6）的嚴(yán)格可行集，從而Ωμ的邊界可表示為：

將μ看做獨(dú)立變量，函數(shù)hμ則依賴于5個變量（x，y，z，u，μ），從而得到如下定理。

定理1 對任意的μ和問題（6）的可行點(diǎn)（x，y，z，u）∈Ωμ，關(guān)于變量（y，z，u）的所有hμ的廣義Jacobian矩陣是非奇異的。

證明：我們引進(jìn)的函數(shù)φμ（z，u）恰好與文獻(xiàn)［1］中使用的函數(shù)互為相反，從而很容易證明這種改變從根本上并不影響在文獻(xiàn)中關(guān)于函數(shù)φμ（z，u）非奇異性質(zhì)的證明。因此，當(dāng)μ≠0時，本定理的結(jié)果是文獻(xiàn)［10］中定理3.5的一個直接推論；而當(dāng)μ＝0時，本定理的結(jié)果是文獻(xiàn)［1］中引理2的一個直接推論。

由文獻(xiàn)［1］可類似證明hμ有如下性質(zhì)：

引理1 任意的μ，函數(shù)hμ（x，y，z，u）是局部Lipschitz連續(xù)和正則的。

引理2 設(shè)（μ＊，x＊，y＊，z＊，u＊）是hμ（x，y，z，u）＝0的一個解，則存在（μ＊，x＊）的一個鄰域Ωμ，x和一個連續(xù)函數(shù)（y，z，u）：Ωμ，x→Rm＋l＋l，使得對任意（μ，x）∈Ωμ，x，有

引理3 給定x＊∈Ωx，則對任意μ，存在唯一點(diǎn)（x＊，yμ（x＊），zμ（x），uμ（x＊））∈Ωμ使得hμ（）＝0，且θ＊μ作為μ的函數(shù)是連續(xù)的。

由上述引理可得如下定理。

定理2 對任意μ知，Ωμ為非空緊集，擾動問題（6）有Pareto最優(yōu)解。

由此，求解BMOP問題（1）可轉(zhuǎn)化為解優(yōu)化問題（6）。

即

2 結(jié) 語

通過以上討論，求解BMOP問題（1）就可通過同倫方法轉(zhuǎn)化為問題（2），再利用最小算子min將問題轉(zhuǎn)化為問題（3），引入函數(shù)h0：Rn＋m＋l＋l→Rm＋l＋l將問題轉(zhuǎn)化為（4），最后利用NCP函數(shù)轉(zhuǎn)化為解非線性優(yōu)化問題（6）和問題（7），并證明了解之間的關(guān)系。從而發(fā)現(xiàn)尋找更好的解決問題（7）的方法尤為關(guān)鍵，接下來將完善問題（7）的求解并給出數(shù)值例子。

［1］ 林銼云，董加禮.多目標(biāo)最優(yōu)化方法與理論［M］.長春：吉林科技出版社，1992.

［2］ 劉慶懷，林正華.求解多目標(biāo)規(guī)劃最小弱有效解的同倫內(nèi)點(diǎn)方法［J］.應(yīng)用數(shù)學(xué)學(xué)報(bào)，2000（2）：188-195.

［3］ 李佳民，劉慶懷.解一類雙層規(guī)劃問題的組合同倫方法［J］.吉林大學(xué)學(xué)報(bào)：理學(xué)版，2007，45（2）：213-215.

［4］ Hobbs B F，Nelson S K.A nonlinear bilevel model for amalysis of electric utility demand-side planning issues［J］.Ann.Oper.Res.，1992，34：255.

［5］ GarciaC B，Zangwill W I.Pathuays to solutions，fixed points and equilibria［M］.Prentice-Hall：New Tersey，1981.

［6］ Bard J F，Moore J T.A branch and bound algo-rithrn for the bilevel programming problem［J］.SIAM Journal on Science and Statistical Computing，1990，11（2）：281-292.

［7］ Aiyoshi E，Shimizn K.A solution method for the static constrained stackelberg problem wia penalty method［J］.IEEE Trans.，Automat，Contr.，1992，34：1111-1114.

［8］ Zhu Daoli，Xu Qing，Lin Zhenghua.A homotopy method for solving bilevel programming problem［J］.Nonlinear Analysis，2004，57：917-928.

［9］ 徐俊彥，苗壯，譚佳偉，等.解線性互補(bǔ)問題的組合同倫方法［J］.長春工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，31（3）：269-274.

［10］ Kanzow C，Jiang H.A cortinuation method for（strongly）monotone variational inequalities［J］. Math.，Prog.，1998，81：103-125.