帶有勢(shì)約束的組合最優(yōu)化的一種解法

曲鐵平，里 莉

(1.沈陽(yáng)理工大學(xué) 理學(xué)院，遼寧 沈陽(yáng) 110159；2.沈陽(yáng)化工大學(xué) 數(shù)理系，遼寧 沈陽(yáng) 110114)

帶有勢(shì)約束的組合最優(yōu)化的一種解法

曲鐵平1，里 莉2

(1.沈陽(yáng)理工大學(xué) 理學(xué)院，遼寧 沈陽(yáng) 110159；2.沈陽(yáng)化工大學(xué) 數(shù)理系，遼寧 沈陽(yáng) 110114)

從經(jīng)典的馬克維茨投資組合問(wèn)題引出一個(gè)一般的組合最優(yōu)化模型，并給出此模型的一個(gè)解法.首先，由拉格朗日分解從原模型的對(duì)偶問(wèn)題得出一個(gè)二階錐規(guī)化的松弛.其次，給出一個(gè)新的含混合整數(shù)二次約束的二次規(guī)化的改進(jìn).最后，證明了此改進(jìn)的連續(xù)松弛問(wèn)題比原問(wèn)題的連續(xù)松弛問(wèn)題更緊.

拉格朗日分解；二階錐規(guī)化；組合最優(yōu)化

組合最優(yōu)化的應(yīng)用十分廣泛，但因?yàn)樗且粋€(gè)NP難問(wèn)題，使得求得最優(yōu)解的過(guò)程變得異常困難，即不可能在多項(xiàng)式時(shí)間內(nèi)尋得其最優(yōu)解.先以投資組合的經(jīng)典問(wèn)題為例看一下組合最優(yōu)化的求解模型.馬克維茨投資組合模型[1-2]在投資組合理論中十分重要，他的期望—方差模型中用期望度量投資的期望收益，用方差度量組合風(fēng)險(xiǎn).已有很多關(guān)于帶有勢(shì)約束和二次約束的組合最優(yōu)化模型的求解成果，比如Bertsimas等[3]提出了一種分支定界法，其中子問(wèn)題的連續(xù)松弛是用Lemke方法求解.Bonami等[4]研究了帶有整數(shù)約束和最小買入約束的投資組合問(wèn)題，其中也用了分支定界方法.Shaw等[5]提出了一種建立在拉格朗日松弛基礎(chǔ)上的分支定界法求解帶有勢(shì)約束的期望—方差模型，在分支定界步驟中的每個(gè)子問(wèn)題的拉格朗日對(duì)偶是用次梯度的方法求解.不過(guò)以上方法在解決此類組合優(yōu)化問(wèn)題時(shí)只能得到近似解，且近似程度也不一定很好.本文針對(duì)帶有勢(shì)約束和二次約束的二次規(guī)化問(wèn)題提出一種近似解法，且可證明此近似解的緊性較好.這不僅為此類組合最優(yōu)化問(wèn)題提供了一個(gè)更好的下界，具有一定的理論意義，而且為投資組合等領(lǐng)域的問(wèn)題提供了更好的近似解，也具有一定的應(yīng)用意義.

1 一般模型

關(guān)于投資組合問(wèn)題的經(jīng)典的期望—方差模型是考慮市場(chǎng)有n個(gè)可投資資產(chǎn)，令R1表示第i個(gè)資產(chǎn)的隨機(jī)收益，x=(x1,x2,…xn)T是各個(gè)資產(chǎn)的投資權(quán)重，所以投資組合的總收益的期望和方差分別為r(x)=μTx,σ(x)=xTΣx，其中μ=(μ1,…,μn)T，而μi=E(Ri)，協(xié)方差矩陣Σ=(σij)，而σij=E[(Ri-μi)(Rj-μj)]，所以馬克維茨經(jīng)典的期望—方差模型如下：

minxTΣx

s.t.μTx≥ρ

x∈X

(1)

式中,ρ表示總收益水平的常數(shù)；X是由預(yù)算等其他市場(chǎng)約束確定的集合.

考慮到現(xiàn)實(shí)中的約束情況，在上述經(jīng)典模型中加入用于限制投資資產(chǎn)數(shù)量的勢(shì)約束和最小買入約束，即

|S(x)|≤K,xi≥ai,?i∈S(x)，其中投資資產(chǎn)集合S(x)={i|xi≠0},0

更為一般的投資組合模型為

(2)

式中：Qi∈Sn(i=1,2)是半正定矩陣；Di是非負(fù)對(duì)角矩陣；ci∈Rn(i=1,2)；A∈Rm×n；b∈Rm；u∈Rn是給出x的上界.

2 拉格朗日分解和混合整數(shù)二次約束的二次規(guī)劃改進(jìn)

討論如何使用拉格朗日松弛技術(shù)得到問(wèn)題(2)的一個(gè)凸緊松弛.由拉格朗日分解從模型(2)的對(duì)偶問(wèn)題得出一個(gè)二階錐規(guī)劃松弛，給出一個(gè)新的混合整數(shù)二次約束的二次規(guī)劃改進(jìn)，此改進(jìn)的連續(xù)松弛恰好等價(jià)于二階錐規(guī)劃松弛.

2.1 拉格朗日分解

