一類雙層多目標規劃問題的若干等價形式

魏彥吉， 陸 晶， 劉慶懷

（1.長春工業大學基礎科學學院，吉林長春 130012；2.吉林農業大學發展學院基礎部，吉林長春 130600）

0 引 言

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

1 基本概念與記號

考慮BMOP問題：

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

文中使用記號如下：

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

文中假設如下：

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）｝是線性獨立的；

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

對于BMOP問題（1），設f，F，g，G都是充分光滑的，F，G是凸的。

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

如果對于給定的點x∈Rn，則｛y∈Rm：G（x，y）＜0｝是非空的，下層優化問題的KKT系統可寫為：

那么問題（1）可等價轉化為如下關于變量（x，y，u）的優化問題：

下面將問題（2）等價轉換為如下問題：

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

若引入函數h0：Rn＋m＋l＋l→Rm＋l＋l如下：

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

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

為了處理互補型約束，文中引進由Kanzow和Jiang［1］提出的NCP函數φμ：R2→R：

式中：μ——擾動參數，μ＞0。

其中

那么，當μ≠0時，可定義最優化問題：

問題（6）是問題（4）關于參數μ的一個光滑擾動問題，盡管問題（4）一般情形下非光滑，但當μ≠0時，問題（6）則是一個光滑最優化問題，且當μ＝0時，問題（6）與問題（4）等價。

記

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

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

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

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

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

由文獻［1］可類似證明hμ有如下性質：

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

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

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

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

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

由此，求解BMOP問題（1）可轉化為解優化問題（6）。

即

2 結 語

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

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

［2］ 劉慶懷，林正華.求解多目標規劃最小弱有效解的同倫內點方法［J］.應用數學學報，2000（2）：188-195.

［3］ 李佳民，劉慶懷.解一類雙層規劃問題的組合同倫方法［J］.吉林大學學報：理學版，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］ 徐俊彥，苗壯，譚佳偉，等.解線性互補問題的組合同倫方法［J］.長春工業大學學報：自然科學版，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.