一種錐規(guī)化的近似解法

李 揚，顧世煜

(1.沈陽理工大學(xué) 理學(xué)院，沈陽 110159； 2.東北中山中學(xué)，沈陽110001)

錐規(guī)化是一種特殊的凸規(guī)化，是線性規(guī)劃的推廣，是在一個仿射空間和一個正則錐的交集上，求線性目標(biāo)函數(shù)的極大或極小值。錐規(guī)化問題涵蓋了線性規(guī)劃、凸二次約束規(guī)化、半正定規(guī)化、二次錐規(guī)化。近些年，由于錐規(guī)化理論和算法的發(fā)展，且在投資組合優(yōu)化、最小風(fēng)險套利、協(xié)方差矩陣的逼近等方面有廣泛的應(yīng)用，因而錐規(guī)化是數(shù)學(xué)規(guī)劃領(lǐng)域的一個活躍的研究方向。錐規(guī)化問題是NP難問題,這種問題沒有一個多項式時間的算法。Bomze等[1]嘗試用可行下降法對錐規(guī)化求解，然而這種方法無法證明解的收斂性，并且需要額外的工作去找出一個可行的起始點，而找可行起始點的難度不亞于解決原問題。Zilinskas[2]使用一種單純形劃分的方法去解錐規(guī)化問題的對偶問題,但模型求解的運行時間過長。Deng等[3]將錐規(guī)化問題近似轉(zhuǎn)化為一個二次規(guī)化問題，然后利用在橢球域上的非負(fù)二次函數(shù)定義的對偶錐，解一個線性錐規(guī)化序列，得到原問題的近似解。以上研究得到的近似解要么計算繁瑣，要么得到解的近似程度不高。

本文引入建立在集合FSOC上的一種非負(fù)二次形式錐，利用一系列的非負(fù)二次形式錐近似計算一種有用的NP難錐規(guī)化問題，是利用對一種標(biāo)準(zhǔn)單形的劃分去逼近對偶錐的方法，根據(jù)半正定規(guī)化的解法，得出NP難錐規(guī)化問題一個比較好的下界，進(jìn)而得到原問題的一種近似解。隨著對標(biāo)準(zhǔn)單形的分割越來越細(xì)，同時逼近錐規(guī)化問題(P)下界的誤差也越來越小。

1 基本概念

給定集合S?Rn,在S上的非負(fù)二次形式的錐定義為

CF={M∈Sn|xTMx≥0,?x∈F}，

式中Sn是n階實對稱矩陣，其對偶錐[4-5]是

式中，cl表示閉集，Cone表示集合的錐包。

一種標(biāo)準(zhǔn)的錐規(guī)化[2]的形式如下：

minf(X)=D·X

s.t.Ai·X=bi,i=1,2,…,m,

(P)

X∈C*

錐規(guī)化在二次規(guī)化和組合最優(yōu)化中非常有用[6]，Burer[7]證明了帶有線性和0-1約束的二次規(guī)化問題都可以改寫為錐規(guī)化模型(P)，許多組合最優(yōu)化也都可以轉(zhuǎn)化為模型(P)問題，但模型(P)是NP難問題，即不能在多項式時間找到最優(yōu)解，這就需要找到其近似解。

2 基本性質(zhì)

定理2設(shè)F?Rn是閉凸集,則CF=CCone(F)。

定理3對于上述定義的二階錐FSOC和GSOC，有FSOC=Cone(GSOC)。

由定理2與定理3的結(jié)果，顯然有以下推論：

推論 對于上述定義的二階錐FSOC和GSOC，有CFSOC=CGSOC。

3 錐規(guī)化模型(P)的近似解

(AP)

假設(shè)標(biāo)準(zhǔn)單形Δ劃分為Δ=Δ1∪Δ2…∪Δk，那么(AP)模型可改進(jìn)為：

(APP)

此問題的對偶問題如下：

(DAAP)

4 結(jié)束語

本文建立在集合FSOC上的一種非負(fù)二次形式錐，利用一系列的非負(fù)二次形式的錐近似計算一種有用的NP難錐規(guī)化問題(P)，利用對標(biāo)準(zhǔn)單形的劃分去逼近對偶錐，根據(jù)半正定規(guī)化的解法，得出這種NP難錐規(guī)化問題的一個比較好的下界，進(jìn)而得到原問題的一個近似解。對于模型(APP)，隨著分割步驟的反復(fù)進(jìn)行，標(biāo)準(zhǔn)單形Δ被分割的越來越細(xì)，同時逼近錐規(guī)化問題(P)下界的誤差也越來越小。更好的逼近原來錐規(guī)化問題(P)的近似解。