兩階段金融衍生品清算問題的半定規劃松弛方法

摘" 要： 在不限制暫時性及永久性價格影響參數大小關系下，研究兩階段金融衍生品清算問題的半定規劃（Semi-definite programming， SDP）松弛方法，其優化模型為一個帶有線性和單個非凸二次約束的非凸二次規劃（Quadratically constrained quadratic program， QCQP）問題。針對該非凸QCQP問題，給出了一個帶有Secant割的SDP松弛，并估計了它與原問題之間的間隙。隨機例子的數值結果表明該SDP松弛可以得到原問題更緊的上界，從而為尋求原問題的一個好的近似解提供方法。

關鍵詞： 兩階段清算模型；金融衍生品；非凸二次規劃；SDP松弛；Secant割

中圖分類號： O224

文獻標志碼： A

文章編號： 1673-3851 （2024） 04-0566-07

DOI：10.3969/j.issn.1673-3851（n）.2024.04.016

收稿日期： 2022-10-12" 網絡出版日期：2023-01-16網絡出版日期

基金項目： 國家自然科學基金項目（12271485，11871433）；浙江省自然科學基金項目（LZ21A010003）

作者簡介： 李" 葉（1997—" ），女，江西南昌人，碩士研究生，主要從事最優化理論與算法方面的研究。

通信作者： 羅和治，E-mail：hzluo@zstu.edu.cn

引文格式：李葉，洪陳春，羅和治. 兩階段金融衍生品清算問題的半定規劃松弛方法［J］. 浙江理工大學學報（自然科學），2024，51（4）：566-572.

Reference Format： LI Ye， HONG Chenchun， LUO Hezhi. The semi-definite programming relaxation method for two-period financial derivatives′ liquidation problem［J］. Journal of Zhejiang Sci-Tech University，2024，51（4）：566-572.

The semi-definite programming relaxation method for two-period financial derivatives′ liquidation problem

LI Ye1， HONG Chenchun2， LUO Hezhi1

（1.School of Science， Zhejiang Sci-Tech University， Hangzhou 310018， China;

2. Huaxin Consulting Co.， Ltd.， Hangzhou 310014， China）

Abstract：" The semi-definite programming （SDP） relaxation method for two-period financial derivatives′ liquidation problem is studied without restricting the relationship between the magnitude of the temporary and permanent price impact parameters， and the optimization model is a nonconvex quadratically constrained quadratic programming （QCQP） problem with linear and single nonconvex quadratic constraints. An SDP relaxation with secant cuts for this nonconvex QCQP problem is presented and the gap between it and the original problem is estimated. The numerical results of random instances show that the SDP relaxation can obtain a tighter upper bound to the original problem and then provides a method for finding a good approximate solution to the problem.

Key words： two-period liquidation model; financial derivatives; nonconvex quadratic programming; SDP relaxation; Secant cut

0" 引" 言

清算持有的投資組合資產被認為是投資者在面臨財務困境時最常采取的手段。設計一種有效的清算策略，以最小的交易成本滿足現金需求，對機構投資者和個人投資者至關重要。如果投資者不加選擇地拋售大量資產，會造成非常大的交易成本。因此，在更多情況下，投資者會在一段時間內逐步進行交易。在清算過程中，由于早期的交易活動會對后續交易造成持續性的影響，在減少交易成本時需重點考慮價格影響因素。Madhava等［1］將價格影響分為暫時和永久的價格影響，暫時性價格影響表示進行交易時價格的瞬時變化，而永久性價格影響表示交易前后價格的變化。

