基于原對(duì)偶內(nèi)點(diǎn)算法求解投資組合優(yōu)化模型

雍龍泉

（陜西理工學(xué)院 數(shù)學(xué)系，陜西 漢中 723001）

1 投資組合優(yōu)化模型

1952年美國學(xué)者M(jìn)arkowitz在Journal of Finance雜志上發(fā)表了一篇文章，題目是Portofolio Selection。這篇文章主張以收益率的方差作為風(fēng)險(xiǎn)的度量，并提出了一個(gè)以極小化風(fēng)險(xiǎn)為目標(biāo)的資產(chǎn)組合選擇模型，稱為均值方差模型。這個(gè)模型及所蘊(yùn)涵的風(fēng)險(xiǎn)分散化思想是現(xiàn)代投資組合理論的基礎(chǔ)[1]。

設(shè)有n種資產(chǎn)可供選擇，這n種資產(chǎn)的收益率為R1，R2，…，Rn(隨機(jī)變量)，均值為 r1，r2，…，rn，協(xié)方差矩陣為 Q=(σij)n×n，其中σij=cov(Ri，Rj)如果每種資產(chǎn)占總資產(chǎn)的比例為x1，x2，…，xn，則投資組合的收益率Rp=R1x1+R2x2+…+Rnxn，其均值