通過(guò)引入一個(gè)0-1變量yi∈{0,1}將問(wèn)題(2)等價(jià)成一個(gè)混合整數(shù)二次約束的二次規(guī)劃問(wèn)題：

(3)

如果將約束中的0-1集合{0,1}n改為[0,1]n，問(wèn)題(3)即松弛為一個(gè)二次約束的二次規(guī)劃問(wèn)題.先引入變量z=x，上述問(wèn)題(3)等價(jià)于：

(4)

d1(λ,γ)=minxT(Q1+λQ2)x+(c1+λc2-γ)Tx

s.t.Ax≤b0≤x≤u

(5)

d2(λ,γ)=minzT(D1+λD2)z+γTz

s.t.eTy≤K

aiyi≤zi≤uiyi,i=1,2,…,n

y∈{0,1}n

(6)

此問(wèn)題的對(duì)偶問(wèn)題為

maxd(λ,γ)

s.t.λ≥0，γ∈Rn

(7)

根據(jù)弱對(duì)偶性，總有v7≤v3=v2，其中v1表示規(guī)劃問(wèn)題i的最優(yōu)解，i=2,3,7.

2.2 二階錐規(guī)劃松弛

將對(duì)偶問(wèn)題(7)松弛為一個(gè)二階錐規(guī)劃問(wèn)題，根據(jù)強(qiáng)對(duì)偶定理和錐對(duì)偶性，可將問(wèn)題(7)松弛為下面的半正定規(guī)化問(wèn)題：

(8)

式中X∈Sn為對(duì)稱矩陣.由錐對(duì)偶定理[6]，如果問(wèn)題(8)是嚴(yán)格可行的，那么強(qiáng)對(duì)偶性成立，即沒(méi)有對(duì)偶間隙，假設(shè)在問(wèn)題(3)的可行域中存在相對(duì)內(nèi)點(diǎn)，那么由此假設(shè)可知問(wèn)題(8)的可行域也是嚴(yán)格可行的.

注意到Qi∈Sn(i=1,2)是半正定矩陣，可以用xTQ1x和xTQ2x分別代替X·Q1和X·Q2，那么問(wèn)題(8)變?yōu)橄铝袉?wèn)題：

(9)

定理1說(shuō)明問(wèn)題(9)比問(wèn)題(3)的松弛問(wèn)題(4)更緊.

定理1v4≤v9≤v2,其中vi表示規(guī)劃問(wèn)題(i)的最優(yōu)解，i=2,4,9.

2.3 混合整數(shù)二次約束的二次規(guī)劃改進(jìn)

已知二階錐規(guī)化問(wèn)題(9)是下面的問(wèn)題(10)的連續(xù)松弛：

(10)

定理2指出問(wèn)題(10)與問(wèn)題(3)等價(jià).

定理2 (x,y,δ)是問(wèn)題(10)的解當(dāng)且僅當(dāng)(x,y)是問(wèn)題(3)的解，進(jìn)而有v10=v3，其中v1表示規(guī)劃問(wèn)題(i)的最優(yōu)解，i=3,10.

從定理1與定理2看到問(wèn)題(10)是比標(biāo)準(zhǔn)的問(wèn)題(3)更為有效的改進(jìn)，因?yàn)閱?wèn)題(10)的松弛問(wèn)題(9)比問(wèn)題(3)的松弛問(wèn)題(4)更緊.

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

本文對(duì)一類帶有勢(shì)約束和二次約束的組合最優(yōu)化模型求解提供了一個(gè)更好的下界，提高了解的近似程度，具有一定的理論意義，而且為投資組合等領(lǐng)域的問(wèn)題提供了更好的近似解，也具有一定的應(yīng)用意義.

[1]Markowitz HM.Portfolio selection[J].Finance，1952，(7)：77-91.

[2]Markowitz H.M.Portfolio selection：Efficient Diversification of Investments[M].Wiley，NewYork，1959.

[3]Bertsimas D，Shioda R.Algorithm for cardinality-constrained quadratic optimization[J].Comput.Optim.Appl，2009，(43)：1-22.

[4]Bonami P，Lejeune M.A.An exact solution approach for portfolio optimization problems understochastic and integer constraints[J].Oper.Res，2009，(57)：650-670.

[5]Shaw D，Liu S，Kopman L.Lagrangian relaxation proceduer for cardinality-constrainedportfolioo ptimization[J].Optim.Methods Softw，2008，(23)：411-420.

[6]Vandenberghe L，Boyd S.Semidefinite programming[J].SIAM Rev，1996，(38)：49-95.

(責(zé)任編輯：馬金發(fā))

A Method of Solving Combination Optimization with Cardinality-constrained

QU Tieping1,LI Li2

(1.Shenyang Ligong University,Shenyang 110159,China;2.Shenyang Huagong University,Shenyang 110114,China)

A method for solving a general combination optimization model is introduced from the classical Markowitz portfolio selection problem.The first,a second-order cone program’s relaxation is obtained from the dual of original model via Lagrangian decomposition.The next,a new mixed integer quadratically constrained quadratic program reformulation presented.The last,it is shown that the reformulation’s continuous relaxation is tighter than the original program’s.

Lagrangian decomposition;second-order cone program;combination optimization

2014-07-07

曲鐵平(1960—)，男，副教授，研究方向：基礎(chǔ)數(shù)學(xué)。

1003-1251(2015)03-0067-03

O221.7

A