Brown等［2］研究了帶有永久和暫時價格影響的最優投資組合降杠桿問題，并要求交易后投資組合的杠桿率降低到可接受的水平；此外，他們考慮到交易后可能會出現流動性沖擊，提出了兩階段模型，并指出在清算過程中對資產清算優先順序進行選擇時，需著重考慮資產價格的不確定性因素。在Brown等［2］的啟發下，Chen［3］研究了資產種類更豐富的投資組合清算問題，提出了一個關于金融衍生品的兩階段魯棒優化模型，并在凸性假設下證明了該模型等價于一個半定規劃（Semi-definite programming， SDP）問題。值得一提，文獻［3］中的凸性假設要求暫時性價格影響因素占主導地位。然而，實證分析表明了這種假設并不總是成立［4］。本文在去掉凸性假設下研究兩階段金融衍生品清算問題，其優化模型歸結為一個帶有非正變量、線性不等式和單個二次約束的非凸二次規劃問題（Quadratically constrained quadratic program， QCQP），求其全局最優解是非常困難的。

眾所周知，非凸QCQP問題一般是NP-難的［5］。由于SDP松弛方法可以為非凸QCQP問題提供緊的松弛界和好的近似解［6］，學者們對于非凸QCQP問題提出了各種形式的SDP松弛。丁曉東等［7］針對帶邊際風險控制的投資組合優化問題提出了一個緊的SDP松弛；章顯業等［8］針對帶凸二次約束的非凸QP問題提出了一個緊的雙非負規劃松弛；Luo等［9］利用罰函數方法提出了二次約束線性規劃問題的SDP松弛；Zheng等［10-11］針對非凸QCQP問題分別提出了基于二次型的最佳D.C.分解以及基于矩陣錐分解和多胞形逼近技術的緊SDP松弛；Eltved等［12］針對廣義信賴域子問題，提出了基于割技術的緊SDP松弛；Azuma等［13］針對一類特殊QCQP問題，給出了精確SDP松弛解的充分條件。

本文在沒有要求暫時性及永久性價格影響參數大小關系的條件下，研究兩階段金融衍生品清算問題的SDP松弛方法，以尋求其最優值的緊松弛界。針對問題的特殊結構，提出了一個帶有Secant割的SDP松弛，并給出它與原問題之間的間隙估計。

本文引入如下記號：Sn為n階對稱矩陣的集合，Tr（A）為矩陣A的跡；對于B∈Sn，B0表示矩陣B為半正定矩陣；X，Y∈Sn，X·Y=Tr（XY）為X，Y的內積；diag（a）為以向量a的分量為對角元的對角矩陣；In為n階單位矩陣。

1" 兩階段金融衍生品清算模型

本節介紹Chen［3］提出的兩階段金融衍生品清算問題的優化模型，該模型能夠以最少的交易成本找到滿足現金需求的最優清算策略，并利用Delta-gamma近似方法［14］估計金融衍生品的收益率。

在第i階段，i=1，2，設yi、pi∈Rn表示各資產的交易量及資產價格。Λ、Φ分別表示臨時性和永久性價格影響矩陣，由于只考慮同一資產之間的價格影響因素，則Λ、Φ為n階對角矩陣，其對角元素分別為λi，i（gt;0），i=1，…，n。Λyi表示因為供需不平衡造成的暫時性影響，Φyi是交易后的信息不對稱對資產價格產生的影響。x0∈Rn表示各資產的初始持有量，在清算期間不允許賣空或買入其他資產的約束可表示為：

y1≤0，y2≤0，-x0≤y1+y2。

設r∈Rn為第一階段的資產收益率，Chen［3］采用Delta-gamma近似方法將金融衍生品的收益率近似為關于其標的資產收益率的二次函數：

ri≈firb=θ-iTp1，i+diag（pb1）Δ-ip1，iTrb+12rbTdiagpb1TΓ-idiagpb1p1，irb，

其中：rb，pb1∈Rn表示標的資產的收益率和初始價格；T表示清算前后的時間長度；θ-i、Δ-i和Γ-i（Greeks）是作為衡量金融衍生品風險的指標，對于只擁有一項標的資產j的金融衍生品i，Δ-i為僅第j個元素非零的向量，Γ-i為僅第j個對角元素非零的矩陣。

考慮到資產流動產生的暫時性影響，這兩個階段的實際交易價格分別為p1+Λy1和p2+Λy2，且交易后會同樣會產生永久性影響，第一階段的交易行為會影響第二階段初始的資產價格，因此p2=diag（e+f（rb））p1+Φy1，其中：f（rb）=［f1（rb），…，fn（rb）］T，e∈Rn為分量全為1的向量。所以清算后產生的總現金流K為：

