不確定平方和凸多項式優化的SDP松弛與魯棒鞍點刻畫

譚 玟,孫祥凱

(重慶工商大學 數學與統計學院,重慶 400067)

凸多項式優化是凸優化問題的一個重要模型,在自動控制系統、交通運輸和工程設計等領域應用廣泛,并取得了很多研究成果[1-4].平方和凸多項式優化作為凸多項式優化問題的一個子類,近年來也得到廣泛關注,因為它可以等價地表示為一個半定線性優化問題,并能通過內點法有效解決[5].此外,平方和凸多項式優化具有精確的半正定規劃(SDP)松弛問題,且原問題與其對偶問題之間存在零對偶間隙[6-8].

上述研究平方和凸多項式優化問題時,通常需要假設所考慮優化問題模型的數據是精確的.但在實際應用中,由于測量、制作誤差以及不精確數據等諸多因素影響,所建模型的優化問題不可避免地存在不確定數據.因此,帶有不確定參數的平方和凸多項式優化問題目前已引起人們廣泛關注.例如: Jeyakumar等[9]基于常見的不確定集,得到了不確定平方和凸優化問題的魯棒解刻畫和精確的SDP松弛問題; Chuong[10]借助線性矩陣不等式以及平方和條件,研究了不確定多目標平方和凸多項式優化問題的最優性條件和對偶定理; Jiao等[11]借助標量化方法,刻畫了不確定多目標平方和凸多項式優化問題的魯棒有效解,并證明了對應的標量問題與松弛問題之間的零對偶間隙; Chuong等[12]借助一類魯棒型閉凸錐約束規格,刻畫了不確定凸二次多目標優化問題的魯棒(弱)有效解的最優性條件.

受上述研究結果的啟發,本文給出一類不確定平方和凸優化問題的魯棒鞍點定理.首先,借助魯棒優化方法,引入不確定平方和凸多項式優化問題的魯棒對等問題; 然后,借助一類魯棒型特征錐約束規格,得到該不確定平方和凸多項式優化問題的精確SDP松弛問題; 最后,引入該不確定平方和凸多項式優化問題的Langrange函數,并借助平方和條件給出其魯棒鞍點定理.

1 預備知識

定義1[5]設f為n上的實多項式,若多項式

f(x)-f(y)-f(y)T(x-y)

注1顯然,平方和凸多項式是凸多項式,但反之不一定成立[13-14].進一步,凸二次函數和凸可分離多項式都是平方和凸多項式.此外,一個平方和凸多項式可能既不是二次的也不是可分離的[5].

本文考慮如下不確定平方和凸多項式優化問題(UP):

其中vj(j=1,2,…,m)為不確定參數且屬于不確定集Vj?k,f:n→和gf:n×Vj→(j=1,2,…,m)均為給定的函數.若無特殊說明,本文總假設f是平方和凸多項式,對任意的vj∈Vj,gj(·,vj)是平方和凸多項式,對任意的x∈n,gj(x,·)是仿射函數,即

定義2問題(UP)的魯棒可行集定義為

F∶={x∈n|gj(x,vj)≤0,?vj∈Vj,j=1,2,…,m}.

2 精確SDP松弛

下面借助一類魯棒型約束規格,建立問題(UP)的精確SDP松弛問題.

2) 顯然,若魯棒Slater條件

{x∈n|gj(x,vj)<0,?vj∈Vj,j=1,2,…,m}≠?

成立,則魯棒型特征錐約束規格(RCCCQ)成立[19].因此條件(RCCCQ)弱于魯棒Slater條件.

下面借助條件(RCCCQ),給出問題(UP)的精確SDP松弛問題.

定理1對于問題(UP),假設F≠?.若條件(RCCCQ)成立,則

證明: 結合文獻[20]中定理3.1及文獻[21]中定理2.1的證明方法,易得結論成立.

推論1[9]對于問題(UP),假設F≠?.若魯棒Slater條件成立,則

證明: 由注2中2)并結合定理1,易得結論成立.

注3由于條件(RCCCQ)弱于魯棒Slater條件,因此定理1改進并推廣了文獻[9]中定理2.3的相關結果.

若不確定集Vj(j=1,2,…,m)為單點集,則易得如下結論.

推論2考慮如下平方和凸多項式優化問題(P):

假設{x∈n|gj(x)≤0,j=1,2,…,m}≠?,且f:n→與gj:n→(j=1,2,…,m)均為平方和凸多項式.若條件(CCCQ)成立,則

3 魯棒鞍點定理

注4若不確定集Vj(j=1,2,…,m)為單點集,則問題(P)的Lagrange函數定義為

即對任意的x∈n,有

(1)

故結合式(1)可得

另一方面,對任意的x∈n,有

例1設m=1,k=2.令不確定集V1?2為

考慮不確定平方和凸多項式優化問題(UP):

易證

證明: 由注2中2)并結合定理2,易得結論成立.

證明: 由注2中1)并結合推論2及定理2,易得結論成立.