本文在没有凸性假设下考虑两阶段金融衍生品清算问题, 其优化模型为NP-难的带单个非凸二次约束和线性约束的非凸二次规划问题。针对该模型的特殊结构, 构造了一个快速的新半定规划(semi-definite programming, SDP)松弛, 估计了它与原问题之间的间隙, 并证明了它比文献中已有SDP松弛提供更紧的下界。数值实验表明该SDP松弛能快速得到原问题的一个非常紧的下界, 为设计求解原问题全局最优解的分支定界算法提供有效的下界。
In this paper, we consider a two-period financial derivative liquidation problem without the convexity assumption. Its optimization model is a non-convex quadratic programming problem with a single quadratic constraint and linear constraints, which is NP-hard. We propose a faster new semi-definite programming (SDP) relaxation for this model by making use of its special structure, and estimate the gap between it and the original problem. We also show that it provides a tighter lower bound than the existing SDP relaxation in the literature. Numerical experiments show that this SDP relaxation can fast provide a very tight lower bound for the original problem, thus can provide effective lower bounds in branch-and-bound algorithm to find the global optimal solution of the problem.
[1] Brown D B, Carlin B, Lobo M S. Optimal portfolio liquidation with distress risk [J]. Management Science, 2010, 56(11): 1997-2014.
[2] Carlin B I, Lobo M S. Cooperative and predatory trading [J]. The Journal of Finance, 2007, 62(5): 35-74.
[3] Luo H Z, Chen Y Y, Zhang X Y, et al. Effective algorithms for optimal portfolio deleveraging problem with cross impact [J]. Mathematical Finance, 2024, 34: 36-89.
[4] Chen J N. Optimal liquidation of financial derivatives [J]. Finance Research Letters, 2020, 34: 101233.
[5] Cornuejols G, Tutuncu R. Optimization Methods in Finance [M]. Cambridge: Cambridge University Press, 2006.
[6] Sias R W, Starks L T, Titman S. The price impact of institutional trading [EB/OL]. [2024- 02-01]. https://papers.ssrn.com/sol3/papers.cfm?abstractid=283779.
[7] 李叶，洪陈春，罗和治，两阶段金融衍生品清算问题的半定规划松弛方法[J] .浙江理工大学学报， 2023，49(1)：26-32.
[8] Audet C, Hansen P, Jaumard B, et al. A branch and cut algorithm for nonconvex quadratically constrained quadratic programming [J]. Mathematical Programming, 2000, 87: 131-152.
[9] Linderoth J. A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs [J]. Mathematical Programming, 2005, 103: 251-282.
[10] Luo H Z, Bai H D, Lim G, et al. New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation [J]. Mathematical Programming Computation, 2019, 11(1): 119-171.
[11] Lu C, Deng Z, Zhou J. et al. A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming [J]. Journal of Global Optimization, 2019, 73: 371-388.
[12] 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.
[13] 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.
[14] 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.
[15] Wang A L, Karzan K F. On the tightness of SDP relaxations of QCQPs [J]. Mathematical Programming, 2022, 193: 33-73.
[16] Song M M, Liu H Y, Wang J L, et al. On local minimizers of nonconvex homogeneous quadratically constrained quadratic optimization with at most two constraints [J]. SIAM Journal on Optimization, 2023, 33(1): 267-293.
[17] Zymler S, Kuhn D, Rustem B. Worst-case value at risk of nonlinear portfolios [J]. Management Science, 2013, 59(1): 172-188.
[18] Markowitz H M. Portfolio selection [J]. The Journal of Finance, 1952, 7(1): 77-91.
北大中文核心期刊