凸二次半定規劃一個新的原始對偶路徑跟蹤算法

黎健玲,安婷,曾友芳,鄭海艷

( 廣西大學數學與信息科學學院,廣西 南寧530004)

1.引言

本文考慮如下二次半定規劃(簡記為QSDP)

其中函數φ:Sn→Sn為自伴隨線性算子,Sn表示n階實對稱矩陣空間.Ai(i=1,···,m),C和X都是n× n階實對稱矩陣,b∈Rm.表示矩陣的內積,即?A∈Rp×q,B∈Rp×q,〈A,B〉=tr(ATB).X ?0 和X ?0 分別表示矩陣X是對稱半正定矩陣和對稱正定矩陣.

凸二次半定規劃是半定規劃[1?4]的推廣,其在證券,金融,最優控制等領域中有著廣泛的應用,因此對凸二次半定規劃的研究受到學者們的關注,并已取得一批研究成果(見文[5–10]).文[5]提出了一個預估校正算法,該算法至多經次迭代可得到一個?最優解.文[8]提出了一個非精確原始對偶路徑跟蹤算法.文[9]提出了一個基于參數核函數的原始-對偶內點算法.

受線性半定規劃的HKM方向啟發,本文提出一個基于HKM方向的新原始-對偶路徑跟蹤算法.在每次迭代中,算法通過求解一個線性方程組產生HKM搜索方向.在一定條件下證明了算法產生的迭代點列落在中心路徑的鄰域內,且算法至多經O(n|log?|) 次迭代可得到一個?-最優解.

在一定的假設條件下,分析了該算法的迭代復雜度.

QSDP(1.1)的對偶問題(簡記為QSDD)為

其中y∈Rm,Z∈Sn.

分別記QSDP(1.1)和QSDD(1.2)的可行域為FP和FD,并記F0P和F0D分別為FP和FD的嚴格內部,即

對于任意的可行點X和(X,y,Z),則對偶間隙為

本文需作如下基本假設:

假設(A1) 線性算子φ(X)是對稱半正定的,即滿足

假設(A2) Slater約束規格成立,即存在X ?0,Z ?0,y∈Rm,使得X∈F0P,(X,y,Z)∈F0D;

假設(A3) 矩陣A1,A2,···,Am線性無關.

2.HKM 方向

稱滿足如下方程組

的點(X,y,Z) 構成的集合為中心路徑,其中為中心參數,I為n階單位矩……