最優(yōu)去杠桿化問(wèn)題的新分枝定界算法

，

(1. 浙江工業(yè)大學(xué) 經(jīng)貿(mào)管理學(xué)院，浙江 杭州 310023；2. 浙江工業(yè)大學(xué) 理學(xué)院，浙江 杭州 310023)

2009年，D′Hulster[1]在世界銀行的報(bào)告中指出：金融機(jī)構(gòu)對(duì)杠桿的過(guò)度使用是最近全球金融危機(jī)發(fā)生的主要成因.杠桿率被認(rèn)為是金融機(jī)構(gòu)承擔(dān)風(fēng)險(xiǎn)和虧損能力的關(guān)鍵因素.在金融困難時(shí)期，金融機(jī)構(gòu)投資者需要解約他們的投資組合來(lái)減少杠桿.在清算大型投資組合時(shí)，如果投資者在有限的市場(chǎng)流動(dòng)性下即刻賣掉所有的資產(chǎn)，投資者必須對(duì)資產(chǎn)的價(jià)格有明顯的妥協(xié).市場(chǎng)微觀結(jié)構(gòu)理論提出交易成本受到臨時(shí)性和永久性價(jià)格沖擊的影響[2].Brown等[3]研究了最優(yōu)去杠桿化問(wèn)題，其中主要目標(biāo)是通過(guò)在一個(gè)較短時(shí)期內(nèi)賣出一部分投資組合中的資產(chǎn)來(lái)產(chǎn)生現(xiàn)金以減少債務(wù)，其模型可歸結(jié)為一個(gè)二次規(guī)劃.Brown等[3]在凸性的假設(shè)下得到了關(guān)于最佳的交易策略的分析結(jié)果.Brown等[3]的凸性假設(shè)要求資產(chǎn)組合中每一項(xiàng)資產(chǎn)的臨時(shí)性價(jià)格沖擊參數(shù)要大于其永久性價(jià)格沖擊參數(shù)的一半.然而，實(shí)證分析表明這個(gè)假設(shè)并不總是成立.例如,Holthausen等[4]觀察到在大宗交易中永久性價(jià)格沖擊占價(jià)格沖擊的主導(dǎo)地位，Sias等[5]在2001年的文章中也提到了類似的現(xiàn)象.為此，Chen等[6]研究了在不限制臨時(shí)性和永久性價(jià)格沖擊影響的大小關(guān)系下的最優(yōu)去杠桿化問(wèn)題，其模型可歸結(jié)為一個(gè)帶有二次和箱子約束的可分離的非凸二次規(guī)劃問(wèn)題.Pardalos等[7]用線性時(shí)間斷點(diǎn)搜索算法來(lái)求解連續(xù)二次背包問(wèn)題，它是一個(gè)帶線性和箱子約束的可分離凸二次規(guī)劃.丁曉東等[8]和蔡偉榮等[9]分別研究了帶邊際風(fēng)險(xiǎn)控制的投資組合問(wèn)題和0-1二次規(guī)劃的半定規(guī)劃松弛.受文獻(xiàn)[7]工作的啟發(fā)，Chen等[6]提出了帶市場(chǎng)價(jià)格影響的最優(yōu)去杠桿化問(wèn)題的拉格朗日斷點(diǎn)算法，證明了該算法在滿足一定條件下能得到全局最優(yōu)解，而當(dāng)條件不滿足時(shí)能得到一個(gè)次最優(yōu)解，并估計(jì)了次優(yōu)解的質(zhì)量.

筆者給出了求最優(yōu)去杠桿化問(wèn)題全局最優(yōu)解的新分枝定界算法及其收斂性.首先，給出了最優(yōu)去杠桿化問(wèn)題的一個(gè)二次凸松弛及其性質(zhì).其次，結(jié)合凸松弛方法和拉格朗日算法[6]，在分枝定界框架下給出了最優(yōu)去杠桿化問(wèn)題的全局算法，證明了算法收斂于全局最優(yōu)解，并進(jìn)行了數(shù)值實(shí)現(xiàn).數(shù)值結(jié)果表明所提出的算法可以有效地找到最優(yōu)去杠桿化問(wèn)題的全局最優(yōu)解.

1 最優(yōu)去杠桿化問(wèn)題的優(yōu)化模型

考慮永久性和臨時(shí)性的價(jià)格影響，Brown等[3]定義去杠桿化過(guò)程中資產(chǎn)的價(jià)格為

pt=p0+Γxt-x0+Λytt∈(0,τ)

式中：pt,xt,yt∈Rm分別為t時(shí)刻投資組合中m種資產(chǎn)的價(jià)格、持有量和交易率的向量；Γ=diag(λ1,…,λm)，其中λi>0為與資產(chǎn)i的累積交易量相關(guān)的永久性價(jià)格沖擊參數(shù)，i=1,…,m；Λ=diag(γ1,…,γm)，其中γi>0為與資產(chǎn)i的交易率相關(guān)的臨時(shí)性價(jià)格沖擊參數(shù)，i=1,…,m；p0>0為資產(chǎn)初始價(jià)格；x0>0為資產(chǎn)初始持有量.資產(chǎn)持有量與交易率滿足

