李 揚(yáng)，顧世煜

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

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

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

1 基本概念

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

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

式中Sn是n階實(shí)對(duì)稱矩陣，其對(duì)偶錐[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ī)化問(wèn)題都可以改寫(xiě)為錐規(guī)化模型(P)，許多組合最優(yōu)化也都可以轉(zhuǎn)化為模型(P)問(wèn)題，但模型(P)是NP難問(wèn)題，即不能在多項(xiàng)式時(shí)間找到最優(yōu)解，這就需要找到其近似解。

2 基本性質(zhì)

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

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

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

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

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

(AP)

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

(APP)

此問(wèn)題的對(duì)偶問(wèn)題如下：

(DAAP)

4 結(jié)束語(yǔ)

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