E(Rp)=E((R1x1+R2x2+…+Rnxn)=r1x1+r2x2+…+rnxn，

方差風(fēng)險(xiǎn)

其中 x=(x1，x2，…，xn)T，現(xiàn)在的問題是如何確定每種資產(chǎn)的比例,使資產(chǎn)組合的預(yù)期收益達(dá)到一定水平并使風(fēng)險(xiǎn)最小,其數(shù)學(xué)模型如下:

Markowitz將此模型稱為標(biāo)準(zhǔn)均值方差投資組合選擇模型，目標(biāo)函數(shù)前增加1/2使為了后面計(jì)算方便，這并不影響問題的最優(yōu)解。這里rp是投資組合的預(yù)期收益率，為使問題有可行解，應(yīng)該滿足

min{r1，r2，…，rn}≤rp≤max{r1，r2，…，rn}

則上述模型(M1)可以改寫為下面的形式:

顯然，標(biāo)準(zhǔn)均值方差投資組合選擇模型是一個(gè)較為特殊的二次規(guī)劃，其目標(biāo)函數(shù)不含一次項(xiàng),由于協(xié)方差矩陣Q半正定，因此這是一個(gè)凸二次規(guī)劃。在過去的幾十年里，凸二次規(guī)劃已經(jīng)成為運(yùn)籌學(xué)、經(jīng)濟(jì)數(shù)學(xué)、管理科學(xué)、系統(tǒng)分析和組合優(yōu)化學(xué)科的基本方法。因此，對(duì)凸二次規(guī)劃的研究引起了專業(yè)人員和學(xué)者們的廣泛興趣[2-3]。

求解凸二次規(guī)劃常用的算法有：Lagrange方法、有效集方法、Lemek方法以及求出所有解的整數(shù)標(biāo)號(hào)法[4-5]，但是這些算法都不是多項(xiàng)式算法。1984年，Karmarkar的著名算法——梯度投影算法發(fā)表以來，其理論上的多項(xiàng)式收斂性及實(shí)際計(jì)算的有效性，使得內(nèi)點(diǎn)算法成為近十多年來優(yōu)化界研究的熱點(diǎn)[6]。受Karmarkar算法的影響，凸二次規(guī)劃的內(nèi)點(diǎn)算法緊接著也被提了出來。內(nèi)點(diǎn)算法的基本思想就是在可行域的內(nèi)部產(chǎn)生一個(gè)點(diǎn)列，沿某個(gè)下降方向開始迭代，收斂到原問題的最優(yōu)解，我們把具有這種特點(diǎn)的算法統(tǒng)稱為內(nèi)點(diǎn)算法。1989年，Renato D.C.Monteiro和Ilan ADLER給出了求解二次規(guī)劃的一個(gè)原—對(duì)偶內(nèi)點(diǎn)算法，其迭代次數(shù)為O計(jì)算復(fù)雜性為O(n3.5L)，這是目前理論上最好且最完善的求解二次規(guī)劃的多項(xiàng)式算法[7-8]；本文我們應(yīng)用該算法來求解Markowitz投資組合選擇模型。

2 原對(duì)偶內(nèi)點(diǎn)算法

考慮下列標(biāo)準(zhǔn)形式的凸二次規(guī)劃(QP)以及它的對(duì)偶問題(QD)

其中 Q∈Rn×n是對(duì)稱的半正定矩陣，A∈Rm×n(m≤n)，c，x∈Rn，b∈Rm我們做如下假設(shè):

（A1）集合 S={x∈Rn|Ax=b，x＞0}非空;

（A2）集合 T={(x，y，z)|ATy-Qx+z=c，z＞0}非空，rank(A)=m。

在這些假設(shè)前提下，由對(duì)偶理論可以看出，問題(QP)和(QD)都有解，并且(QP)和(QD)的最優(yōu)解的集合是有界的。

對(duì)于(QP)中的x≥0和(QD)中的 z≥0，為了防止出現(xiàn)“邊界效應(yīng)”，我們可以應(yīng)用對(duì)數(shù)壁壘函數(shù)技術(shù)，把(QP)和(QD)分別轉(zhuǎn)化為下述非線性規(guī)劃問題：

其中 X=diag(x)，Z=diag(z)

移動(dòng)的方向和步長是原對(duì)偶內(nèi)點(diǎn)算法的關(guān)鍵，我們從當(dāng)前點(diǎn)(xk，yk，zk)開始，找到一個(gè)方向(dx，dy，dz)，使其沿著該方向轉(zhuǎn)移到一個(gè)新的點(diǎn)(xk+1，yk+1，zk+1)。本文選用經(jīng)典的Newton法，迭代方向(dx，dy，dz)由如下線性方程組決定:

解該方程組得到:

獲得初始點(diǎn)和牛頓方向后,(QP)和(QD)按如下公式

轉(zhuǎn)移到下一個(gè)新的點(diǎn)。其中0＜ρ＜1，αP和αD分別是原空間和對(duì)偶空間的步長，下面我們來給出αP和αD的選取。x和z的非負(fù)性要求可用來選擇αP和αD，我們采取一種簡單辦法，令

由于對(duì)偶間隙g(μ)=cTx-bTy+xTQx=cTx-(Ax)Ty+xTQx=xT(c-ATy+xTQx)=xTz=nμ，因此，當(dāng)對(duì)偶間隙 nμ＜ε 時(shí)(其中 ε 為容許的誤差)，x為原問題的近似最優(yōu)解,在迭代過程中,我們?nèi)?/p>

μk+1=σμk，（0＜σ＜1）

算法的具體步驟

步驟0 初始化。設(shè)k:=0，并找出一個(gè)初始解(xk，yk，zk)∈S×T，設(shè) ε＞0 為容許的誤差，ρ，σ 是控 制 參 數(shù) 且 ρ∈（0，1），σ ∈（0，1），置 μ0=σn-1(x0)Tz0；

步驟1 檢查最優(yōu)性。若(xk)Tzk≤ε，停止得到最優(yōu)解,否則轉(zhuǎn)步驟2；

步驟2 尋找轉(zhuǎn)移方向，計(jì)算 dxk，dyk，dzk，計(jì)算步長 αP，αD；

步驟3 移動(dòng)到新解，xk+1=轉(zhuǎn)步驟1。

表1 股票收益數(shù)據(jù)

3 模型應(yīng)用

設(shè)有三種股票A、B、C在1943～1954的價(jià)格 （已經(jīng)包括了分紅在內(nèi)）增長情況如表1所示.表中第一個(gè)數(shù)據(jù)1.300的含義是股票A在1943年的年末價(jià)值是其年初價(jià)值的1.300倍,即收益為30%,其余數(shù)據(jù)的含義以此類推.假設(shè)你在1955年時(shí)有一筆資金準(zhǔn)備投資這三種股票,并期望年收益達(dá)到15%,那么應(yīng)如何選擇投資?