不失一般性，假設(shè)一個(gè)有限的交易周期τ=1.Brown等[3]考慮了一個(gè)具有常數(shù)交易率的交易策略，即

yt=y/τ=y

式中y=x1-x0∈Rm為交易期間的累計(jì)交易額，且x1為交易結(jié)束后投資者持有的資產(chǎn)量.交易結(jié)束后資產(chǎn)價(jià)格為p1=p0+Γy，投資組合的資產(chǎn)

價(jià)值為

是一個(gè)關(guān)于y的二次函數(shù).交易期間產(chǎn)生的現(xiàn)金額為

用來(lái)償還債務(wù).記l0為投資者最初的債務(wù)，交易后的債務(wù)為

投資者的目標(biāo)是在交易結(jié)束后獲得最大的凈資產(chǎn)值.同時(shí)，考慮到金融杠桿率(即債務(wù)與凈資產(chǎn)值的比率)不超過(guò)ρ1的限制，即l1(y)≤ρ1e1(y)，以及投資者不允許賣空與買進(jìn)新資產(chǎn)，即-x0≤y≤0.為此，Brown等[3]建立了單階段最優(yōu)去杠桿化問(wèn)題的優(yōu)化模型為

maxe1(y)

s.t.l1(y)≤ρ1e1(y),-x0≤y≤0

(1)

當(dāng)Λ-Γ/2是正定矩陣時(shí)，問(wèn)題(1)是凸二次規(guī)劃(詳見(jiàn)文獻(xiàn)[3]).注意到當(dāng)永久性價(jià)格主導(dǎo)支配臨時(shí)性價(jià)格時(shí)，矩陣Λ-Γ/2的正定性條件一般是不成立的.Chen等[6]研究了在不受永久性和臨時(shí)性價(jià)格影響的相對(duì)大小的限制下的情形，此時(shí)問(wèn)題(1)是一個(gè)帶箱子和二次約束的非凸二次規(guī)劃，它是NP難問(wèn)題.

2 二次凸松弛

Yl,u=y∈Rm|li≤yi≤ui,i=1,…r,

-x0,i≤yi≤0,i=r+1,…,m

考慮問(wèn)題(1)的一個(gè)限制形式，即

y∈Yl,u

(2)

為了得到問(wèn)題(2)的凸松弛，對(duì)e1y中的凸函數(shù)部分和gy中的凹函數(shù)部分作線性松弛.令

φl(shuí)i,uiyi= -λi-γi/2li+uiyi-liui+x0,iγiyi+e0/m,yi∈li,ui,i=1,…,r

經(jīng)比較易得

fiyi≤φl(shuí)i,uiyiyi∈li,ui

(3)

fili=φl(shuí)i,uili,fiui=φl(shuí)i,uiuii=1,…,r

用φl(shuí)i,uiyi替代問(wèn)題(2)中的fiyi，i=1,…,r，就得到二次凸松弛問(wèn)題為

y∈Yl,u

(4)

由式(3)可知：?jiǎn)栴}(4)的最優(yōu)值是問(wèn)題(2)的一個(gè)上界.

首先比較問(wèn)題(2)和它的凸松弛問(wèn)題(4)在最優(yōu)解處最優(yōu)值的關(guān)系，有如下結(jié)果：

證畢.

由定理1的證明過(guò)程，容易得到下面的推論.

3 新分枝定界全局算法

本節(jié)結(jié)合凸松弛方法和文獻(xiàn)[6]的拉格朗日算法給出最優(yōu)去杠桿化問(wèn)題的新的分枝定界全局算法.值得指出的是：不同于已有分枝定界算法，新分枝定界全局算法是用文獻(xiàn)[6]的拉格朗日算法來(lái)計(jì)算問(wèn)題(1)的下界，并結(jié)合所計(jì)算的下界和二次凸松弛來(lái)確定所得的解是否為全局最優(yōu)解；新算法的分枝維數(shù)是r，而經(jīng)典分枝定界算法的分枝維數(shù)是m.

如圖1所示，說(shuō)話者的話語(yǔ)是有意圖的，說(shuō)話者為了滿足聽(tīng)話者的交際期待，根據(jù)關(guān)聯(lián)認(rèn)知原則和省力原則，將意圖編碼成交際參與者互知的、表達(dá)所言的語(yǔ)言形式，通過(guò)語(yǔ)言編碼明示他的交際意圖，并希望聽(tīng)話者根據(jù)語(yǔ)境、通過(guò)語(yǔ)言解碼推導(dǎo)出他的真正意圖。說(shuō)話者相信聽(tīng)話者能結(jié)合具體語(yǔ)境信息和自身的認(rèn)知語(yǔ)境知識(shí)，解讀話語(yǔ)的所言意義，如果所言意義滿足不了聽(tīng)話者的交際期待，他就以語(yǔ)用確定的方式推導(dǎo)說(shuō)話者話語(yǔ)的隱意。

