最优去杠杆化问题的新分枝定界算法

，

(1. 浙江工业大学 经贸管理学院，浙江 杭州 310023；2. 浙江工业大学 理学院，浙江 杭州 310023)

2009年，D′Hulster[1]在世界银行的报告中指出：金融机构对杠杆的过度使用是最近全球金融危机发生的主要成因.杠杆率被认为是金融机构承担风险和亏损能力的关键因素.在金融困难时期，金融机构投资者需要解约他们的投资组合来减少杠杆.在清算大型投资组合时，如果投资者在有限的市场流动性下即刻卖掉所有的资产，投资者必须对资产的价格有明显的妥协.市场微观结构理论提出交易成本受到临时性和永久性价格冲击的影响[2].Brown等[3]研究了最优去杠杆化问题，其中主要目标是通过在一个较短时期内卖出一部分投资组合中的资产来产生现金以减少债务，其模型可归结为一个二次规划.Brown等[3]在凸性的假设下得到了关于最佳的交易策略的分析结果.Brown等[3]的凸性假设要求资产组合中每一项资产的临时性价格冲击参数要大于其永久性价格冲击参数的一半.然而，实证分析表明这个假设并不总是成立.例如,Holthausen等[4]观察到在大宗交易中永久性价格冲击占价格冲击的主导地位，Sias等[5]在2001年的文章中也提到了类似的现象.为此，Chen等[6]研究了在不限制临时性和永久性价格冲击影响的大小关系下的最优去杠杆化问题，其模型可归结为一个带有二次和箱子约束的可分离的非凸二次规划问题.Pardalos等[7]用线性时间断点搜索算法来求解连续二次背包问题，它是一个带线性和箱子约束的可分离凸二次规划.丁晓东等[8]和蔡伟荣等[9]分别研究了带边际风险控制的投资组合问题和0-1二次规划的半定规划松弛.受文献[7]工作的启发，Chen等[6]提出了带市场价格影响的最优去杠杆化问题的拉格朗日断点算法，证明了该算法在满足一定条件下能得到全局最优解，而当条件不满足时能得到一个次最优解，并估计了次优解的质量.

笔者给出了求最优去杠杆化问题全局最优解的新分枝定界算法及其收敛性.首先，给出了最优去杠杆化问题的一个二次凸松弛及其性质.其次，结合凸松弛方法和拉格朗日算法[6]，在分枝定界框架下给出了最优去杠杆化问题的全局算法，证明了算法收敛于全局最优解，并进行了数值实现.数值结果表明所提出的算法可以有效地找到最优去杠杆化问题的全局最优解.

1 最优去杠杆化问题的优化模型

考虑永久性和临时性的价格影响，Brown等[3]定义去杠杆化过程中资产的价格为

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

式中：pt,xt,yt∈Rm分别为t时刻投资组合中m种资产的价格、持有量和交易率的向量；Γ=diag(λ1,…,λm)，其中λi>0为与资产i的累积交易量相关的永久性价格冲击参数，i=1,…,m；Λ=diag(γ1,…,γm)，其中γi>0为与资产i的交易率相关的临时性价格冲击参数，i=1,…,m；p0>0为资产初始价格；x0>0为资产初始持有量.资产持有量与交易率满足

不失一般性，假设一个有限的交易周期τ=1.Brown等[3]考虑了一个具有常数交易率的交易策略，即

yt=y/τ=y

式中y=x1-x0∈Rm为交易期间的累计交易额，且x1为交易结束后投资者持有的资产量.交易结束后资产价格为p1=p0+Γy，投资组合的资产

价值为

是一个关于y的二次函数.交易期间产生的现金额为

用来偿还债务.记l0为投资者最初的债务，交易后的债务为

投资者的目标是在交易结束后获得最大的净资产值.同时，考虑到金融杠杆率(即债务与净资产值的比率)不超过ρ1的限制，即l1(y)≤ρ1e1(y)，以及投资者不允许卖空与买进新资产，即-x0≤y≤0.为此，Brown等[3]建立了单阶段最优去杠杆化问题的优化模型为

maxe1(y)

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

(1)