記股票A、B、C每年的收益率分別為R1，R2和R3（注意表中的數(shù)據(jù)減去1后才是年收益），則 Ri(i=1，2，3)是一個(gè)隨機(jī)變量。用E，D分別表示隨機(jī)變量的數(shù)學(xué)期望和方差，用cov表示兩個(gè)隨機(jī)變量的協(xié)方差,依據(jù)概率論的知識(shí)和表1中的數(shù)據(jù),則有:

ER1=0.0890833，ER2=0.213667，ER3=0.234583；

DR1=cov(R1，R1)=0.01080754，DR2=cov(R2，R2）=0.05839170，DR3=cov(R3，R3)=0.09422681，cov(R1，R2)=0.01240721，cov(R1，R3)=0.01307513，cov(R2，R3)=0.05542639

設(shè)x1，x2和x3分別表示投資人投資股票A、B、C的比例,則此問題的數(shù)學(xué)模型為:

采用原對(duì)偶內(nèi)點(diǎn)算法進(jìn)行求解,這里

采用Matlab6.5編程求解，在初始點(diǎn)取不同值情況下，算法中的相關(guān)參數(shù)保持一致，取參數(shù)ρ=0.65，σ=0.5，誤差ε=0.0001。經(jīng)過21此迭代，獲得該問題的最優(yōu)解為

x1=0.530091，x2=0.356412，x3=0.113497

利用Matlab提供的二次規(guī)劃求解命令quadprog[9]和非線性規(guī)劃求解軟件LINDO/LINGO[10]分別進(jìn)行了驗(yàn)證，所得的結(jié)果一致，這說明我們計(jì)算的結(jié)果是可靠的。因此，投資這三種股票的比例為:A占53%，B占36%,C占11%。風(fēng)險(xiǎn)方差為0.0224138。

4 結(jié)論

一種股票收益的均值衡量這種股票的平均收益狀況；一種股票收益的方差衡量這種股票收益的波動(dòng)幅度；兩種股票收益的協(xié)方差表示他們之間的相關(guān)程度。本文用原對(duì)偶內(nèi)點(diǎn)算法求解了標(biāo)準(zhǔn)均值方差投資組合選擇模型。該模型具有易擴(kuò)展性，可以通過改變期望的年收益率而得到不同的投資決策，具有較廣泛的應(yīng)用空間和一定的推廣價(jià)值。

[1]張忠楨.凸規(guī)劃——投資組合與網(wǎng)絡(luò)優(yōu)化的旋轉(zhuǎn)算法[M].武漢：武漢大學(xué)出版社，2004.

[2]寇述舜.凸分析與凸二次規(guī)劃[M].天津：天津大學(xué)出版社,1994.

[3]張忠楨.凸規(guī)劃[M].武漢:武漢大學(xué)出版社,2004.

[4]陳寶林.最優(yōu)化理論與算法[M].北京：清華大學(xué)出版社,1989.

[5]寇述舜.線性互補(bǔ)問題全部解的求法——整標(biāo)集法[J].天津大學(xué)學(xué)報(bào),2001,34(5).

[6]Karmarkar.N.A New Polynomial-time Algorithm for Linear Programming[J].Combinatorica,1984,（4）.

[7]Renato D.C.Monteiro，Ilan ADLER.Interior Path Following Primal-dual Algorithms[J].Math.Prog.,1989,（44）.

[8]Monteiro R.C， Alder I， Resende.M.C.A Polynomial-time Primaldual Affine Scaling for Linear and Convex Quadratic Programming and Its Power Series Extension[J].Mathematics of Openation Research,1990,（15）.

[9]王沫然.MATLAB 5.X與科學(xué)計(jì)算[M].北京:清華大學(xué)出版社,2000.[10]謝金星.優(yōu)化建模與LINDO/LINGO軟件[M].北京:清華大學(xué)出版社,2005.