現(xiàn)在給出求問(wèn)題(1)全局最優(yōu)解的新分枝定界全局算法.

算法1新分枝定界全局算法

輸入：Λ,Γ,x0,p0,ρ1，以及停機(jī)準(zhǔn)則ε>0.

步驟1用文獻(xiàn)[6]的拉格朗日算法求解問(wèn)題(1),得到y(tǒng)*.若y*是問(wèn)題(1)的一個(gè)次最優(yōu)解，則令v*=e1(y*)，執(zhí)行步驟2；否則，y*為問(wèn)題(1)的全局最優(yōu)解，停止.

步驟2(終止條件) 若Ω≠?，執(zhí)行步驟3；否則，y*為問(wèn)題(1)的全局最優(yōu)解，停止.

步驟6令k=k+1，執(zhí)行步驟3.

下面分析當(dāng)ε=0時(shí)算法1的全局收斂性.

由于yk和vk分別為問(wèn)題(4)在Bk=[lk,uk]上的最優(yōu)解和最優(yōu)值，由定理1得

在上式取關(guān)于k∈K的極限得到

4 數(shù)值結(jié)果

本節(jié)給出算法1對(duì)最優(yōu)去杠桿化問(wèn)題的數(shù)值結(jié)果，并與Chen等[6]的拉格朗日算法進(jìn)行數(shù)值比較.算法是在Matlab 2013中實(shí)現(xiàn)，數(shù)值實(shí)驗(yàn)在聯(lián)想PC(處理器主頻為2.40 GHz，內(nèi)存為4.00 GHz)上進(jìn)行.算法1中凸二次子問(wèn)題用軟件CPLEX中的凸二次規(guī)劃求解器來(lái)求解.

表1新分枝定界算法與拉格朗日算法的數(shù)值比較

Table1Thenumericalcomparisonofnewbranch-and-boundalgorithmandLagrangealgorithm

mr拉格朗日算法[6]最優(yōu)值花費(fèi)時(shí)間/sT新分枝定界算法最優(yōu)值花費(fèi)時(shí)間/s1020．09460．001600．09180．00601040．23060．000200．22860．00241040．05430．000400．05350．01141020．31450．002810．31450．00281010．07650．002110．07650．00215080．67250．006110．67250．006150160．30200．002200．30030．01225090．50520．000500．50470．002350150．66890．000400．66730．004750130．64790．003810．64790．0038100220．95680．003210．95680．0032100321．55850．001701．55260．0060100180．94260．001400．93720．0051100261．29080．003211．29080．0032100260．41150．002000．41040．0108

5 結(jié) 論

考慮了不限制臨時(shí)性和永久性價(jià)格沖擊參數(shù)大小關(guān)系的最優(yōu)去杠桿化問(wèn)題，它是一個(gè)帶有箱子約束和二次約束的非凸二次規(guī)劃問(wèn)題，求它的全局最優(yōu)解是NP-難的.提出了基于拉格朗日算法和二次凸松弛技術(shù)的新分枝定界全局算法，分析了算法的收斂性，并進(jìn)行了數(shù)值實(shí)現(xiàn).數(shù)值結(jié)果表明新算法能夠有效地找到最優(yōu)去杠桿化問(wèn)題的全局解.

[1] D′HULSTER K. The leverage ratio: a new binding limit on banks[EB/OL]. [2017-04-03]. http://www.worldbank.org/financialcrisis/pdf/levrage-ratio-web.pdf.

[2] MADHAVAN A. Market microstructure: a survey[J]. Journal of financial markets, 2000, 3(3):205-258.

[3] BROWN D B, CARLIN B I, LOBO M S. Optimal portfolio liquidation with distress risk[J]. Management science, 2010, 56(11):1997-2014.

[4] HOLTHAUSEN R W, LEFTWICH R W, MAYERS D. Large-block transactions, the speed of response, and temporary and permanent stock-price effects[J]. Journal of financial economics, 1990, 26(1):71-95.

[5] SIAS R W, STARKS L T, TITMAN S. The price impact of institutional trading[EB/OL]. [2017-04-03]. http://papers.ssrn.com/sol3/papers.cfm?abstract_id.

[6] CHEN J, FENG L, PENG J, et al. Analytical results and efficient algorithm for optimal portfolio deleveraging with market impact[J]. Operations research, 2014, 62(1):195-206.

[7] PARDALOS P M, KOVOOR N. An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds[J]. Mathematical programming, 1990, 46(1):321-328.

[8] 丁曉東,肖琳燦,羅和治.帶邊際風(fēng)險(xiǎn)控制的投資組合問(wèn)題的半定規(guī)劃松弛[J].浙江工業(yè)大學(xué)學(xué)報(bào),2017,45(1):64-68.

[9] 蔡偉榮,柳葉,羅和治.基于矩陣分解的0-1二次規(guī)劃的SDP松弛[J].浙江工業(yè)大學(xué)學(xué)報(bào),2015,43(5):582-586.