当Λ-Γ/2是正定矩阵时，问题(1)是凸二次规划(详见文献[3]).注意到当永久性价格主导支配临时性价格时，矩阵Λ-Γ/2的正定性条件一般是不成立的.Chen等[6]研究了在不受永久性和临时性价格影响的相对大小的限制下的情形，此时问题(1)是一个带箱子和二次约束的非凸二次规划，它是NP难问题.

2 二次凸松弛

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

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

考虑问题(1)的一个限制形式，即

y∈Yl,u

(2)

为了得到问题(2)的凸松弛，对e1y中的凸函数部分和gy中的凹函数部分作线性松弛.令

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

经比较易得

fiyi≤φli,uiyiyi∈li,ui

(3)

fili=φli,uili,fiui=φli,uiuii=1,…,r

用φli,uiyi替代问题(2)中的fiyi，i=1,…,r，就得到二次凸松弛问题为

y∈Yl,u

(4)

由式(3)可知：问题(4)的最优值是问题(2)的一个上界.

首先比较问题(2)和它的凸松弛问题(4)在最优解处最优值的关系，有如下结果：

证毕.

由定理1的证明过程，容易得到下面的推论.

3 新分枝定界全局算法

本节结合凸松弛方法和文献[6]的拉格朗日算法给出最优去杠杆化问题的新的分枝定界全局算法.值得指出的是：不同于已有分枝定界算法，新分枝定界全局算法是用文献[6]的拉格朗日算法来计算问题(1)的下界，并结合所计算的下界和二次凸松弛来确定所得的解是否为全局最优解；新算法的分枝维数是r，而经典分枝定界算法的分枝维数是m.

如图1所示，说话者的话语是有意图的，说话者为了满足听话者的交际期待，根据关联认知原则和省力原则，将意图编码成交际参与者互知的、表达所言的语言形式，通过语言编码明示他的交际意图，并希望听话者根据语境、通过语言解码推导出他的真正意图。说话者相信听话者能结合具体语境信息和自身的认知语境知识，解读话语的所言意义，如果所言意义满足不了听话者的交际期待，他就以语用确定的方式推导说话者话语的隐意。

现在给出求问题(1)全局最优解的新分枝定界全局算法.

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

输入：Λ,Γ,x0,p0,ρ1，以及停机准则ε>0.

步骤1用文献[6]的拉格朗日算法求解问题(1),得到y*.若y*是问题(1)的一个次最优解，则令v*=e1(y*)，执行步骤2；否则，y*为问题(1)的全局最优解，停止.

步骤2(终止条件) 若Ω≠∅，执行步骤3；否则，y*为问题(1)的全局最优解，停止.

步骤6令k=k+1，执行步骤3.

下面分析当ε=0时算法1的全局收敛性.

由于yk和vk分别为问题(4)在Bk=[lk,uk]上的最优解和最优值，由定理1得

在上式取关于k∈K的极限得到

4 数值结果

本节给出算法1对最优去杠杆化问题的数值结果，并与Chen等[6]的拉格朗日算法进行数值比较.算法是在Matlab 2013中实现，数值实验在联想PC(处理器主频为2.40 GHz，内存为4.00 GHz)上进行.算法1中凸二次子问题用软件CPLEX中的凸二次规划求解器来求解.

表1新分枝定界算法与拉格朗日算法的数值比较

Table1Thenumericalcomparisonofnewbranch-and-boundalgorithmandLagrangealgorithm

mr拉格朗日算法[6]最优值花费时间/sT新分枝定界算法最优值花费时间/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 结 论

考虑了不限制临时性和永久性价格冲击参数大小关系的最优去杠杆化问题，它是一个带有箱子约束和二次约束的非凸二次规划问题，求它的全局最优解是NP-难的.提出了基于拉格朗日算法和二次凸松弛技术的新分枝定界全局算法，分析了算法的收敛性，并进行了数值实现.数值结果表明新算法能够有效地找到最优去杠杆化问题的全局解.

[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] 丁晓东,肖琳灿,罗和治.带边际风险控制的投资组合问题的半定规划松弛[J].浙江工业大学学报,2017,45(1):64-68.

[9] 蔡伟荣,柳叶,罗和治.基于矩阵分解的0-1二次规划的SDP松弛[J].浙江工业大学学报,2015,43(5):582-586.