K（y1，y2）=-（p1+Λy1）Ty1-（p2+Λy2）Ty2

=-y1

y2TΛ12Φ

12ΦΛy1

y2-p1

diag（e+f（rb））p1Ty1

y2。

設a、l為清算后的資產和負債，l0為初始負債。由于第二階段的永久性影響Φy2會影響交易后的資產價格，且無需考慮第二階段的資產收益，所以在計算清算后的資產a時的資產價格為p2+Φy2。清算過程產生的現金流可用于清償負債，故清算后的凈資產值為

e（y1，y2）=a-l=（p2+Φy2）T（x0+y1+y2）-（l0-K（y1，y2））=-y1y2TΛ-Φ-12Φ-12ΦΛ-Φy1y2+Φx0+diag（f（rb））p1Φx0Ty1y2+x0Tdiag（e+f（rb））p1-l0。

清算問題的目標是最大化交易后的凈資產，在滿足現金流需求的同時盡量減少由價格影響造成的交易成本。因此，兩階段金融衍生品的清算模型可歸結為如下帶有線性和單個二次約束的二次規劃問題：

maxy1，y2∈Rne（y1，y2）;

s.t." K（y1，y2）≥κ，

-x0≤y1+y2，

y1≤0，y2≤0（1）

其中：κ為清算后最低的現金流需求。文獻［3］假設Λ-Φ為半正定矩陣，從而問題（1）是一個凸二次規劃，證明了問題（1）等價于一個SDP問題。在沒有假設Λ-Φ為半正定性的條件下，問題（1）是一個非凸二次約束二次規劃，求其全局最優解是NP-難的。

2" SDP松弛方法及間隙估計

本節給出求解問題（1）的一個SDP松弛，并估計其與原問題之間的間隙。

為方便描述，將問題（1）重新改寫為如下QCQP問題：

miny∈R2n" f（y）=yTQ0y+q0Ty+d0;

s.t." g（y）=yTQ1y+q1Ty+d1≤0，

Ay≤x0，y≤0（2）

其中：

y=y1

y2，Q0=Λ-Φ-12Φ

-12ΦΛ-Φ，Q1=Λ12Φ

12ΦΛ，

q0=-Φx0+diag（f（rb））p1

Φx0，q1=p1

diag（e+f（rb））p1，

d0=x0Tdiag（e+f（rb））p1-l0，d1=κ，A=-In-In。

注意到Q0、Q1均為分塊矩陣，且每一子塊均為對角矩陣。定理1給出了這類分塊矩陣的特征值及其相應的正交單位特征向量。

定理1" 設Q=ABBA，其中A=diag（α1，…，αn）和B=diag（β1，…，βn）為對角陣，再設μ1，…，μn，μn+1，…，μ2n為Q的特征值，且ζ1，…，ζn，ζn+1，…，ζ2n∈R2n為其對應的正交單位特征向量，則

a）μi=αi+βi，μn+i=αi-βi，i=1，…，n；

b）若αi，βi≠0，i=1，…，n，且αi+βi≠αj+βj，αi-βi≠αj-βj，i，j=1，2，…，n，i≠j，則

ζi，i=ζi，n+i=22，ζi，j=0，j=1，…，2n，j≠i，n+i，i=1，…，n，

ζn+i，i=22，ζn+i，n+i=-22，ζn+i，j=0，j=1，…，2n，j≠i，n+i，i=1，…，n。

證明" a）計算矩陣Q的特征多項式：

f（μ）=μIn-A-B

-BμIn-A=μIn-A-B

μIn-A-BμIn-A-B

=μIn-A+B-B

OμIn-A-B=μIn-A+BμIn-A-B

=（μ-α1+β1）…（μ-αn+βn）（μ-α1-β1）…（μ-αn-βn），

其中O為n階零矩陣。令f（μ）=0，得Q的特征值為μi=αi+βi，μn+i=αi-βi，i=1，…，n。

b）當μ1=α1+β1時，齊次線性方程組為（Q-μ1I2n）x=0，其中I2n為2n階單位矩陣。注意到β1≠0，α1+β1≠αj+βj，j=2，…，n。經矩陣行初等變換，系數矩陣化為階梯型矩陣：

Q-μ1I2n=-β10…0β10…0

0α2-μ1…00β2…0

00…αn-μ100…βn

β10…0-β10…0

0β2…00α2-μ100

00…βn00…αn-μ1

→10…0-10…0

01…001…0

00…100…1

00…00β2-α2+μ1…0

00…000…βn-αn+μ1

00…000…0，

得基礎解系：η1=（1，0，…0，1，0，…，0）T，再單位化得ζ1=22，0，…0，22，0，…，0T。同理，對i=2，…，n，當μi=αi+βi時，由（Q-μiI2n）x=0得基礎解系：ηi=（ηi，1，…，ηi，2n）T，其中：ηi，i=ηi，n+i=1，ηi，j=0，j=1，…，2n，j≠i，n+i。再單位化得ζi=（ζi，1，…，ζi，2n）T，其中：ζi，i=ζi，n+i=22，ζi，j=0，j=1，…，2n，j≠i，n+i，i=2，…，n。

對i=1，…，n，當μn+i=αi-βi時，由（Q-μn+iI2n）x=0，利用矩陣行初等變換和條件αi-βi≠αj-βj，j=1，…，n，j≠i，得基礎解系：ηn+i=（ηn+i，1，…，ηn+i，2n）T，其中：ηn+i，i=1，ηn+i，n+i=-1，ηn+i，j=0，j=1，…，2n，j≠i，n+i，再單位化得ζn+i=（ζn+i，1，…，ζn+i，2n）T，其中：ζn+i，i=22，ζn+i，n+i=-22，ζn+i，j=0，j=1，…，2n，j≠i，n+i。

注意到ζ1，…，ζn，ζn+1，…，ζ2n是兩兩正交的。故ζ1，…，ζn，ζn+1，…，ζ2n為矩陣Q相應于特征值μ1，…，μn，μn+1，…，μ2n的正交單位特征向量。

證畢。

由定理1，立得Q0、Q1的特征值和相應的正交單位特征向量。

推論1" 設μki，μkn+i，i=1，…n為Qk的特征值，k=0，1，則

μ0i=λi-32i，μ0n+i=λi-12i，i=1，…，n；

μ1i=λi+12i，μ1n+i=λi-12i，i=1，…，n。

并且Q0、Q1有相同的正交單位特征向量ζ1，…，ζn，ζn+1，…，ζ2n∈R2n，其中

ζi，i=ζi，n+i=22，ζi，j=0，j=1，…，2n，j≠i，n+i，i=1，…，n；

ζn+i，i=22，ζn+i，n+i=-22，ζn+i，j=0，j=1，…，2n，j≠i，n+i，i=1，…，n。

基于推論1，給出問題（2）的一個帶有Secant割的SDP松弛。不失一般性，設Q0、Q1的前r0，r1個特征值為負。根據推論1，對Qk特征值分解，得Qk=Qk+-CkTCk，k=0，1，其中：

Qk+=∑2ni=rk+1μkiζiζTi0，Ck=（-μk1ζ1，…，-μkrkζrk）T，

且μkilt;0，i=1，…，rk，μki≥0 i=rk+1，…，2n，k=0，1。令Y=yyT，得yTQky=Qk·Y，k=0，1。設lk，uk∈Rrk分別為Cky在可行域上的下界和上界，k=0，1，其中：

（y，Y）∈R2n×S2nQ1·Y+q1Ty+d1≤0

Ay≤x0，y≤0

YyyT。

令cki=-μkiζi，i=1，…，rk，k=0，1，則lk，uk可通過求解如下SDP問題得到：

lki=min（y，Y）∈（cki）Ty，

uki=max（y，Y）∈（cki）Ty，i=1，…，rk，k=0，1。

當lki≤（cki）Ty≤uki時，有：

cki（cki）T·Y=（（cki）Ty）2≤（lki+uki）（cki）Ty-lkiuki，i=1，…，rk，k=0，1（3）

其中：式（3）為Saxena等［15］所提出的Secant割。將Y=yyT松弛為半正定錐約束YyyT，可得問題（2）的如下SDP松弛問題：

min "Q0·Y+q0Ty+d0；

s.t." Q1·Y+q1Ty+d1≤0，

cki（cki）T·Y≤（lki+uki）（cki）Ty-lkiuki，i=1，…，rk，k=0，1，

Ay≤x0，y≤0，

YyyT（4）

定理2估計了問題（2）與問題（4）之間的間隙。記g^（y，Y）=Q1·Y+q1Ty+d1，且f*和v*分別為問題（2）和問題（4）的最優值。

定理2" 設（y-，Y-）為問題（4）的最優解，則

f（y-）-f*≤∑r0i=1c0i（c0i）T·Y--（（c0i）Ty-）2≤14‖u0-l0‖22，

g（y-）≤∑r1i=1c1i（c1i）T·Y--（（c1i）Ty-）2≤14‖u1-l1‖22。

證明" 因問題（4）是問題（2）的松弛，故f*≥v*。根據Q0=Q0+-C0TC0，Y-yyT0以及問題（4）中的Secant割約束，可推得：

f（y-）-f*≤f（y-）-v*=Q0·（y-y-T-Y-）=Q+0·（y-y-T-Y-）+∑r0i=1c0i（c0i）T·Y--（（c0i）Ty-）2

≤∑r0i=1c0i（c0i）T·Y--（（c0i）Ty-）2

≤∑r0i=1-（（c0i）Ty-）2+（l0i+u0i）（c0i）Ty--l0iu0i

≤14‖u0-l0‖22。

同理，由Q1=Q1+-C1TC1，Y-yyT0及（y-，Y-）的可行性，可推得

g（y-）≤g（y-）-g^（y-，Y-）=Q1·（y-y-T-Y-）

=Q+1·（y-y-T-Y-）+∑r1i=1c1i（c1i）T·Y--（（c1i）Ty-）2≤∑r1i=1c1i（c1i）T·Y--（（c1i）Ty-）2

≤∑r1i=1-（（c1i）Ty-）2+（l1i+u1i）（c1i）Ty--l1iu1i≤14‖u1-l1‖22。

證畢。

推論2" 設（y-，Y-）為問題（4）的最優解。若cki（cki）T·Y-=（（cki）Ty-）2，i=1，…，rk，k=0，1，則y-為問題（2）的最優解。

證明" 由定理2及假設，得f（y-）-f*≤0，g（y-）≤0。結合Ay-≤x0，y-≤0，知y-為問題（2）的可行解，從而f（y-）≥f*。因此，f（y-）=f*。故y-為問題（2）的最優解。

證畢。

3" 數值實驗

本節給出了求解問題（1）和問題（4）的平均數值結果，并通過數值實驗驗證SDP松弛為原問題提供緊的松弛界。數值實驗在MATLAB（R2018b）中實現，電腦的操作系統為Windows 10，處理器為Intel（R） Core（TM）i7-10710U CPU（1.10 GiHz），運行內存為16 GiB。

在數值實驗中，對隨機生成的10個問題進行測試，并用MOSEK求解器求解SDP問題（4），GUROBI求解器求解問題（1）。測試問題中的參數類似于文獻［3］的方法隨機產生，即：Λ、Φ的對角元服從U（10-5，10-4），即區間［10-5，10-4］上的均勻分布；θ-服從U（-0.1，-0.01），Δ-i的元素服從U（0，1），Γ-i的元素服從U（0.01，0.1），x0，i=104，p1，i=1，p1，i=1，rbi=-0.05，i=1，…，n，κ=0.2×（x0）Tp1。

表1給出了GUROBI求解器對問題（1）及MOSEK求解器對問題（4）的10個隨機測試例子的平均數值結果，其中：“vopt”“vub”和“時間”分別表示對10個測試例子得到的問題（1）的平均最優值、問題（4）的平均最優值以及平均CPU時間（單位：s）；“（*）”表示求解器在3600 s內求得全局最優解的實例數，“—”表示求解器未能在3600 s內找到全局最優解；“vgap”表示問題（1）和問題（4）全局最優值的相對間隙（單位：%），計算公式為：

vgap/%=vub-vopt|vopt|×100。

由表1可知，按照相對間隙，SDP松弛問題（4）能為問題（1）提供更緊的上界。當問題維數及Q0、Q1的負特征值個數增多時，GUROBI求解速度較慢，并且當n≥100時，GUROBI無法在3600 s內求到最優解。相比之下，松弛問題（4）在n=200時仍有效求解，并為原問題提供更緊的上界。

4" 結" 語

本文在不限制暫時性價格影響因素占主導地位的交易市場中研究兩階段金融衍生品清算問題，其模型是一個帶線性和單個非凸二次約束的非凸二次規劃問題，給出了該模型的一個帶有Secant割的SDP松弛及其間隙估計。隨機例子的數值結果表明，本文提出的SDP松弛能為原問題提供了更緊的上界。

參考文獻：

［1］Madhavan A . Market microstructure： A survey［J］. Journal of Financial Markets， 2000， 3（3）： 205-258.

［2］Brown D B， Carlin B I， Lobo M S. Optimal portfolio liquidation with distress risk［J］. Management Science， 2010， 56（11）：1997-2014.

［3］Chen J N. Optimal liquidation of financial derivatives［J］. Finance Research Letters， 2020， 34： 101233.

［4］Sias R W， Starks L T， Titman S. The price impact of institutional trading［M］. SSRN， 2001.［EB/OL］.（2001-09-19）［2022-10-12］.https：∥papers.ssrn.com/sol3/papers.cfm？abstract_id=283779.

［5］Pardalos P M， Vavasis S A. Quadratic programming with one negative eigenvalue is NP-hard［J］. Journal of Global Optimization， 1991， 1（1）： 15-22.

［6］Ye Y Y. Approximating quadratic programming with bound and quadratic constraints［J］. Mathematical Programming， 1999， 84（2）： 219-226.

［7］丁曉東， 肖琳燦， 羅和治. 帶邊際風險控制的投資組合問題的半定規劃松弛［J］. 浙江工業大學學報， 2017， 45（1）： 64-68.

［8］章顯業， 羅和治. 帶凸二次約束非凸二次規劃的雙非負規劃松弛及其解法［J］. 浙江理工大學學報（自然科學版）， 2022， 47（4）： 601-607.

［9］Luo H Z， Bai X D， Peng J M. Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods［J］. Journal of Optimization Theory and Applications， 2019， 180（3）： 964-992.

［10］Zheng X J， Sun X L， Li D. Convex relaxations for nonconvex quadratically constrained quadratic programming： matrix cone decomposition and polyhedral approximation［J］. Mathematical Programming， 2011， 129（2）： 301-329.

［11］Zheng X J， Sun X L， Li D. Nonconvex quadratically constrained quadratic programming： best D.C. decompositions and their SDP representations［J］. Journal of Global Optimization， 2011， 50（4）： 695-712.

［12］Eltved A， Burer S. Strengthened SDP relaxation for an extended trust region subproblem with an application to optimal power flow［J］. Mathematical Programming， 2022： 1-26.

［13］Azuma G， Fukuda M， Kim S， et al. Exact SDP relaxations of quadratically constrained quadratic programs with forest structures［J］. Journal of Global Optimization， 2022， 82（2）： 243-262.

［14］Zymler S， Kuhn D， Rustem B. Worst-case value at risk of nonlinear portfolios［J］. Management Science， 2013， 59（1）： 172-188.

［15］Saxena A， Bonami P， Lee J. Convex relaxations of non-convex mixed integer quadratically constrained programs： projected formulations［J］. Mathematical Programming， 2011， 130（2）： 359-413.

（責任編輯：康" 鋒）